( d ) Escriba la matriz de adyacencia M del grafo .
( e ) A partir de lo anterior , halle el número total de caminatas de una longitud máxima de 3 a partir de C a E .
La siguiente tabla muestra el peso mínimo de una ruta que conecta dos vértices cualquiera .
[ 3 ]
[ 2 ]
( f ) Escriba el valor de
( i ) p ;
|
O |
A |
B |
C |
D |
E |
O |
- |
30 |
36,1 |
p |
36,1 |
30 |
A |
30 |
- |
20 |
30 |
34,1 |
q |
B |
36,1 |
20 |
- |
10 |
14,1 34,1 |
C |
p |
30 |
10 |
- |
10 |
30 |
D |
36,1 34,1 14,1 |
10 |
- |
20 |
E |
30 |
q |
34,1 |
30 |
20 |
- |
( ii ) q . [ 2 ]
( g ) Utilizando el algoritmo del vecino más próximo , comenzando y terminando en O , halle el límite superior de la distancia total de un ciclo que pasa por las seis posiciones de espantapájaros .
[ 3 ]
( h ) Utilizando el algoritmo del vértice eliminado , borrando el vértice C , halle el límite inferior de la distancia total de un ciclo que pasa por las seis posiciones de espantapájaros , dando la respuesta correcta con un decimal .
[ 4 ]
© SE Production Limited 4 Todos los Derechos Reservados 2021