ClubEnsayos.com - Ensayos de Calidad, Tareas y Monografias
Buscar

Algoritmo Krukal


Enviado por   •  19 de Diciembre de 2012  •  389 Palabras (2 Páginas)  •  396 Visitas

Página 1 de 2

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 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 de diferentes costes por conectar cada par de oficinas. ¿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 en diversas á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

uniones entre 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 tener mú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 hecho un 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ón entre 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. Este algoritmo 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:

 se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es

un árbol separado

 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.

...

Descargar como (para miembros actualizados) txt (2 Kb)
Leer 1 página más »
Disponible sólo en Clubensayos.com