Taller Grafos
Descargar el siguiente archivo y realizar el taller sobre grafos que en el se encuentra
1. Para los siguientes grafos
Conteste las siguientes preguntas:
a. Explique la diferencia entre los dos grafos anteriores
b. En el grafo dirigido hay una trayectoria para ir de D hasta A?. sí la hay describa la trayectoria y si no que le colocaría al grafo para que se de esa trayectoria y escríbala.
c. Diga cual es el número máximo de lados que pueden tener los dos grafos
d. Represente el grafo dirigido con matriz de adyacencia
e. Represente el grafo no dirigido con lista ligada de adyacencia
f. Represente el grafo dirigido con matriz de incidencia
g. Represente el grafo dirigido con lista ligada de adyacencia
h. Cuantos ciclos se pueden dar en ambos grafos y escriba cada uno de ellos
i. Hallar el grado para cada uno de los vértices de cada grafo
2. Construir un algoritmo que permita crear la matriz de adyacencia en un grafo no dirigido.
3. Construir un algoritmo que permita crear la matriz de incidencia en un grafo no dirigido.
4. Defina con sus palabras:
a) Adyacencia
b) Incidencia
c) Grado de un grafo
d) Trayectoria
e) Trayectoria simple
f) Ciclo
g) Grafo conectado
h) Grafo fuertemente conectado
5. Investigar los Recorridos sobre grafos:
5.1 Investigar que es el Recorrido DFS sobre grafos y un ejemplo
5.2 Investigar que es el Recorrido BFS sobre grafos y un ejemplo
SOLUCION
a. Diferencia entre los dos grafos
Grafo no dirigido: En este grafo, los arcos no tienen dirección, lo cual significa que la relación entre los nodos es bidireccional. Cada arista puede ser recorrida en ambos sentidos.
Grafo dirigido: En este grafo, las aristas tienen una dirección específica, representada con flechas. Esto significa que cada arista solo puede ser recorrida en la dirección indicada, estableciendo una relación unidireccional entre los nodos.
b. Trayectoria de D a A en el grafo dirigido
No existe una trayectoria directa que vaya de D -> A Para que se pueda llegar de D -> A podríamos agregar una arista que vaya de D -> A haci como lo muestra en la imagen
c. Número máximo de lados que pueden tener los grafos
Grafo no dirigido: El número máximo de lados posibles del grafo es: 15
Grafo dirigido: El número máximo de lados posibles del grafo es : 20
d. Matriz de adyacencia del grafo dirigido
e. Lista ligada de adyacencia para el grafo no dirigido
f. Matriz de incidencia del grafo dirigido
g. Lista ligada de adyacencia del grafo dirigido
h. Ciclos en ambos grafos
Grafo no dirigido
En el grafo no dirigido, un ciclo es una secuencia de vértices que comienza y termina en el mismo vértice identificamos los siguientes ciclos:
- Ciclo 1: A → C → B → A
- Ciclo 2: B → A → C → B
- Ciclo 3: C → A → B → C
- Ciclo 4: C → D → F → E → C
- Ciclo 5: F → E → C → D → F
- Ciclo 6: E → F → D → C → E
- Ciclo 7: D → C → E → F → D
Grafo dirigido
En el grafo dirigido, un ciclo es una secuencia de vértices que comienza y termina en el mismo vértice identificamos los siguientes ciclos:
- Ciclo 1: D → E → D
i. Grado de cada vértice en cada grafo
Grafo dirigido:
- A: Grado de entrada 0, grado de salida 2 , grado total = 2
- B: Grado de entrada 1, grado de salida 3, grado total = 4
- C: Grado de entrada 1, grado de salida 1, grado total = 2
- D: Grado de entrada 3, grado de salida 1, grado total = 4
- E: Grado de entrada 3, grado de salida 1, grado total = 4
Grafo no dirigido:
- A: Grado 2
- B: Grado 2
- C: Grado 4
- D: Grado 2
- E: Grado 2
- F: Grado 2
2. algoritmo para matriz de adyacencia en un grafo no dirigido
4. definicion de palabras:
a) Adyacencia: Dos nodos son adyacentes si están conectados directamente por un lado; es decir, hay un "camino directo" entre ellos.
b) Incidencia: Una arista incide en un nodo si ese nodo es uno de sus extremos, o dicho de otra manera, si el lado "toca" o conecta a ese nodo.
c) Grado de un grafo: Es el número de conexiones (lados) que tiene un nodo en el grafo. Para nodos en grafos dirigidos, se especifica el "grado de entrada" (lados que llegan) y "grado de salida" (lados que salen).
d) Trayectoria: Es un camino que se sigue en un grafo de un nodo a otro, pasando por varios nodos conectados.
e) Trayectoria simple: Es una trayectoria donde no se repite ningún nodo; cada nodo se visita una sola vez.
f) Ciclo: Es una trayectoria que comienza y termina en el mismo nodo, formando un "circuito cerrado".
g) Grafo conectado: Es un grafo en el que siempre existe al menos un camino entre cualquier par de nodos.
h) Grafo fuertemente conectado: En un grafo dirigido, significa que existe una trayectoria en ambas direcciones entre cada par de nodos; puedes ir de cualquier nodo a otro y regresar.
5.1 Recorrido DFS (Depth-First Search)
Qué es DFS: El recorrido en profundidad (Depth-First Search o DFS) explora un grafo profundizando lo más que se pueda en cada rama antes de retroceder. Comienza desde un nodo y va avanzando hacia los nodos adyacentes hasta que ya no hay nodos por explorar en esa rama; luego retrocede al último punto donde haya una conexión no explorada y continúa.
Ejemplo: Imagina un grafo con los nodos A, B, C, D y E conectados así:
- A está conectado a B y C.
- B está conectado a D.
- C está conectado a E.
Si empezamos en A, el DFS exploraría de la siguiente forma:
- A → B → D (comienza en A, profundiza a B y luego a D).
- Al no haber más conexiones desde D, retrocede y prueba otro camino.
- A continuación, explora desde A hacia C y luego E.
Resultado: El orden de recorrido sería A, B, D, C, E.
5.2 Recorrido BFS (Breadth-First Search)
Qué es BFS: El recorrido en amplitud (Breadth-First Search o BFS) explora un grafo nivel por nivel, primero revisando todos los nodos adyacentes al nodo de inicio antes de profundizar. Utiliza una estructura de cola para recordar el orden de exploración.
Ejemplo: Tomando el mismo grafo (A, B, C, D, E) y comenzando en A:
- A explora sus nodos adyacentes: B y C.
- Luego explora desde B, moviéndose a D.
- A continuación, explora desde C y se mueve a E.
Resultado: El orden de recorrido sería A, B, C, D, E.