Documentacion

2.2.2 Problema del árbol expandido mínimo.

ALGORITMO DE ÁRBOL DE EXPANSIÓN MÍNIMA
El algoritmo de árbol de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con lamínima longitud de las ramas enlazantes. Una aplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o máspoblaciones adicionales. El diseño más económico el 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 los siguientes. Sea N = {1, 2, ... , n} el conjunto de nodos de la red, y se definen:

Ck = Conjunto de nodos que se han conectado enforma permanente en la iteración k.
[pic]K= Conjunto de nodos que todavía se deben conectar en forma permanente.

Paso O. El conjunto Co =Ǿ y [pic]o = N.
Paso 1. Comenzar con cualquier nodo en elconjunto [pic]o no conectado (o "inconexo"), e igualar Cl = {i}, con lo que [pic]l = N - {i}. Igualar k = 2.
Paso general k. Seleccionar un nodo j* en el conjunto no conectado [pic]k-1 que produzca elarco más corto a un nodo, en el conjunto conectado Ck-1. Enlazar a j* en forma permanente con Ck-1 y sacarlo de [pic]k-1, esto es
Ck = Ck-1 + {j*}, [pic]k = [pic]k-1 - {j*}Si el conjunto [pic]k, de nodos no conectados es vacío, detenerse. En cualquier otro caso, igualar k = k + 1 y repetir el paso.
Ejemplo 6.2-1
Midwest TV Cable Company está en el proceso deproporcionar servicio de cable a cinco nuevas áreas habitacionales. La figura 6.4 representa los enlaces posibles de TV entre las cinco áreas. Las millas de cable se muestran en cada arco. Determine la red decable más económica.
El algoritmo comienza en el nodo 1 (cualquier otro nodo podría ser), con lo que se obtiene C1 = {1}, Cl = {2,3,4,5,6}
Las iteraciones del algoritmo se resumen en la...