Algoritmo De Kruskal
Páginas: 3 (569 palabras)
Publicado: 7 de diciembre de 2012
rEL ALGORITMO DE KRUZKAL
PRESENTADO POR :
JUAN PABLO GÓMEZ
AL PROFESOR :
JULIO HERNANDO VARGAS
CURSO DE MATEMÁTICAS AVANZADAS
MAESTRÍA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓNSEPTIEMBRE DEL 2012
UNIVERSIDAD TECNOLÓGICA DE PEREIRA
El problema del árbol de mínima expansión
Una aplicación típica de este problema es el diseño de las redes telefónicas. Una
empresa condiferentes 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 de diferentes costes por conectar cada par deoficinas. ¿Cómo conectar
entonces las oficinas al mínimo coste total?
La formulación del árbol de mínima expansión MST (Minimal Spanning Tree)
también ha sido aplicada para hallar soluciones endiversas áreas como el diseño
de las redes de transporte, diseño de redes de comunicaciones, TV por cable,
internet , etc. En todos estos problemas tenemos una serie de nodos con posibles
unionesentre ellos a distintos costes y el objetivo es unir todos los nodos a coste
mínimo
Un árbol de expansión de un grafo es un subgrafo que contiene todos sus vértices
o nodos. Un grafo puede tenermúltiples árboles por esto existen algoritmos para
encontrar el árbol de coste mínimo.Este problema fue resuelto por Dijkstra (1959),
Kruskal (1956) y Prim (1957). A lo largo de la historia se ha hechoun gran
esfuerzo para encontrar un algoritmo rápido para este problema.
El algoritmo de Kruskal
Kruskal es un algoritmo voraz en la teoría de grafos,que encuentro el mínimo árbol
de expansiónentre un árbol con pesos. Es decir, el algoritmo busca subconjunto
de aristas, que formando un árbol, incluye todos los vértices donde el valor total de
las aristas del árbol es el mínimo. Estealgoritmo fue publicado por primera vez
en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue
escrito porJoseph Kruskal.
El algoritmo Funciona de la siguiente manera:
...
PRESENTADO POR :
JUAN PABLO GÓMEZ
AL PROFESOR :
JULIO HERNANDO VARGAS
CURSO DE MATEMÁTICAS AVANZADAS
MAESTRÍA DE INGENIERÍA DE SISTEMAS Y COMPUTACIÓNSEPTIEMBRE DEL 2012
UNIVERSIDAD TECNOLÓGICA DE PEREIRA
El problema del árbol de mínima expansión
Una aplicación típica de este problema es el diseño de las redes telefónicas. Una
empresa condiferentes 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 de diferentes costes por conectar cada par deoficinas. ¿Cómo conectar
entonces las oficinas al mínimo coste total?
La formulación del árbol de mínima expansión MST (Minimal Spanning Tree)
también ha sido aplicada para hallar soluciones endiversas áreas como el diseño
de las redes de transporte, diseño de redes de comunicaciones, TV por cable,
internet , etc. En todos estos problemas tenemos una serie de nodos con posibles
unionesentre ellos a distintos costes y el objetivo es unir todos los nodos a coste
mínimo
Un árbol de expansión de un grafo es un subgrafo que contiene todos sus vértices
o nodos. Un grafo puede tenermúltiples árboles por esto existen algoritmos para
encontrar el árbol de coste mínimo.Este problema fue resuelto por Dijkstra (1959),
Kruskal (1956) y Prim (1957). A lo largo de la historia se ha hechoun gran
esfuerzo para encontrar un algoritmo rápido para este problema.
El algoritmo de Kruskal
Kruskal es un algoritmo voraz en la teoría de grafos,que encuentro el mínimo árbol
de expansiónentre un árbol con pesos. Es decir, el algoritmo busca subconjunto
de aristas, que formando un árbol, incluye todos los vértices donde el valor total de
las aristas del árbol es el mínimo. Estealgoritmo fue publicado por primera vez
en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue
escrito porJoseph Kruskal.
El algoritmo Funciona de la siguiente manera:
...
Leer documento completo
Regístrate para leer el documento completo.