JOSEPH
B. KRUSKAL
Joseph B. Kruskal (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010) 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 arcossucesivamente
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)
Joseph
B. Kruskal [en línea] Recuperado de: http://es.wikipedia.org/wiki/Joseph_Kruskal
Consulta: Septiembre 16, 2012
Joseph
B. Kruskal [en línea] Recuperada de: http://tinyurl.com/chl7o3t
Consulta:
Septiembre 16, 2012
