ALGORITMO DE KRUSKAL
Páginas: 2 (471 palabras)
Publicado: 7 de noviembre de 2013
ALGORITMO DE KRUSKAL
Antes de explicar directamente el algoritmo de Kruskal, comenzaré dando conceptos sobre que es un árbol de expansión mínima para entender mejor el problema.
Árbol deExpansión
Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las aristas de G. Al ser creado un árbol no existiránciclos, además debe existir una ruta entre cada par de vértices.
Un grafo puede tener muchos árboles de expansión, veamos un ejemplo con el siguiente grafo:
En la imagen anterior se puedeobservar que el grafo dado posee 3 árboles de expansión, dichos arboles cumplen con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.
Árbol de Expansión MínimaDado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemploanterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:
De la imagen anterior el árbol de expansión mínima sería el primer árbol de expansión cuyo peso totales 6. El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los más conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).
ALGORITMO DEKRUSKAL
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo. 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 del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo.
Como trabaja:
Primeramente ordenaremoslas aristas del grafo por su peso de menor a mayor. Mediante la técnica greedy Kruskal intentara unir cada arista siempre y cuando no se forme un ciclo, ello se realizará mediante Union-Find. Como...
Antes de explicar directamente el algoritmo de Kruskal, comenzaré dando conceptos sobre que es un árbol de expansión mínima para entender mejor el problema.
Árbol deExpansión
Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las aristas de G. Al ser creado un árbol no existiránciclos, además debe existir una ruta entre cada par de vértices.
Un grafo puede tener muchos árboles de expansión, veamos un ejemplo con el siguiente grafo:
En la imagen anterior se puedeobservar que el grafo dado posee 3 árboles de expansión, dichos arboles cumplen con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.
Árbol de Expansión MínimaDado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Al ejemploanterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:
De la imagen anterior el árbol de expansión mínima sería el primer árbol de expansión cuyo peso totales 6. El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los más conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).
ALGORITMO DEKRUSKAL
El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo. 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 del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo.
Como trabaja:
Primeramente ordenaremoslas aristas del grafo por su peso de menor a mayor. Mediante la técnica greedy Kruskal intentara unir cada arista siempre y cuando no se forme un ciclo, ello se realizará mediante Union-Find. Como...
Leer documento completo
Regístrate para leer el documento completo.