Árbol de Mínima Expansión
Optimización de Topologías de Red
Teoría del Modelo
Este modelo vincula todos los nodos de una red valiéndose de la longitud mínima total de las ramas de conexión. Es una estructura estrictamente acíclica (un árbol), lo que significa que no existen bucles cerrados que generen redundancia de recursos.
Sea N = {1, 2, ..., n} el conjunto completo de nodos de la red.
Ck: Conjunto de nodos conectados de manera permanente en la iteración k.
C̄k: Conjunto de nodos que se construirán permanentemente después de la iteración k (nodos no conectados).
Algoritmo de Resolución
Establezca el conjunto inicial conectado como vacío C0 = ∅ y el conjunto no conectado con todos los nodos C̄0 = N.
Inicie con cualquier nodo i en el conjunto no conectado. Defina C1 = {i}, lo que produce C̄1 = N - {i}. Establezca el contador de iteraciones k = 2.
Seleccione un nodo j* en el conjunto no conectado C̄k-1 que produzca el arco más corto hacia cualquier nodo del conjunto ya conectado Ck-1. Vincule j* permanentemente, elimínelo de C̄k-1 y repita hasta que C̄k esté vacío.
Resolución del Grafo de 9 Nodos
Rastreo secuencial de conexiones partiendo desde el Nodo 1 (Punto de distribución) hasta enlazar el sistema completo de forma óptima:
Paso 0: Inicio
Establecemos el nodo 1 como punto de partida. Aún no hay conexiones.
| Iteración | Nodos Conectados (Ck) | Arco Elegido | Longitud |
|---|---|---|---|
| Inicio | {1} | - | - |
| 1 | {1, 5} | 1 → 5 | 4 |
| 2 | {1, 5, 6} | 5 → 6 | 3 |
| 3 | {1, 5, 6, 7} | 6 → 7 | 3 |
| 4 | {1, 5, 6, 7, 2} | 1 → 2 | 5 |
| 5 | {1, 5, 6, 7, 2, 9} | 5 → 9 | 6 |
| 6 | {1, 5, 6, 7, 2, 9, 3} | 2 → 3 | 6 |
| 7 | {1, 5, 6, 7, 2, 9, 3, 8} | 9 → 8 | 5 |
| 8 | {1, 5, 6, 7, 2, 9, 3, 8, 4} | 6 → 4 | 7 |
| Longitud Mínima Total: | 39 | ||