Parcial 3

1. Identificar los lados y vértices del siguiente grafo no dirigido:

Solución:

Lados: {L1, L2, L3, L4}

Vértice: {A, B, C, D} 

2. Represente un grafo dirigido y diga la diferencia con el grafo del numeral 1

Solución:

Lados: {1, 2, 3, 4}

Vértice: {A, B, C, D} 

Diferencias: Un grafo dirigido es aquel en el que los arcos tienen un único sentido. Los arcos de un grafo dirigido se representan gráficamente con flechas. Un grafo no dirigido es un grafo donde los arcos conectan a los nodos en ambos sentidos.

3. Hallar el número máximo de lados en los grafos de los ejercicios 1 y 2 y demostrarlo mediante la fórmula

 Solución:

 Formula(No dirigido): n(n-1)/2 -> 4(4-1)/2 = 6

 Formula(Dirigido): n(n-1) -> 4(4-1) = 12

4· Hallar la representaciones de matriz de adyacencia y matriz de incidencia para el grafo problema 1

Para representar como matriz de incidencia se deben numerar los lados de la siguiente manera en el grafo: (la numeración es de forma aleatoria)

Y la matriz de incidencia seria: 

5. Representar el grafo dirigido del ejercicio propuesto dos como una lista ligada de adyacencia:

Solución:

6· Realizar el recorrido DFS sobre grafos representado como matriz de incidencia: Debe recorrer la matriz de incidencia para determinar, por cual vértice realizo el recorrido. Después debe llamar recursivamente a dfs con el siguiente lado del grafo y así de manera sucesiva.