Joseph
B. Kruskal (1928-2010)
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 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).
FAMILIA
Joseph era hermano del matemático y estadístico William Kruskal
(autor de la Prueba de Kruskal-Wallis),
y del matemático y físico Martin Kruskal (autor de las coordenadas de Kruskal-Szekeres).
FUENTE.
AUTOR: Wikipedia
FECHA: 18 de Septiembre de 2012
No hay comentarios:
Publicar un comentario