6 . Considere el siguiente grafo ponderado : 32
F
E 9 19
( a ) ¿ Existe un circuito euleriano en el grafo anterior ? Explique su respuesta .
[ 2 ] El algoritmo de Prim , empezando en C , se utiliza para encontrar el árbol de expansión mínimo para este grafo .
D
( b ) Indique la arista de menor peso .
( c ) Utilizando el algoritmo , halle el árbol de expansión mínimo .
( d ) Escriba el peso del árbol de expansión mínimo .
La siguiente tabla muestra el peso mínimo de un camino que conecta dos vértices cualesquiera .
[ 1 ]
[ 3 ]
[ 1 ]
|
A |
B |
C |
D |
E |
F |
G |
A |
- |
17 |
23 |
44 |
27 |
18 |
26 |
B |
17 |
- |
6 |
27 |
21 |
30 |
10 |
C |
23 |
6 |
- |
21 |
27 |
36 |
16 |
D |
44 |
27 |
21 |
- |
19 |
28 |
23 |
E |
27 |
21 |
27 |
19 |
- |
9 |
11 |
F |
18 |
30 |
36 |
28 |
9 |
- |
20 |
G |
26 |
10 |
16 |
23 |
11 |
20 |
- |
( e ) Utilizando del algoritmo del vecino más cercano , empezando y terminando en G , halle el límite superior del peso total de un ciclo , que pasa por los siete vértices .
[ 3 ]
( f ) Utilizando el algoritmo del vértice eliminado , quitando el vértice G , halle el límite inferior del peso total de un ciclo , que pasa por los siete vértices .
[ 4 ]
© SE Production Limited 22 Todos los Derechos Reservados 2021