Árbol Mínimo Expandido

Grupo 2: Gleidimar Cuenca, Yiberlys Oliveros, Maira Pérez y Solmari Porras.

Cuando hablamos de Árbol Mínimo Expandido, nos referimos a la unión de nodos dentro de una red. Esta debe estar unida de tal manera que no se creen ciclos y así, los nodos se unan para las distancias mínimas o costos mínimos, sea el caso.

El Árbol Mínimo Expandido es apropiado para problemas, en los cuales, la redundancia es expansiva, o el flujo a lo largo de los arcos se considera instantáneo.

¿Para qué se utiliza?                    

Principalmente se utiliza para planificar y diseñar redes de cualquier tipo. Es una buena forma de establecer planes eficientes dentro de una comunidad; por ejemplo, en la planificación de servicios públicos, como el servicio de agua, de alumbrado, de transporte, entre otros.

Objetivo

Tal y como se señala el principal objetivo del Árbol Mínimo Expandido es minimizar las distancias o los costos, bien sea el caso que deseamos resolver.

Problema

A continuación, presentamos un ejemplo sencillo y fácil de entender para la ejecución de este método:

   La operadora de acueductos HidroCapital, requiere suministrar agua a varios sectores del este de la ciudad de Caracas. En el siguiente gráfico se presentan los diferentes puntos donde se debe abastecer el servicio de agua:

Gráfico #1

Determinar la forma más económica de suministrar agua a todos los sectores a través de un Árbol Mínimo Expandido.

Solución 

Para resolver este problema, utilizamos como herramienta el programa TORA

El procedimiento se realizó de la siguiente manera:

Abrimos el programa y damos "Click Here"

Luego, damos click a "Network models" y siguiente a "Minimal Spanning Tree"

Le colocamos nombre al problema en "Problem Title" y seguidamente el número de nodos "No. of Nodes"; en este caso, son 8 nodos que serían los sectores. Agregamos todos los datos que nos muestra el Gráfico #1 con respecto a los nodos A, B, C, D, E, F, G y H. En la tabla se muestra, respectivamente, los costos (miles de Bs.) que hay entre un nodo y otro. Después de llenar la tabla, damos click a "SOLVE Menu"

Nos pide para "salvar" el documento. Damos click a "Si" y lo guardamos en cualquier parte de nuestro disco duro.

Luego damos click a "Solve Problem" y después a "Go To Output Screen"

Seguidamente, en "Starting Node" seleccionamos cualquier nodo que representaría el "nodo de partida o inicio" como tal, y damos click a "All Iterations" y "Aceptamos" lo que nos pide.
Se observa entonces una lista de las conexiones de los nodos que serían los más económicos con respecto a la construcción de tuberías para suministrar agua hacia los sectores.

Y el nuevo gráfico, de acuerdo a los resultados de TORA, queda de la siguiente manera:

Gráfico #2

En conclusión, se reduce a 25 mil Bs., el costo total de la construcción de tuberías para el suministro de agua hacia los diversos sectores del este de Caracas.

Conceptos básicos

• Árbol: una serie de nodos que no contienen ciclos

• Árbol Expandido: es un árbol que conecta todo los nodos de la red  (contiene n-1 arcos).

• Arcos: líneas, ligaduras o ramas. Se etiquetan para dar nombre a los nodos en sus puntos terminales.

• Nodos: puntos o vértices.