Parcial #3
- TRABAJO FINAL (50%) -
Parte #1
- Identificar los lados y vértices del siguiente grafo no dirigido:
Solución:
- Vértices: {A,B,C,D}
- Lados: {L1,L2,L3,L4}
2. Represente un grafo dirigido y diga la diferencia con el grafo del numeral 1
Solución:
Vértices: {A,B,C,D}
Lados:
- 1 = {B,A}
- 2 = {A,C}
- 3 = {C,B}
- 4 = {C,D}
Diferencias: Un grafo no dirigido es un grafo donde los lados conectan a los nodos en ambos sentidos; por el contrario, los grafos dirigidos son aquellos en donde los lados conectan a los nodos en un solo sentido.
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
Solución:
Matriz de adyacencia:
- Matriz de Incidencia:
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.
Solución:
