Expansion Minima
Páginas: 4 (811 palabras)
Publicado: 26 de septiembre de 2012
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 spanningtree - MST) también llamado árbol recubridor euclíde o mínimo.
Este problema es un problema típico de optimizacióncombinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientrasestudiaba lanecesidad de electrificación rural en el sur de Moravia en Checos vaquia.El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcossucesivamenteseleccionados 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 grafopuede tener múltiplesárboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionadoscon todos) tendría 16 árboles.La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa condiferentesoficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica leofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par deoficinas.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 deredes de transporte, diseño de redes detelecomunicaciones - TV por cable, sistemas distribuidos,interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos deparentesco, análisis de clusters ybú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 comosolució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...
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 spanningtree - MST) también llamado árbol recubridor euclíde o mínimo.
Este problema es un problema típico de optimizacióncombinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientrasestudiaba lanecesidad de electrificación rural en el sur de Moravia en Checos vaquia.El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcossucesivamenteseleccionados 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 grafopuede tener múltiplesárboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionadoscon todos) tendría 16 árboles.La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa condiferentesoficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica leofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par deoficinas.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 deredes de transporte, diseño de redes detelecomunicaciones - TV por cable, sistemas distribuidos,interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos deparentesco, análisis de clusters ybú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 comosolució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...
Leer documento completo
Regístrate para leer el documento completo.