El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.
Funciona de
la siguiente manera:
§ se crea un conjunto C que contenga a todas las aristas del
grafo
§ mientras C es no
vacío
§ eliminar una arista de peso mínimo de C
§ si esa arista conecta dos árboles diferentes se añade al bosque,
combinando los dos árboles en un solo árbol
§ en caso contrario, se desecha la arista
Al acabar
el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de
expansión mínimo del grafo.
Este
algoritmo fue publicado por primera vez en Proceedings
of the American Mathematical Society, pp. 48–50 en 1956, y fue escrito por Joseph Kruskal.
Referencias
Algoritmo
de Kruskal [en línea] [Fecha de consulta: 16, Septiembre 2012]. Disponible en <http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal>
Joseph Kruskal
Joseph B. Kruskal (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010)1 fue un matemático y estadístico estadounidense.
Investigador del Math Center (Bell-Labs), en 1956 descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo, el cual 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, el cual es NP-completo. 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 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).
Referencias
Biography Joseph Kruskal [en línea] [Fecha de consulta: 16, Septiembre 2012]. Disponible en <http://es.wikipedia.org/wiki/Joseph_Kruskal>
Joseph Kruskal
. [Imágen]. [Fecha de consulta: 16, Septiembre
2012]. Disponible en: < http://es.wikipedia.org/wiki/biography_Joseph_Kruskal>
No hay comentarios:
Publicar un comentario