RESOLUCIÓN DE UN PROBLEMA DE ÁRBOL DE EXPANSIÓN MÍNIMA
EL PROBLEMA
La ciudad de Cali cuenta con un nuevo plan parcial de vivienda el
cual contará con la urbanización de más de 7 proyectos habitacionales
que se ubicarán a las afueras de la ciudad. Dado que el
terreno en el que se construirá no se encontraba hasta ahora dentro
de las zonas urbanizables de la ciudad, el acueducto municipal no cuenta
con la infraestructura necesaria para satisfacer las
necesidades de servicios públicos en materia de suministro de agua.
Cada uno de los proyectos de vivienda inició la construcción de un nodo
de acueducto madre, el cual cuenta con las conexiones
de las unidades de vivienda propias de cada proyecto (es decir que
cada nodo madre solo necesita estar conectado con un ducto madre del
acueducto municipal para contar con su suministro). El
acueducto municipal al ver la situación del plan parcial debe de
realizar las obras correspondientes a la instalación de ductos madres
que enlacen todos los nodos del plan con el nodo Meléndez
(nodo que se encuentra con suministro de agua y que no pertenece al
plan parcial de vivienda, además es el más cercano al mismo), la
instalación de los ductos implica obras de excavación, mano de
obra y costos de los ductos mismos, por lo cual optimizar la
longitud total de los enlaces es fundamental. Las distancias existentes
(dadas en kilómetros) correspondientes a las rutas factibles
capaces de enlazar los nodos del plan parcial se presentan a
continuación. Además la capacidad de bombeo del nodo Meléndez es más que
suficiente para satisfacer las necesidades de presión que
necesita la red madre.
El acueducto municipal le contacta a usted para que mediante sus
conocimientos en teoría de redes construya una red de expansión que
minimice la longitud total de ductos y que enlace todos los
nodos del plan parcial de vivienda.
PASO 0:
PASO 1:
Se definen los conjuntos iniciales C0 = {ø} que corresponde al conjunto de nodos enlazados de forma permanente en la iteración indicada en el subíndice y Č0
= {N =
1,2,3,4,5,6,7,8} que corresponde al conjunto de nodos pendientes por
enlazar de manera permanente en la iteración indicada en el subíndice.
PASO 1:
Se debe definir de manera arbitraria el primer nodo permanente del conjunto Č0, en este caso escogeremos el nodo 1 (puede ser cualquier otro), que algebraicamente se representa
con la letra i, se procede a actualizar los conjuntos iniciales, por ende C1 = {i} = {1} y Č0 = {N - i} = {2,3,4,5,6,7,8}, actualizamos k por ende ahora
será igual a 2.
PASO 2:
Ahora se debe seleccionar el nodo j del conjunto ČK-1 (es decir del conjunto del paso 1) el cual presente el arco con la menor longitud y que se encuentre enlazado con uno de
los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1 (es decir que se debe de encontrar un nodo que tenga el arco de menor longitud
enlazado al nodo 1).
Los arcos o ramales de color naranja representan los arcos que enlazan el conjunto ČK-1 (es decir del conjunto del paso 1, recordemos que K en este paso es igual a 2, por
ende ČK-1= Č1) con los nodos de enlace permanente del conjunto Ck-1 en el cual ahora solo se encuentra el nodo 1, por ende ahora solo falta escoger el de
menor longitud, que en este caso es el arco cuya longitud es 2, que enlaza de forma permanente ahora el nodo 2.
Al actualizar los conjuntos quedan así:
C2 = {1,2} y Č2 = {3,4,5,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración. Ahora se seleccionará un nuevo nodo j del conjunto Č2que presente el
enlace (ramal o arco) de menor longitud con los nodos que se encuentran en el conjunto C2.
Los arcos de color naranja representan los enlaces posibles y dado
que existe empate entre las menores longitudes se elige de manera
arbitraria, en este caso se representa nuestra elección con un
arco de color verde, enlazando de forma permanente ahora el nodo 4.
Al actualizar los conjuntos quedan así:
C3 = {1,2,4} y Č3 = {3,5,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
Lo que representan los arcos naranja y verde es ya conocido, ahora
la línea azul interrumpida irá trazando nuestro árbol de expansión
final. Dado a que el arco menor es el de longitud 3, ahora se
enlazará de manera permanente el nodo 5.
Al actualizar los conjuntos quedan así:
C4 = {1,2,4,5} y Č4 = {3,6,7,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
Ahora se enlazará de manera permanente el nodo 7.
Al actualizar los conjuntos quedan así:
C5 = {1,2,4,5,7} y Č5 = {3,6,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
Ahora se enlazará de manera permanente el nodo 6.
Al actualizar los conjuntos quedan así:
C6 = {1,2,4,5,7,6} y Č6 = {3,8}
Ahora se procede a actualizar k ya que se procede a efectuar la siguiente iteración.
Se rompen los empates de forma arbitraria, ahora se enlazará de manera permanente el nodo 3.
Al actualizar los conjuntos quedan así:
C7 = {1,2,4,5,7,6,3} y Č7 = {8}
Ahora se procede a actualizar k ya que se procede a efectuar la última iteración.
Ahora se enlazará de manera permanente el nodo 8.
Al actualizar los conjuntos quedan así:
C8 = {1,2,4,5,7,6,3,8} = {N} y Č8 = {ø}
Por ende se ha llegado al árbol de expansión mínima
Árbol que presenta una longitud total minimizada de 21 kilometros de ductos.
Video del ejemplo:
Video del ejemplo:
No hay comentarios.:
Publicar un comentario