ÁRBOL DE EXPANSIÓN MÍNIMA
MARIA CAMILA PARRA MEDINA
CÓD: 20142015029
ING. CÉSAR ALMICAR LÓPEZ
TEORÍA DE GRAFOS
UNIVERSIDAD DISTRITAL FRANCISCO JOSÉ DE CALDAS
FACULTAD DE INGENIERÍA
INGENIERÍA INDUSTRIAL
2019
ÁRBOL DE EXPANSIÓN MÍNIMA
1. Marco Teórico
1.1 Árbol de Expansión mínima
Es un modelo de optimización a través del cual se busca el camino que conecte todos
los nodos n de una red de arcos (i-j), de tal forma que este ofrezca el menor peso
posible, teniendo en cuenta que todos los recorridos tienen que ser abiertos (no ser
ciclos)[1]. Generalmente se utiliza cuando la redundancia es excesiva o la cantidad de
flujo en los arcos es instantánea
La solución óptima se caracterizará por poseer n-1 arcos, teniendo en cuenta en denotar
los arcos pertenecientes al árbol con el valor 1 mientras que aquellos que no con valor
0.
La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa
con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras,
o las redes eléctricas.
Su modelo general es:
Imagen 1. Tomado de ejemplo de árbol mínimo (clase)
Donde :
Cij: Costo o distancia de los arcos de la red
Xij: Arcos de la red
S= Subtour (ciclo)
Con el fin de llevar a cabo este objetivo se hace uso de dos algoritmos, los cuales son:
1.2 Algoritmo de Kruskal
Fue creado por Joseph B. Kruskal, un investigador del Math Center (Bell-Labs) en
1956, con el objetivo de dar solución al árbol de mínimo coste total mínimo o árbol
recubridor euclídeo mínimo. Su construcción se basa en la elección inicial de un
arco o arista de menor valor dentro de la red, sucesivamente se seleccionan de las
restantes las de valor mínimo, recordando en no generar ningún ciclo[3], se finaliza
al momento de recorrer todos los nodos sin importar que todas las aristas no hayan
sido utilizadas. [4]
1.3 Algoritmo de Prim
Al igual que el algoritmo de Kruskal, busca la solución del modelo de optimización
del árbol de expansión mínimo, este se da en redes nonexas, no dirigidas y
ponderadas. Fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de
manera independiente por el científico computacional Robert C. Prim en 1957 y
redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también
conocido como algoritmo DJP o algoritmo de Jarnik.
Se lleva a cabo tomando el arco con menor valor en la red y a partir de los nodos
seleccionados, elegir los nodos incidentes de distancia menor hasta que se recorran
todos los nodos.
2. Solución ejercicio
2.1 Ejercicio original
Tomando en cuenta el ejercicio dado a resolver, se realizan los diversos algoritmos
con el fin de encontrar el subconjunto de nodos o árbol de expansión mínima a
través del cual se obtiene la menor longitud recorriendo todos los nodos de la red.
Dicho lo anterior, la red original dada es:
Imagen 2. Tomado de taller
2.2 Algoritmo de Prim
Dada la explicación y clase y posterior investigación se llevó a cabo la construcción
del árbol de expansión a través del algoritmo de Prim, tomando como arco inicial de
menor valor, el cual corresponde al arco (14-18) con una distancia de 4, a partir de
ahí se tomaron los arcos incidentes mínimos a los nodos ya seleccionados,
llevando a una solución óptima de de n-1 arcos, siendo n=20, y consiguiente 19 los
cuales se muestran en la siguiente imagen del árbol hallada, procedimiento que se
puede encontrar en el documento anexo de Excel.
Imagen 3. Tomado de taller anexo (Excel)
Solución óptima
Arco Distancia
(1-2) 5
(2-7) 11
(7-11) 9
(11-15) 8
(15-19) 10
(19-16) 12
(6.4) 11
(6-5) 7
(5-10) 8
(10-14) 10
(14-18) 4
(18-20) 7
(9-13) 8
(13-14) 9
(8-9) 7
(17-18) 9
(2-3) 4
(3-8) 6
(7-12) 12
TOTAL RECORRIDO 157
Imagen 4. Tomado de taller (Excel)
De lo anterior al realizar la sumatoria de los valores correspondientes a los arcos del
árbol de expansión, se concluye que la longitud mínima o costo mínimo de la ruta
hallada que conecte todos los nodos de la red es igual a 157 unidades.
2.3 Algoritmo de Kruskal
Es importante conocer que el resultado obtenido por ambos algoritmos debe ser igual, por
lo que el árbol de expansión hallado debe coincidir en sus arcos y valores.
Teniendo en cuenta lo anterior se eligió como primer arco aquel con mínimo valor en la red
el cual fue (14-18) con distancia 4 y en segundo lugar el arco (2-3) con distancia 4, de allí
en adelante se siguió eligiendo los arcos con menor valor ubicados en cualquier parte d ela
red, hasta llegarr al resultado siguiente:
Imagen 5. Tomada de taller anexo (Excel)
Solución óptima
Arco Distancia
(1-2) 5
(2-7) 11
(7-11) 9
(11-15) 8
(15-19) 10
(19-16) 12
(6.4) 11
(6-5) 7
(5-10) 8
(10-14) 10
(14-18) 4
(18-20) 7
(9-13) 8
(13-14) 9
(8-9) 7
(17-18) 9
(2-3) 4
(3-8) 6
(7-12) 12
TOTAL RECORRIDO 157
Se obtiene la misma estructura de árbol de expansión que en el algoritmo Prim, con un
valor mínimo de recorrido igual a 157 unidades.
2.4 Solución de optimización
Dado lo anterior se realiza el modelo de optimización a través del programa Excel,
teniendo en cuentas las restricciones subtour y la cantidad de visita de nodos.
BIBLIOGRAFÍA
[1] Árbol de expansión mínima. Tomado
dehttps://www.inf.utfsm.cl/~esaez/fio/s1_2004/apuntes/grafos_s1_2004.pdf
[2] Árbol de expansión mínima y flujo máximo. Tomado de:
http://www.angelfire.com/planet/invo_ago_2006/clase8_2.pdf
[3]Árboles ponderados y árboles de expansión mínima. Tomado de:
https://compdiscretas.wordpress.com/2012/11/04/4-4-arboles-ponderados-y-arboles-de-
expansion-minima/
[4]Algoritmo de Kruskal. Tomado de: http://arodrigu.webs.upv.es/grafos/doku.php?
id=algoritmo_kruskal
[5]Algoritmo de Prim Tomado de:
![BIBLIOGRAFÍA
[1]
Árbol
de
expansión
mínima.
Tomado
dehttps://www.inf.utfsm.cl/~esaez/fio/s1_2004/apuntes/grafos_s1_](https://screenshots.scribd.com/Scribd/252_100_85/326/478912473/8.jpeg)
