Problema Árbol de expansión Mínima

Árbol: Es un grafo en el que existe un único nodo desde el que se puede acceder a todos los demás y cada nodo tiene un único predecesor, excepto el primero, que no tiene ninguno. También podemos definir un árbol como:

Árbol de expansión: Un árbol de expansión es aquel árbol que enlaza todos los nodos de la red, de igual manera no permite la existencia de ciclos.

• Un grafo conexo y sin ciclos.
• Un grafo sin ciclos y con n-1 aristas, siendo n el número de vértices.

• Árbol de mínima expansión: Árbol de máximo alcance cuyo valor es mínimo, es decir, la suma de sus aristas es 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 bien representar una distancia o unidad de medida).

 

Sean

 

N = {1,2,3,...,n} el conjunto de nodos de la red.

C_k= 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 C₀ = {ø} y Č₀ = {N}, es decir que antes del paso 1 no se han 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 Č₀ llamado i el cual será el primer nodo permanente, a continuación se debe de actualizar el conjunto C₁ = {i}, que significa que al tiempo en que el conjunto C₁ gana el elemento i el conjunto Č₀ pierde el elemento i por ende ahora será igual a Č₁ = 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ón inmediatamente 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 C_K-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. Al actualizar el algoritmo en este paso los conjuntos deben de quedar de la siguiente forma.

 

C_K = C_K-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 el punto 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.