Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
El nodo no conectado más cercano a O, A o B es el nodo E (más cercano a B). Se conecta el nodo E
con el nodo B.
El nodo no conectado más cercano a O, A, B, C o E es el nodo D (más cercano a E). Se conecta el
nodo D con el nodo E.
El único nodo no conectado es T. Está más cerca del nodo D. Se conecta el nodo T con el nodo D.
Todos los nodos han quedado conectados, por lo que ésta solución (óptima) que se buscaba. La
longitud total de las ramas es 14 millas.
Aunque con este procedimiento a primera vista puede parecer que la elección del nodo inicial
afectará la solución final – y la longitud total de las ligaduras -, en realidad no es así. Se sugiere verificar
este hecho en el caso del ejemplo, mediante otra aplicación del algoritmo, pero con un nodo distinto de O.
El tercer problema al que se enfrenta el administrador de Seervada Park durante la temporada pico
es determinar la ruta de algunos viajes de tranvía desde la entrada del parque (estación O) hasta el mirador
(estación T), de manera que el número de viajes diarios sea el máximo (cada camioneta debe regresar por la
misma ruta que tomó de ida, por lo que el análisis se harpa sólo sobre los viajes de ida). Para evitar
perturbaciones innecesarias a la ecología y a la vida silvestre se impusieron límites superiores estrictos
sobre el número de viajes de salida permitidos hacia el mirador para cada camino individual en la dirección
48