red, de manera que se minimiza la longitud total.
La aplicación de este tipo de problemas de optimización se ubica, sobre todo, en las redes de comunicación eléctrica, telefónica,
telegráfica, carretera, ferroviaria, aérea, marítima; etc. Donde los nodos representan puntos de consumo eléctrico,
teléfonos, aeropuertos; etc. Y los arcos podrían ser líneas de alta tensión, vías de ferrocarril, rutas aéreas; etc.
Si n = número de nodos, entonces la solución óptima debe incluir n-1 arcos.
El Algoritmo de Kruskal para resolver este problema es muy sencillo. Los pasos son los siguientes:
1. Comenzar en forma arbitraria en cualquier nodo y conectarlo con el nodo más próximo (menos distante).
2. Identificar el nodo no conectado que este más cerca de alguno de los nodos conectados. Deshacer los empates de
forma arbitraria. Agregar este nodo al conjunto de nodos conectados. Repetir este paso hasta que se hayan conectado
todos los nodos.
Se utiliza para transporte, las duraciones de ahora son distancias, las distancias pueden ir de ida o de regreso, por esta
razón ya no tienen dirección. El objetivo es conectar a todos los nodos con la mínima distancia.
No hay comentarios.:
Publicar un comentario