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:

1. · Explique la diferencia entre los dos grafos anteriores

La diferencia es que un grafo es definido y otro no definido, donde el grafo definido, teniendo menos vértices que el grafo definido, tiene más aristas. 

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.

Para que exista una trayectoria en el grafo dirigido de D hasta A, se debe crear una traza que vaya desde D hasta A . 

c. Diga cual es el número máximo de lados que pueden tener los dos grafos

Grafo no dirigido es n*(n-1)/2

N = 6 6*(6-1)/2 6*5/2 30/2

Máximo de lados grafo no dirigido: 15

Grafo dirigido es n*(n-1)

N=5 5*(5-1) 5*4

Máximo de lados grafo dirigido: 20

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

https://sistemasuniremingtonb.webnode.com.co/Creado con WebnodeEs

Documento que pueden utilizar como base para resolver varios puntos del Taller grafo