Viajes
El día de hoy estaba trabajando en diversas cosas y salió que quise hacer un grafo. El grafo es el siguiente:
Con la siguiente información:
[math]V={M,L,T,G,S,A}[/math]
[math]E={(M,T),(M,G),(M,L),(M,S),(L,G),(L,A),(G,T),(A,S),(G,S)}[/math]
Y los siguientes pesos:
MT={807,320}
ML={433,175}
MS={417,200}
LA={126,107}
LG={245,207}
GT={227,200}
GS={357,254}
MG={580,236}
AS={168,140}
Basado en estos pesos, las condiciones especificadas son las siguientes:
- Hay que pasar por los nodos {T,L,S}.
- Se debe comenzar en M y terminar en S.
- El costo debe ser mínimo.
La matriz de adyacencia es la siguiente:
[math]begin{pmatrix} & M & L & T & G & A & S\ M & 0 & 433,175 & 807,320 & 580,236 & 0 & 417,200\ L & 433,175 & 0 & 0 & 245,207 & 126,107 & 0\ T & 807,320 & 0 & 0 & 227,200 & 0 & 0\ G & 580,236 & 245,207 & 227,200 & 0 & 0 & 357,254\ A & 0 & 126,107 & 0 & 0 & 0 & 168,140\ S & 417,200 & 0 & 0 357,254 & 168,140 & 0 end{pmatrix}[/math]
De la matriz podemos notar que las opciones son reducidas, que se conforman de la siguiente manera:
MTGLAS=(1573,974)
MLGTGS=(1483,1036)
MGTGLAS=(1573,1090)
En este caso en específico consideramos que la mejor opción es MTGLAS.