Grafos

Algoritmo de Kruskal

Grafos forma parte de un proyecto de investigación y desarrollo de aplicaciones informáticas de diseño modular orientadas hacia la docencia, investigación y labores profesionales de Ingeniería de Organización. Grafos contiene entre otras una DLL con el Algoritmo de Kruskal:

Joseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de coste total mínimo (minimum spanning tree - MST) también llamado árbol recubridor euclídeo mínimo. Este problema es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.

El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.

La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.

La formulación del MST también ha sido aplicada para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros).

Otra aplicación menos obvia es que el árbol de coste total mínimo puede ser usado como solución aproximada al problema del viajante de comercio (traveling salesman problem), recuerde que encontrar la solución óptima a este problema es NP-Hard. La manera formal de definir este problema es encontrar la trayectoria más corta para visitar cada punto al menos una vez. Nótese que si se visitan todos los puntos exactamente una vez, lo que se tiene es un tipo especial de árbol. En el ejemplo anterior, 12 de los 16 árboles son trayectorias de este tipo. Si se tiene una trayectoria que visita algunos vértices o nodos más de una vez, siempre se puede soltar algunos nodos del árbol. En general el peso del árbol total mínimo es menor que el del viajante de comercio, debido a que su minimización se realiza sobre un conjunto estrictamente mayor. Existen diferentes algoritmos y maneras de usar el árbol de coste total mínimo para encontrar la solución al problema del viajante de comercio (con resultados cercanos al óptimo).

 

Algoritmo de Kruskal (árbol de coste total mínimo)

Dado un grafo G con nodos conectados por arcos con peso (coste o longitud): el peso o coste total de un árbol será la suma de pesos de sus arcos. Obviamente, árboles diferentes tendrán un coste diferente. El problema es entonces ¿cómo encontrar el árbol de coste total mínimo?

Una manera de encontrar la solución al problema del árbol de coste total mínimo, es la enumeración completa. Aunque esta forma de resolución es eficaz, no se puede considerar un algoritmo, y además no es nada eficiente.

Este problema fue resuelto independientemente por Dijkstra (1959), Kruskal (1956) y Prim (1957) y la existencia de un algoritmo polinomial (que todos ellos demostraron) es una grata sorpresa, debido a que un grafo con N vértices puede llegar a contener NN-2 subárboles. A lo largo de la historia se ha hecho un gran esfuerzo para encontrar un algoritmo rápido para este problema. El algoritmo de Kruskal es uno de los más fáciles de entender y probablemente el mejor para resolver problemas a mano.

El algoritmo se basa en una propiedad clave de los árboles que permite estar seguros de si un arco debe pertenecer al árbol o no, y usar esta propiedad para seleccionar cada arco. Nótese en el algoritmo, que siempre que se añade un arco (u,v), éste será siempre la conexión más corta (menor coste) alcanzable desde el nodo u al resto del grafo G. Así que por definición éste deberá ser parte del árbol.

Este algoritmo es de tipo greedy, ya que a cada paso, éste selecciona el arco más barato y lo añade al subgrafo. Este tipo de algoritmos pueden no funcionar para resolver otro tipo de problemas, por ejemplo para encontrar la ruta más corta entre los nodos a y b.

Para simplificar, se asumirán que existe un único árbol de coste total mínimo, aunque en muchos problemas puede existir más de una solución optima de igual valor total mínimo.

A continuación se muestra el pseudocódigo del Algoritmo:

Kruskal (G)

E(1)=0, E(2)= todos los Arcos del grafo G
      Mientras E(1) contenga menos de n-1 arcos y E(2)=0 do
         De los arcos de E(2) seleccionar el de menor coste -->e(ij)
         E(2)= E(2) - {e(ij)}
              Si V(i), V(j) no están en el mismo árbol entonces
                 juntar los árboles de  V(i) y de V(j) en uno sólo
              end Si
      end do
Fin del algoritmo
 

Este problema puede ser resuelto por diferentes algoritmos, e incluso en la actualidad sigue siendo tema de interés en investigaciones. Es interesante la lectura de los siguientes algoritmos (que resuelven este problema para diferentes supuestos), aunque son bastante complejos y probablemente no requiera utilizarlos a no ser que trabaje con grafos de grandes dimensiones:

Karger, Klein, and Tarjan, "A randomized linear-time algorithm to find minimum spanning trees", J. ACM, vol. 42, 1995, pp. 321-328.

Fredman and Willard, "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719-725.

Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109-122.

Fuente: A. Rodríguez

más información

- Kruskal (Bell Labs)
- Publicaciones de Kruskal (Bell Labs)
- Historia de la investigación matemática en Bell Labs
- Minimum Spanning Tree
- Otakar Boruvka on Minimum Spanning Tree Problem (translation of the both 1926 papers, comments, history) (2000) Jaroslav Nesetril, Eva Milková, Helena Nesetrilová
- J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society, 7:48-50, 1956.
 

Creative Commons License Alejandro Rodríguez Villalobos