Árbol Mínimo Expandido

Autores: Andres Henriquez, Deilimar Pajaro y Genesis Ponce

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

Este método es utilizado para la planificación y diseño de cualquier tipo de red, si quisiéramos utilizarlo en una carrera como Organización Empresarial seguramente lo podríamos aplicar en el diseño de un proceso como ensamblaje de un producto cualquiera, donde tengamos que transportar piezas de un lado a otro; podemos utilizarlo también para establecer prioridades en el diseño de alguna estrategia guiada a cumplir los objetivos de una Organización.

¿Que debemos tomar en cuenta?

1) No deben haber ciclos ¡Nunca!, si llegara a existir aunque sea un pequeño ciclo dentro de nuestra red entonces créeme que no se trata de un árbol mínimo expandido.

2) Debemos unir cada nodo con el que esta más cercano o tiene un mínimo costo.

3) Debe haber una ligadura o arco uniendo cada par de nodos con el fin de que se unan todos los nodos que necesitamos y sean factibles para cumplir nuestro principal objetivo, reducir los costos y distancias o los tiempos.

4) La red siempre tendrá una cantidad de arcos igual a n nodos menos 1, la idea es que no haya un numero exagerado e innecesario de arcos (caminos, ligaduras) entre nuestros nodos, así evitamos también la formación de ciclos que repito, no deben existir dentro de nuestra red!

¿Para que 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 empresa, en una comunidad, en la planificación de servicios públicos como las tuberías de agua que abastecen a toda una ciudad, el servicio de alumbrado en una comunidad, el servicio de transporte también podría ser planificado con este método, entre otros.

¿Cómo se usa?

Paso 1. Teniendo un conjunto de nodos debemos tomar cualquiera y conectarlo con el más cercano o tiene un bajo costo.

Paso 2. Conectar los siguientes nodos con la misma regla del paso 1.

Problema

Un cyber ubicado en la ciudad de Caracas tiene el proyecto de unir 6 computadoras representadas en la siguiente red, los números en cada arco representan la longitud en metros del cable necesario para conectar las computadoras.

Siguiendo los pasos 1 y 2 deberíamos lograr tener algo como esto:

Logrando así reducir la longitud del cable que debemos utilizar para la conexión de las computadoras que sería igual a 16 metros de cable.

¿Como resolverlo con WinqSB?

1) Se llena el método tabular, este se ira auto-llenando de manera que parecerá una matriz simétrica.

2) Pido la Solución del problema en la barra de tareas.

Análisis

·         Se debe conectar el nodo 1 con el nodo 2 a una distancia de 1 metro.

·         Se debe conectar el nodo 1 con el nodo 3 a una distancia de 5 metros.

·         Se debe conectar el nodo 2 con el nodo 4 a una distancia de 4 metros.

·         Se debe conectar el nodo 2 con el nodo 5 a una distancia de 3 metros.

·         Se debe conectar el nodo 4 con el nodo 6 a una distancia de 3 metros.

Distancia total: 16 metros

3) Interacciones

Paso a paso para resolver el problema en WinqSB

Mark Silva, Arbol de expansión minima WinqSB

Bibliografia

• Teoría de redes, www.Ingenierosindustriales.JIMDO.com
• BUSTOS EDUARDO, Modelos de redes: Árbol de expansión mínima.
• SARMIENTO y ALOMOTO, Redes (Árbol de expansión mínima)