Grafos

Guia Ejercicios Grafos
1. Dado un grafo dirigido, constituido por los siguientes arcos:
Arco | Punto de Origen | Punto de Llegada |
1-2 | 1 | 2 |
2-3 |2 | 3 |
3-1 | 3 | 1 |
1-4 | 1 | 4 |
5-4 | 5 | 4 |
5-6 | 5 | 6 |
6-7 | 6 | 7 |
7-5 | 7 | 5 |
6-10 | 6 | 10 |
10-9 | 10 | 9 |
9-8 | 9 | 8 |
8-10| 8 | 10 |

Aplicar el algoritmo de DFS para hallar las componentes fuertemente conexas. Se asume que se parte del vértice 1.

2. Dado el siguiente grafo nodirigido, compuesto por los siguientes arcos con sus respectivos pesos:

Arco | Peso |
1-2 | 2 |
1-7 | 1 |
2-3 | 5 |
2-4 | 1 |
3-4 | 1 |
3-5 | 3 |4-5 | 4 |
7-8 | 1 |
7-9 | 3 |
8-9 | 5 |
8-10 | 3 |
9-10 | 10 |
5-10 | 1 |
5-6 | 2 |
10-6 | 2 |

Aplicar el algoritmo de Dijkstra para hallar laruta más corta desde el vértice 1 hacia el resto de los vértices.

3. Dado el siguiente grafo no dirigido, compuesto por los siguientes arcos:
Arco |
1-2|
1-3 |
2-3 |
2-4 |
3-4 |
4-5 |
4-6 |
5-6 |
5-10 |
6-7 |
10-9 |
7-8 |
9-8 |
6-9 |
5-8 |
1-11 |
11-13 |
11-12 |
12-13 |
12-14|
13-14 |

Aplicar el algoritmo de DFS para hallar los puntos de articulación partiendo del nodo 1.

4. Dado el siguiente grafo no dirigido, compuestopor los siguientes arcos y sus respectivos pesos:

Arco | Peso |
1-2 | 3 |
1-6 | 3 |
2-7 | 7 |
7-6 | 1 |
2-3 | 3 |
6-5 | 2 |
7-8 | 2 |
3-8 | 1 |8-5 | 5 |
3-4 | 7 |
4-5 | 4 |

Aplicar algoritmo KRUSKAL para hallar el árbol máximo Cobertor y el algoritmo de PRIM para hallar el árbol mínimo cobertor.