Taller Grafos
Introduce un texto aquí...
1. Para los siguientes grafos
Conteste las siguientes preguntas:
1. · 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 gafos 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
Conteste las siguientes preguntas:
1. · 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 gafos 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 el Recorrido DFS sobre grafos y un ejemplo
5.2 Investigar que el Recorrido BFS sobre grafos y un ejemplo
Solución
1. Diferencias: La diferencia entre los dos grafos mas notoria es que el primero no es dirigido al contrario del segundo que si es dirigido.
B. No se encuentra una trayectoria entre A y D, para generar una trayectoria entre estos dos nodos se debe crear una incidencia dirigida de A hacia D
C. Primer grafo = n=6 | 6 * (6-1)/2 | 30/2 | = 15
Segundo grafo = n= 5 | 5 * (5-1) | 5 * 4 | = 20
D. 1. grafo:
2 grafo:
E.
F.
G.
.H,
En el grafo 1, se pueden dar tres ciclos: A-B-C-A, A-C-E-F-A, y A-D-F-A. En el grafo 2, se puede dar un ciclo: A-E-D-A.
I.
En el grafo 1, los grados de los vértices son los siguientes:
En el grafo 2, los grados de los vértices son los siguientes:
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: En un grafo, dos nodos son adyacentes si están conectados por una arista. La adyacencia es una relación simétrica, lo que significa que si el nodo A está conectado al nodo B, entonces el nodo B también está conectado al nodo A.
b) Incidencia: En un grafo, la incidencia se refiere a la relación entre los nodos y las aristas. Si una arista une dos nodos, entonces se dice que la arista incide en esos dos nodos. La matriz de incidencia es una forma de representar esta relación en una matriz.
c) Grado de un grafo: El grado de un nodo en un grafo es el número de aristas que inciden en ese nodo. El grado de un grafo es la suma de los grados de todos los nodos en el grafo.
d) Trayectoria: Una trayectoria en un grafo es una secuencia de nodos en la que cada par de nodos consecutivos está conectado por una arista. La longitud de una trayectoria es el número de aristas que contiene.
e) Trayectoria simple: Una trayectoria simple es una trayectoria en la que no se visitan nodos repetidos. Es decir, cada nodo en la trayectoria aparece solo una vez.
f) Ciclo: Un ciclo en un grafo es una trayectoria cerrada en la que el primer y el último nodo son el mismo. Un ciclo simple es un ciclo en el que no se visitan nodos repetidos, excepto para el primer y el último nodo.
g) Grafo conectado: Un grafo se dice que es conectado si hay una trayectoria entre cualquier par de nodos en el grafo. Es decir, no hay nodos aislados en el grafo.
h) Grafo fuertemente conectado: Un grafo dirigido se dice que es fuertemente conectado si hay una arista dirigida entre cualquier par de nodos en el grafo. Es decir, no hay nodos aislados y se puede llegar a cualquier nodo desde cualquier otro nodo siguiendo las aristas dirigidas.
5. Investigar los Recorridos sobre grafos:
En cuanto a los recorridos sobre grafos, estos son una técnica utilizada para visitar todos los vértices de un grafo. Hay dos formas de recorrer un grafo: recorrido en profundidad y recorrido en anchura. Si el conjunto de nodos marcados se trata como una cola, entonces el recorrido es en anchura; si se trata como una pila, el recorrido es en profundidad 1. El recorrido en anchura es una generalización del recorrido por niveles de un árbol. Se trata de visitar un nodo inicial y luego a todos los nodos que están a un arco de distancia de éste, luego a todos los nodos que están a dos arcos de distancia de éste y así sucesivamente, hasta alcanzar a todos los nodos a los que se pueda llegar desde el nodo inicial. Una aplicación típica de este recorrido es la resolución de problemas de planificación. La búsqueda en amplitud se puede utilizar para hallar la distancia más corta entre algún nodo inicial y los nodos restantes del grafo 1.
5.1 Investigar que el Recorrido DFS sobre grafos y un ejemplo
El recorrido DFS (Depth First Search) es un algoritmo utilizado para recorrer todos los nodos de un grafo. La estrategia consiste en partir de un vértice determinado y a partir de allí, cuando se visita un nuevo vértice, explorar cada camino que salga de él. Es decir, se va tan lejos como sea posible a lo largo de cada rama antes de retroceder.
Cita: Árboles de DFS, puentes y puntos de articulación | Aprende programación competitiva. (s. f.). https://aprende.olimpiada-informatica.org/dfs-tree
ejemplo:
5.2 Investigar que el Recorrido BFS sobre grafos y un ejemplo
