Arbol De Expancion Minima

Arbol de expansión minima

• Este problema sirge cuando todos los nodos de una red debne conectar entre ellos, sin formar un loop

• El arbol de expansión minima es apropiado para problemas en los cuales la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantaneo

ÁRBOL DE EXPANSIÓN MÍNIMA: ALGORITMO DE KRUSKAL

Publicado el abril 19, 2012| 5 comentarios

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 de Expansió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án ciclos, además debe existir una ruta entre cada par de vértices.

Un grafo puede tener muchos arboles de expansión, veamos un ejemplo con el siguiente grafo:

En la imagen anterior se puede observar que el grafo dado posee 3 arboles 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ínima

Dado 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 ejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo peso total es 6.

El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).

Algoritmo de Kruskal

Para poder comprender el algoritmo de kruskal será necesario revisar primer el tutorial de Union-Find.

Como trabaja:

Primeramente ordenaremos las 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 hemos ordenado las aristas por peso comenzaremos con la arista de menor peso, si los vértices que contienen dicha arista no están en la misma componente conexa entonces los unimos para formar una sola componente mediante Union(x , y), para revisar si están o no en la misma componente conexa usamos la función SameComponent(x , y) al hacer esto estamos evitando que se creen ciclos y que la arista que une dos vértices siempre sea la mínima posible.

Algoritmo en Pseudocódigo

1 método Kruskal(Grafo):

2 inicializamos MST como vacío

3 inicializamos estructura unión-find

4 ordenamos las aristas del grafo por peso de menor a mayor.

5 para cada arista e que une los vértices u y v

6 si u y v no están en la misma componente

7 agregamos la arista e al MST

8 realizamos la unión de las componentes de u y v

Ejemplo y código paso a paso

Tengamos el siguiente grafo no dirigido:

Primeramente usaremos el método MakeSet de unión-find para inicializar cada componente, obteniendo las siguientes componentes conexas iniciales:

Ahora el siguiente paso es ordenar las aristas del grafo en orden ascendente:

Lo siguiente será recorrer todas las aristas ya ordenadas y verificar si sus vértices están o no en la misma componente.

La primera arista a verificar es la que une a los vértices 8 y 7, verificamos si están en la misma componente, para ello hacemos Find(8)

...