Analisis De Redes

Ejemplo
Una Compañía de TV por cable se encuentra en proceso de proporcionar el servicio de cable a cinco nuevas áreas urbanizadas de casas habitación. La figura No. 1 representa los enlacespotenciales de TV entre las cinco áreas. Los kilómetros de cable se muestran en cada rama. Utilice el algoritmo del árbol de expansión mínima para determinar la red de cable más económica para la empresa,FiguraNo.1 Enlaces potenciales de TV entre las cinco áreas
Tres (kilómetros)
2
6
5
4
1
9
1
5
3
10
7
5
8
6
3
4
|
El algoritmo empieza en el nodo 1 (cualquier otro nodo tambiénservirá), lo que nos da
C1 = {1}, Ĉ1 = {2, 3, 4, 5, 6}
Las iteraciones del algoritmo se resumen en la figura No. 2. Los arcos delgados proporcionan todos los enlaces candidatos entre C y Ĉ. Las ramasgruesas representan los enlaces permanentes entre los nodos del conjunto conectado C y la rama de guiones representan el nuevo eslabón (permanente) añadido a cada iteración.

Ĉ2
Figura No.2Iteraciones del algoritmo de expansión mínima
C2
Ĉ1
3
5
5
2
2
6
4
1
9
1
3
9
C1
3
1
1
5
5
6
6
7
7
4
4
Iteración 2
Iteración 1
3
3
2
1
4
5
6
5
2
63
3
6
6
Ĉ4
C4
C3
4
1
Ĉ3
5
4
1
1
5
8
7
7
3
4
Iteración 4
Iteración 3
3
3
5
1
6
5
2
3
2
4
3
1
4
Ĉ5
Eslabones alternativos
C5
6
4
1
1
4
106
5
5
5
5
3
3
Iteración 6
(Arbol de expansión mínima)

Iteración 5
|
Por el ejemplo, en la iteración 1, la rama 1 → 2 es el eslabón más corto (= 1 kilometro) entre todas las ramascandidato del nodo 1 a los nodos 2, 3, 4, 5 y del conjunto no conectado Ĉ1. Por tanto, el eslabón 1→ 2 se hace permanente y j* = 2, lo que da
C2 = {1, 2}, Ĉ2 = {3, 4, 5, 6}
La solución la da el árbolde expansión mínima que se muestra en la iteración 6 de la figura 2. El mínimo resultante de kilómetros de cable necesario para proporcionar el servicio de cable deseado es 1 + 3 + 4 + 3 + 5 = 16...