Algoritmos de Grafos: Prim, Dijkstra, Kruskal y Fleury

Clase 39 de 40 • Curso de Matemáticas Discretas

Clase anteriorSiguiente clase

Ejemplo:

Encuentre el árbol de expansión mínima y su coste total utilizando el algoritmo de Prim:

Captura de pantalla 2018-07-24 a la(s) 15.09.34.png

Solución

Captura de pantalla 2018-07-24 a la(s) 15.09.59.png

Ejercicios de práctica:

Después de mirar el ejemplo, resuelve los siguientes ejercicios y comenta en el sistema de discusiones tus respuestas.

1. Encuentre el camino de menor coste para ir desde a hasta e utilizando el algoritmo de Dijkstra. ¿Cuál es el coste?

Captura de pantalla 2018-07-24 a la(s) 15.10.49.png

2. Encuentre el árbol de expansión mínima utilizando el algoritmo de kruskal:

Captura de pantalla 2018-07-24 a la(s) 15.11.20.png

3. Encuentre un ciclo Euleliano utilizando el algoritmo de Fleury:

Captura de pantalla 2018-07-24 a la(s) 15.11.51.png

4. Encuentre el flujo Máximo desde a hasta d:

Captura de pantalla 2018-07-24 a la(s) 15.12.36.png