Antología de Investigación de Operaciones
Ingeniería en Sistemas Computacionales
Una red con n nodos requiere de sólo( n-1) ligaduras para proporcionar una trayectoria entre cada par de nodos. No debe usarse más ligaduras puesto que ello aumentaría, sin necesidad, la longitud total de las ligaduras seleccionadas. Las( n-1) ligaduras deben elegirse de tal manera que la red resultante – con solo las ligaduras seleccionadas – forme un árbol de expansión – según la definición que se presentó anteriormente-. Por lo tanto, el problema es encontrar el árbol de expansión con la longitud total mínima de sus ligaduras.
La figura de 2.3.( a) se ilustra el concepto de árbol de expansión, pues los nodos O, A, B y C no están conectados con los nodos D, E y T. Se necesita una ligadura más para hacer esta conexión. En realidad, esta red consta de dos árboles, uno para cada uno de dos conjuntos de nodos. Las ligaduras de la figura 2.3.( b), sí se expanden por toda la red – es decir, es una gráfica conexión según la definición de redes-, pero no es un árbol porque tiene dos ciclos( O-A-B-C-O y D-T-E-D), esto es, tiene demasiadas ligaduras. Como el problema de Seervada Park tiene n = 7 nodos, en la definición de redes se indicó que una red debe tener exactamente n-1 = 6 ligaduras y ningún ciclo para calificar como árbol de expansión. Esta condición se logra en la figura 2.3.( c), por lo que esta red es una solución factible – con una longitud total de 24 millas en las ramas o ligaduras – para el problema del árbol de expansión mínima( Se verá que esta solución no es óptima, puesto que es posible construir un árbol de expansión con sólo 14 millas es sus ramas).
Figura 2.3.( a)
Figura 2.3.( b)
Figura 2.3.( c)
45