Joer

Republica bolivariana de Venezuela
Ministerio del poder popular para la Educación Superior
Misión sucre
Morón- Estado Carabobo
Sistema

Integrantes:
Margareth Ramos
Eduarw CarielWilkins Aldama
Carlos Mangles
Erika López
Prof:
Marielys Gutierrez
28 de abril de 2012

Algoritmo de Kruskal
Definición
Es un algoritmo de la teoría de grafos para encontrar un árbolrecubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas es mínimo.margareth
Joseph Kruskal
Fue un investigador que 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. Elobjetivo 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. wilkinsFuncionamiento
* Se parte colocando todos los vértices del grafo separados, y se decide partir por un vértice de inicio.
* Dado el vértice de inicio, armamos una lista de todas las aristas queposee, ordenadas es forma decreciente según su ponderación.
* Tomamos la de menor coste, retiramos de la lista a la arista utilizada y agregamos las nuevas aristas que nos proporciona el nuevo vértice.* Así sucesivamente, generando subgrafos conexos hasta llegar a conectar todos los subgrafos conexos formando un árbol de cubrimiento de costo minimo. eduarw
Regla principal.
El objetivoprincipal del algoritmo de kruskal es crear un árbol a partir de arcos sucesivamente seleccionados de mínimo peso pero que estos no formen ningún ciclo.
La manera formal de resolver un problema esencontrar la trayectoria mas corta para visitar cada nodo al menos una vez. carlos

Ejemplo paso a paso:

Grafo Original
Los numeros de las aristas indican su peso.

AD y CE son las aristas con m...