Problema de árbol de expansión mínima
En estos problemas se requiere que los arcos o ligaduras seleccionadas proporcionen
una trayectoria entre cada par de nodos.
Algoritmo del árbol de expansión mínima:
1. Se selecciona, de manera arbitraria, cualquier nodo y se conecta, es decir, se
agrega un arco al nodo distinto más cercano.
2. Se identifica el nodo no conectado más cercano a un nodo conectado y se
conectan estos dos nodos, es decir, se agrega un arco entre ellos. Este paso se
repite hasta que todos los nodos están conectados.
3. Se pueden romper los empates de nodos de manera arbitraria, pero el algoritmo
debe llegar siempre a una misma solución óptima. Cabe mencionar que la
presencia de estos empates son señal de que puede existir (aunque no
necesariamente) soluciones óptimas múltiples. Todas esas soluciones se pueden
identificar si se trabaja con las demás formas de romper los empates al final.
Aplicación del algoritmo del árbol de expansión mínima al problema del Bosque de
Chapultepec
La administración debe determinar los caminos bajo los cuales se deben tender líneas
eléctricas para conectar a todas las estaciones con una longitud total mínima de cable.
Figura 1. Casetas en el bosque de Chapultepec
Solución
1er paso. Se selecciona arbitrariamente el nodo T y se conecta al nodo más cercano, el
cual es el nodo D
D 5 T
2do paso. El nodo más cercano es el nodo E desde D
A
2 2
D 5 T
O B
1
1 3
E
C
Como ya están conectados todos los nodos, entonces tendríamos la distancia óptima con
14 millas. Este resultado debe ser el mismo si se parte desde cualquier otro nodo.
2 2 D 5 T
O B
1
3
1 E
C
Se comprueba que vuelve a dar la distancia óptima de 14 millas sin importar del nodo del
que se parta.
Ejemplo 2
El campus de la universidad tiene cinco microcomputadoras. La distancia entre cada par
de computadoras (en cuadras de la ciudad) se da en la figura 5. Las computadoras deben
estar conectadas mediante un cable subterráneo. ¿Cuál es la longitud mínima de cable
requerido? Observe que no se traza un arco que conecte un par de nodos, esto significa
que (debido a las formaciones rocosas subterráneas) no se puede tender un cable entre
estas computadoras.
Figura 2. Distancia entre las microcomputadoras
1 1 2
4
2 2 3
6
5 2 3
4
4 5
Solución:
1er paso. Se elige de manara arbitraria el nodo 1 y se conecta con el nodo más cercano
que es el nodo 2.
1
1 2
2do paso. El nodo más cercano a 1 o 2 es el nodo 5 desde 2
1
1 2
2
5
3er paso. El nodo más cercano a 1, 2 o 5 es el nodo 3
1
1 2
2
5 3
4
2
4
Como ya se encuentran conectados todos los nodos, se tiene una solución óptima con
una distancia mínima de 9.
1 1 2
4
2 2 3
6
5 2 3
4
4 5
Solución: 2
1 1
2
3
5 2
4 4
Como ya se encuentran conectados todos los nodos, se tiene una distancia óptima, la
cual vuelve a ser de 9.