Á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.
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 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 Č0 llamado i el cual será el primer nodo permanente, a continuación se debe de actualizar el conjunto
C1 = {i}, que significa que 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ó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 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. Al
actualizar 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 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.
