Taller de grafos
Introduce un texto aquí...
1. Para los siguientes grafos
Conteste las siguientes preguntas:
1. · Explique la diferencia entre los dos grafos anteriores
Respuesta: La diferencia es que un grafo es definido y otro no definido, donde el grafo definido, teniendo menos vértices que el grafo definido.
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.
Respuesta: Para que exista una trayectoria en el grafo dirigido de D hasta A, se debe crear una traza que vaya desde D hasta A <D,A>.
c. Diga cual es el número máximo de lados que pueden tener los dos grafos
Respuesta: en el caso del grafo no dirigido es hay que aplicar la formula n*(n-1)/2 N = 6
6*(6-1)/2
6*5/2
30/2 lo que da como resultado 15 como maximo de lados.
Para el caso del grafo dirigido se aplica la formula n*(n-1) N=5
5*(5-1)
5*4 lo que da como resultado 20 como maximo de lados.
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.
La gráfica sin trayectoria cuenta con 14 ciclos
(A,B) , (A,C), (B,A),(C,A),(C,D),(C,E),(D,C),(E,C)
CICLO 1
(A,B) (B,C) (C,A)
CICLO 2
(A,C)(C,D) (D,F) (F,E), (E,C) (C,B) (B,A)
CICLO 3
(F,D) (D,C) (C,E) (E,F)
I. Hallar el grado para cada uno de los vértices de cada grafo
Para el grafo no dirigido:
A es grado 2
B es grado 2
C es grado 4
D es grado 2
E es grado 2
F es grado 2
Para el grafo dirigido:
A entra: 0 salen: 2
B entra : 1 salen : 3
C entra : 1 salen : 1
D entra : 3 salen : 1
E entra : 3 salen : 1
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.
Respuesta: para los puntos 2 y 3 descargue el siguiente archivo.
4. Defina con sus palabras:
a) Adyacencia: La adyacencia es un concepto matemático que se refiere a la relación entre dos vértices en un grafo. Dos vértices son adyacentes si están conectados por una arista. Esto significa que hay un camino directo entre ellos.
b) Incidencia: La incidencia es un concepto relacionado con la adyacencia. Se refiere a la relación entre un vértice y una arista. Dos vértices son adyacentes si están conectados por una arista. Esto significa que hay un camino directo entre ellos. La incidencia entre un vértice y una arista se refiere a la cantidad de aristas que conectan al vértice con la arista. Por ejemplo, un vértice puede estar conectado a una arista de manera directa, o se puede decir que la incidencia entre el vértice y la arista es 1. Si hay dos aristas conectadas al vértice, la incidencia entre el vértice y la arista es 2.
c) Grado de un grafo: El grado de un grafo se refiere al número de aristas conectadas a un vértice. Esto significa que, si hay dos aristas conectadas a un vértice, el grado del vértice es 2. El grado de un grafo es la suma de los grados de todos los vértices que forman parte del grafo. Por lo tanto, el grado de un grafo es una forma de medir el número de aristas en el grafo.
d) Trayectoria: Una trayectoria es la secuencia de vértices que uno visita en un grafo para llegar desde un vértice inicial hasta un vértice final. Esto implica que hay un orden en los vértices que se visitan para llegar de uno a otro. Por lo tanto, una trayectoria en un grafo es una secuencia de aristas que se unen para formar un camino.
e) Trayectoria simple: Una trayectoria simple es una trayectoria en la que no se visita ningún vértice más de una vez.
f) Ciclo: Un ciclo en un grafo es un camino entre dos nodos en el que el primer y el último nodo son el mismo. Esto significa que el camino comienza y termina en el mismo nodo. Los ciclos a menudo se representan como una forma cerrada y son los caminos más simples en un grafo. Un grafo puede tener ciclos de longitud diferente, desde un ciclo de 3 nodos hasta ciclos de longitud infinita.
g) Grafo conectado: Un grafo conectado es un grafo en el que hay al menos un camino entre cualquier par de vértices. Esto significa que hay al menos una secuencia de aristas conectadas entre cualquier par de vértices.
h) Grafo fuertemente conectado :Un grafo fuertemente conectado, por otro lado, es un grafo en el que hay al menos un camino de ida y vuelta entre cualquier par de vértices. Esto significa que hay al menos una secuencia de aristas conectadas entre cualquier par de vértices, que se pueden seguir en ambos sentidos. Esta característica garantiza que todos los vértices en el grafo estén estrechamente conectados entre sí, lo que significa que cada vértice se puede alcanzar desde cualquier otro vértice.
5. Investigar los Recorridos sobre grafos:
5.1 Investigar que el Recorrido DFS sobre grafos y un ejemplo
Es un algoritmo de búsqueda de grafos que se utiliza para recorrer todos los nodos de un grafo. Funciona explorando primero un nodo y luego sus vecinos, luego sus vecinos, y así sucesivamente. El algoritmo sigue cada rama hasta encontrar un nodo sin vecinos o un nodo que ya haya sido visitado antes, y luego retrocede y sigue la siguiente rama.
Un ejemplo aplicable de recorrido DFS es encontrar el camino más corto entre dos nodos en un grafo. El algoritmo comenzará desde el nodo inicial y seguirá los caminos hacia los nodos adyacentes hasta que llegue al nodo objetivo. El camino más corto se encontrará una vez que se haya recorrido todos los nodos del grafo.
5.2 Investigar que el Recorrido BFS sobre grafos y un ejemplo:
Es un algoritmo para recorrer grafos, en el cual se recorren todos los nodos de un grafo a partir de un nodo inicial. El algoritmo se basa en explicar los nodos a partir del nodo inicial, uno a uno, empezando desde los vecinos del nodo inicial e iterando la explicación al siguiente nivel de vecinos uno a uno. Un ejemplo aplicable es el recorrido de una red social. Supongamos que queremos recorrer los amigos de un usuario, en este caso el nodo inicial sería el usuario. El algoritmo recorrería primero todos sus amigos directos para luego recorrer los amigos de sus amigos, y así sucesivamente.