Árbol De Expansión mínima

Árbol de mínima expansión

El algoritmo de mínima expansión enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicación característica es la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre las poblaciones puede pasar por uno o más poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados, resultado que se obtiene implementando el algoritmo de árbol de expansión mínima.

Los pasos del procedimiento son como siguen:

Sea:

N = {1, 2, …. n} el conjunto de nodos de la red. K C =Conjunto de nodos conectados de forma permanente en la iteración “k”

Ck =Conjunto de nodos que aún se deben conectar de forma permanente en la iteración “k”.

Paso 0. Se inicia con el conjunto 0 C =y C0=N. Es decir, todos los nodos están sin conectar en la iteración cero.

Paso 1. Sea “i” cualquier nodo de la red, de forma tal que en la primera iteración C1={i} al hacer esto se debe descontar dicho nodo de los no conectados C1=N-{i}. Pasar a la siguiente iteración k = 2.

Paso k. Seleccionar un nodo “j” Ck1 (que pertenece al conjunto de los nodos que aún se deben conectar de la iteración anterior); de forma tal que produzca el arco más corto a un nodo conectado del conjunto. Ck-1 y sacarlo del conjunto Ck1.

O colocado en términos sencillos, el paso “k” se refiere a:

Ck=Ck-1 + {j}, Ck =Ck1 -{j}

Cuando Ck=N y Ck =el proceso se detiene.

...