Prueba - Aplicaciones e Interpretación Nivel Sup. | Page 234

5 . Considere el siguiente grafo ponderado :
F
50
A
59
57
53
63
E
61 65 G
B
54
68
58
52
D
61
C
( a ) ¿ Existe un camino euleriano en el grafo anterior ? Explique su respuesta .
( b ) Escriba la matriz de adyacencia M del grafo .
( c ) A partir de lo anterior , halle el número total de caminos de longitud 4 desde D hasta A .
El algoritmo de Kruskal se utiliza para hallar el árbol de expansión mínimo de este grafo .
[ 2 ]
[ 2 ]
[ 2 ]
( d ) Utilizando el algoritmo , halle el árbol de expansión mínimo .
( e ) Escriba el peso del árbol de expansión mínimo .
La siguiente tabla muestra el peso mínimo de una ruta que conecta dos vértices cualesquiera .
[ 3 ]
[ 1 ]
A
B
C
D
E
F
G
A
-
63
111 121 109
50
53
B
63
-
52
113 126 113
65
C
111
52
-
61
115 115
58
D
121 113
61
-
54
113
68
E
109 126
115
54
-
59
61
F
50
113
115 113
59
-
57
G
53
65
58
68
61
57
-
© SE Production Limited 18 Todos los Derechos Reservados 2021