AlvaRuiz_Grafos

República Bolivariana de Venezuela
Universidad “Fermín Toro”
Decanato de Ingeniería
Cabudare- Edo. Lara

















Alumna:
Alva Ruiz 25178462
Ejercicios sobre Grafos
1.- Suponer elgrafo no dirigido de la siguiente figura. Mostrar:
a) El árbol de expansión de costo mínimo utilizando el algoritmo de Prim (Valor 5%).
b) El árbol de expansión de costo mínimo utilizandoel algoritmo de Kruskal. ¿Son iguales las soluciones obtenidas en ambos algoritmos? En caso contrario, ¿son válidas las distintas soluciones? ¿Por qué? (Valor 5%)

a) Con el algoritmo deprim

b) Con el algoritmo de kruskal

¿Son iguales las soluciones obtenidas en ambos algoritmos?
Si son iguales

En caso contrario, ¿son válidas las distintas soluciones? ¿Por qué?
Si serianvalidas siempre y cuando tenga el mismo peso de costo



2.- Utilizar el algoritmo de Dijkstra para encontrar los caminos más cortos que van desde el nodo a hasta los restantes nodos, en elsiguiente grafo dirigido. Mostrar los valores S, D y P para todos los pasos de ejecución del algoritmo.



Llegar a d
vertices
Pas01
Pas02
Pas03
Pas04
Pas05
Pas06
A
(0,a)
*
*
*
*
*
B
(3,a)(3,a)
*
*
*
*
C
+
(4,b)
(4,b)
*
*
*
D
(6,a)
+
(5,f)
(5,f)
*
*
E
+
+
+
*
*
*
F
(5,a)
(4,b)
(4,b)
*
*
*

Llegar b
vertices
Pas01
Pas02
Pas03
Pas04
Pas05
Pas06
A
(0,a)
*
*
*
*
*
B
(3,a)
(3,a)
*
**
*
C
+
*
*
*
*
*
D
(6,a)
*
*
*
*
*
E
+
*
*
*
*
*
F
(5,a)
*
*
*
*
*

Llegar a f
vertices
Pas01
Pas02
Pas03
Pas04
Pas05
Pas06
A
(0,a)
*
*
*
*
*
B
(3,a)
(3,a)
*
*
*
*
C
+
(4,c)
*
*
*
*
D(6,a)
+
*
*
*
*
E
+
+
+
+
+
+
F
(5,a)
(4,f)
(4,f)
*
*
*



Llegar a c
vertices
Pas01
Pas02
Pas03
Pas04
Pas05
Pas06
A
(0,a)
*
*
*
*
*
B
(3,a)
(3,a)
*
*
*
*
C
+
(4,c)
(4,c)
*
*
*
D
(6,a)
+
*
*
*
*E
+
+
+
+
+
+
F
(5,a)
(4,f)
*
*
*
*

No se puede aplicar dijkstra a este grafo dirigido cuando tenemos como destino el vértice e debido a que no tiene una arista que llegue hacia el