matematicas

ALGORITMO DEL ÁRBOL DE EXPANSIÓN MÍNIMA
El algoritmo del árbol de expansión mínima es un modelo de optimización de redes que consiste en enlazar todos los nodos de la red de forma directa y/o indirecta con el objetivo de que la longitud total de los arcos o ramales sea mínima (entiéndase por longitud del arco una cantidad variable según el contexto operacional de minimización, y que puede bienrepresentar una distancia o unidad de medida).

Sean

N = {1,2,3,...,n} el conjunto de nodos de la red.
Ck= Conjunto de nodos que se han enlazado de forma permanente en la iteración k
Čk= Conjunto de nodos que hacen falta por enlazarse de forma permanente.
PASO CERO (0): CONCEPTUALIZACIÓN DEL ALGORITMO
Definir los conjuntos C0 = {ø} y Č0 = {N}, es decir que antes del paso 1 no sehan enlazado de forma permanente nodo alguno, y por ende el conjunto que representa a los nodos que hacen falta por enlazarse de forma permanente es igual a la cantidad de nodos que existen en la red.
PASO 1:
Se debe de escoger de manera arbitraria un nodo en el conjunto Č0 llamado i el cual será el primer nodo permanente, a continuación se debe de actualizar el conjunto C1 = {i}, que significaque al tiempo en que el conjunto C1 gana el elemento i el conjunto Č0 pierde el elemento i por ende ahora será igual a Č1 = N - {i}, además se debe actualizar el subíndice de los conjuntos k, el cual ahora será igual a 2.
PASO 2: PASO GENERAL "K"
Se debe de seleccionar un nodo j del conjunto ČK-1 ("k-1" es el subíndice que indica que se está haciendo referencia al conjunto de la iteracióninmediatamente anterior) el cual tenga el arco o ramal con menor longitud con uno de los nodos que se encuentran en el conjunto de nodos de enlace permanente CK-1. Una vez seleccionado se debe de enlazar de forma permanente lo cual representa que pasa a formar parte del conjunto de enlaces permanentes y deja de formar parte del conjunto que todavía se debe conectar para lograr la expansión. Alactualizar el algoritmo en este paso los conjuntos deben de quedar de la siguiente forma.

CK = CK-1 + {j} mientras que ČK = ČK-1 - {j}
El paso general que define k que al mismo tiempo representa a las iteraciones debe de ejecutarse toda vez que el conjunto ČK no sea vacío, cuando este conjunto sea igual a vacío se tendrá el árbol de expansión mínima.

El entendimiento del algoritmo desde elpunto de vista algebraico no es quizá el más simple, sin embargo mediante el ejemplo gráfico se verá que es un algoritmo muy sencillo de elaborar.
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 laciudad. 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 lasconexiones 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 seencuentra 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...