En la bibliografia inglesa se llama Spanning Tree of Minimum Cost Algorithm.
El número máximo de arcos que puede tener un grafo de n vértices es n * ( n - 1 ) / 2.
Cualquier grafo conectado con n vértices debe tener al menos n - 1 arcos
y todos los grafos conectados con n - 1 arcos son árboles.
Para unir n vértices de un grafo, solo es necesario n - 1 arcos.
Al unir n vértices de un grafo con n - 1 arcos estamos en presencia de un
árbol contenido en el grafo.
El costo de un árbol contenido es la sumatoria de los costos de sus ramas.
Podemos sintetizar diciendo, los vértices son puntos a conectar, los
arcos puentes físicos, los árboles contenidos son
posibles configuraciones de puentes entre los vértices con el mínimo
número de arcos y el árbol contenido mínimo es el de mínimo costo.
El Algoritmo Arbol Incluido de Mínimo Costo se usa en hallar un conjunto
de ecuaciones independientes, en un sistema de ecuaciones, en particular es muy
usado en el analisis de circuitos eléctricos. Otro ejemplo de su uso es considerar
representadas ciudades en los vértices del grafo y en los arcos las
posibles líneas de comunicación entre las ciudades, con su respectivo costo.
Nos proponemos conectar todas la ciudades al mínimo costo.
*---* 16 *---* *---* 16 *---*
| 1 |---------| 2 | | 1 |---------| 2 |
*---* *---* *---* *---*
| \21 11/ | \5 11/ | \5
| \*---*/ | \*---* *---*/ | \*---*
19| | 6 | |6 | 3 | | 6 | |6 | 3 |
| /*---*\ | /*---* *---* | *---*
| /33 14\ | /10 |
*---* *---* *---* *---*
| 5 |---------| 4 | | 5 |---------| 4 |
*---* 18 *---* *---* 18 *---*
Grafo 1 Spanning Tree 1
Observar que estamos hablando de un grafo conectado, pero nó de un grafo
completo, donde los arcos del grafo son puentes factibles, a considerar a
priori. El algoritmo determinará los arcos imprescindibles, a mínimo costo.
Luego pueden adicionarse, si el caso lo merece, arcos redundantes, sabiendo
cuanto, más alla del mínimo, estoy aceptando.
Veamos un bosquejo del algoritmo :
Arcos Costos Accion Nodos Arcos N - 1
*---* *---* *---* *---* *---* *---*
comenzar 0 0 5 | 1 | | 2 | | 3 | | 4 | | 5 | | 6 |
*---* *---* *---* *---* *---* *---*
*---* *---* *---* *---* *---* *---*
(2, 3) 5 aceptado 2 1 5 | 1 | | 2 |---| 3 | | 4 | | 5 | | 6 |
*---* *---* *---* *---* *---* *---*
*---* *---* *---* *---* *---*
(2, 4) 6 aceptado 3 2 5 | 1 | | 2 |---| 3 | | 5 | | 6 |
*---* *---* *---* *---* *---*
| *---*
+-----| 4 |
*---*
*---* *---* *---* *---* *---*
(3, 4) 10 rechazado 3 2 5 | 1 | | 2 |---| 3 | | 5 | | 6 |
*---* *---* *---* *---* *---*
| *---*
+----| 4 |
*---*
*---* *---* *---* *---*
(2, 6) 11 aceptado 4 3 5 | 1 | | 2 |---| 3 | | 5 |
*---* *---* *---* *---*
*---* | | *---*
| 6 |----+ +----| 4 |
*---* *---*
*---* *---* *---* *---*
(4, 6) 14 rechazado 4 3 5 | 1 | | 2 |---| 3 | | 5 |
*---* *---* *---* *---*
*---* | | *---*
| 6 |----+ +----| 4 |
*---* *---*
*---* *---* *---* *---*
(1, 2) 16 aceptado 5 4 5 | 1 |---| 2 |---| 3 | | 5 |
*---* *---* *---* *---*
*---* | | *---*
| 6 |----+ +----| 4 |
*---* *---*
*---* *---* *---*
(4, 5) 18 aceptado 6 5 5 | 1 |---| 2 |---| 3 |
*---* *---* *---*
*---* | | *---* *---*
| 6 |----+ +----| 4 |---| 5 |
*---* *---* *---*
(1, 3) 19 terminar 6 5 5
(3, 6) 33 terminar 6 5 5
En la bibliografia inglesa se llama
Single Source All Destinations Algorithm.
Como ejemplo, consideremos un sistema de caminos entre ciudades y un motociclista
que, estando en una ciudad, se pregunta :
Observar que interesa la suma de los pesos de los arcos recorridos y no la
cantidad de arcos transitados.
Llamaremos fuente a el vértice donde comienza el camino y destino
donde se desea llegar. Usaremos digrafos, para contemplar el caso más general
de caminos que permiten una sola mano de tránsito.
45
+--------------------->---------------------+
| 50 10 |
+---+-------->--------+---+-------->--------+---+ Fuente Destino Paso Mas Corto Longitud
fuente |Ve0| +-----|Ve1| +---------|Ve4|
+---+ | +---+ | +-------+---+ Ve0 Ve1 Ve0 Ve2 Ve3 Ve1 10
| | | destino | | destino
| | | | | | Ve0 Ve2 Ve0 Ve2 25
| | | | | |
20 A V 10 +--<--+ 20 A 35 A V 30 Ve0 Ve3 Ve0 Ve2 Ve3 45
| | | 15 | | |
| | | | | | Ve0 Ve4 Ve0 Ve4 45
| | | | | |
+---+ | +---+-------+ | +---+ Ve0 Ve5 infinito
|Ve2|-----+ |Ve3|---------+ |Ve5|
+---+-------->--------+---+--------<--------+---+
destino 15 destino 3 destino
Grafo 2
Veamos un bosquejo del algoritmo, empleando fuerza bruta de computo,
dado un grafo y un vértice fuente :
........>.......
. paso 1 .
+---+.... ....+---+
fuente |VeX|...........>..........|VeY| destino
+---+.... paso 2 ....+---+
. .
........>.......
paso n
+---+ +---+
50|Ve1|50 +---+ +---+ |Ve0|
+---+ 50|Ve1| |Ve0| +---+
+---+ inf+---+ +---+ +---+ +---+ +---+ +---+
10|Ve2|10 +---+ +---+ 0|Ve0| |Ve1| +---+ |Ve4| |Ve2|
+---+ 0|Ve0| inf|Ve3| +---+ +---+ |Ve2| +---+ +---+
+---+ +---+ +---+ 15+---+ +---+ +---+ +---+ +---+ +---+ +---+
0|Ve0| inf|Ve3|inf +---+ +---+ 10|Ve2| |Ve4| +---+ |Ve5| |Ve3| |Ve5|
+---+ +---+ 10|Ve2| 45|Ve4| +---+ +---+ |Ve3| +---+ +---+ +---+
+---+ +---+ inf+---+ +---+ +---+ +---+ +---+
45|Ve4|45 +---+ 25|Ve3| |Ve5| +---+ |Ve1|
+---+ inf|Ve5| +---+ +---+ |Ve1| +---+
+---+ inf+---+ +---+ +---+
inf|Ve5|inf |Ve4|
+---+ +---+
Veamos ahora un ejemplo mas concreto. Si la fuente es Boston, quiero determinar
los caminos mas cortos al resto de las ciudades que participan del grafo.
San Francisco Denver Chicago Boston
*---* 800 *---* 1200 *---* 1500 *---*
| 2 |------<------| 3 |--------<---------| 4 |----------------------<------------------------| 5 | Fuente
*---* *---* *---* +---*---*
| / \ |
| / \ |
| / \ V 250
| / \ |
| / \ 1000 |
| 1000 / ---------------<--------------*---*---+
300V -----------<------------ --------------<--------------| 6 | New York
| / / 1400 +---*---*
| / / |
| / / |
| / / V 900
| / / |
| / / |
*---* 1700 *---* 1000 *---*---+
| 1 |------------------------------------| 8 |----------<------------| 7 |
*---* *---* *---*
Los Angeles New Orleans Miami
Grafo 3
1 2 3 4 5 6 7 8
1 0
2 300 0
3 1000 800 0
4 1200 0
5 1500 0 250
6 1000 0 900 1400
7 0 1000
8 1700 0
Vertice LA SF D C B NY M NO
Iteracion S Seleccionado Distancia 1 2 3 4 5 6 7 8
Inicial inf inf inf 1500 0 250 inf inf
1 5 6 inf inf inf 1250 0 250 1150 1650
2 5,6 7 inf inf inf 1250 0 250 1150 1650
3 5,6,7 4 inf inf 2450 1250 0 250 1150 1650
4 5,6,7,4 8 3350 inf 2450 1250 0 250 1150 1650
5 5,6,7,4,8 3 3350 3250 2450 1250 0 250 1150 1650
6 5,6,7,4,8,3 2 3350 3250 2450 1250 0 250 1150 1650
5,6,7,4,8,3,2
En la bibliografia inglesa se llama
All Pairs Shortest Paths Algorithm.
Nos proponemos hallar los pasos más cortos entre cualquier par de vértices
de un grafo.
1 2 3 A0 *......*
...................... i j
-2 .
+--------<--------+ 1 . 0 1 inf A1 *......*......*
| | . i 1 j
V | 2 . -2 0 1
*---* 1 *---* 1 *---* . A2 *......*......*......*
| 1 |------>------| 2 |------>------| 3 | 3 . inf inf 0 i 1 2 j
*---* *---* *---* . ...
Grafo 3 Matriz de Costos de Adyacencias An *......*......*... ...*......*
i 1 2 n j
La Matriz de Costos de Adyacencia se construye a partir de las siguientes consideraciones :
Observar que para un grafo de n vertices no pueden existir pasos de m s de
n vertices, por lo tanto, solo existen Matriz de Costos A0, A1, A2, ..., An.
No puede existir An+1.
En la bibliografia inglesa se llama
Transitive Closure Algorithm.
Un problema común a tratar con grafos es determinar la existencia de un paso
desde un vértice cualquiera del grafo, digamos i, a otro vértice cualquiera,
digamos j.
En la Matríz de Cierre Transitivo A+, es A+(i,j) = 1 si hay un paso de longitud > 0 de i a j.
En la Matríz de Cierre Transitivo Reflexivo A*, es A*(i,j) = 1 si hay un paso de longitud >= 0 de i a j.
+-------------<-------------+
| |
*---* *---* *---* *---* *---*
| 1 |---->----| 2 |---->----| 3 |---->----| 4 |---->----| 5 |
*---* *---* *---* *---* *---*
Grafo 4
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
............. ............. .............
1 . 0 1 0 0 0 1 . 0 1 1 1 1 1 . 1 1 1 1 1
. . .
2 . 0 0 1 0 0 2 . 0 0 1 1 1 2 . 0 1 1 1 1
. . .
3 . 0 0 0 1 0 3 . 0 0 1 1 1 3 . 0 0 1 1 1
. . .
4 . 0 0 0 0 1 4 . 0 0 1 1 1 4 . 0 0 1 1 1
. . .
5 . 0 0 1 0 0 5 . 0 0 1 1 1 5 . 0 0 1 1 1
Matriz de Matriz de Matriz de
Adyacencia A Cierre Transitivo A+ Reflexion Cierre Trasitivo A*
del Grafo 4 del Grafo 4 del Grafo 4
Observar en A+ que si existen unos en la diagonal principal, existe un ciclo
de largo mayor a uno, para el vertice que se cruza en la diagonal pricipal.
Observar que en A* los unos de la diagonal principal solo indican que hay
un ciclo de largo cero o mayor a cero, para el vertice que se cruza en la diagonal
principal, donde obviamente, siempre hay un paso de largo cero de un
vertice a si mismo. La matriz A* se construye facilmente a partir de A+,
simplemente completando con unos la diagonal principal.
En la bibliografia inglesa se llama
Topological Sort Algorithm.
*---* *---* *---* *---*
|c13|------->-------|C14|--------->--------|C15|---->----|C 5|
*---* *---*\ *---* *---*
| \ --->--
| ->--*---* *---* \*---* *---*
| |C 4|-----|C 8| |C 2| |C 9|
| ->--*---* *---* /*---* /*---*
| / | | / --->---
*---*------------>------------- *---*/ *---*
|C 1|------------------>-------------------|C 3|---->----|C 6|
*---* | | *---*\ *---*
| | | --->---
| | V \
| +-------------->----------------|-----------*---*
| | -->---|C 7|
| *---*--/ *---*
+---------------->--------------|C10|
*---*--\ *---* *---*
-->---|C11|---->----|C12|
*---* *---*
Grafo 5
En la bibliografia inglesa se llama
Critical Paths Algorithm.
*---* *---*
| 2 | | 7 |
a1=6 *---* a4=1 a7=9 *---* a10=2
/ \ / \
*---*--->--- --->---*---*--->--- --->---*---*
comienzo | 1 | | 5 | | 9 | final
*---*--->--- --->---*---*--->--- --->---*---*
| \ / \ /
| a2=4 *---* a5=1 a8=7 *---* a11=4
| | 3 | | 8 |
| *---* *---*
| |
a3=5 | a6=2 | a9=4
| *---* *---* |
+---->----| 4 |----->----| 6 |----->---+
*---* *---*
Grafo 6
En la bibliografia inglesa se llama
Enumerating All Paths Algorithm.
*---* *---*
| 2 |---->----| 4 |
*---* *---*
3 / | \ / | \ 3
*---*->-- | \ 4 / | ->--*---*
| 1 | V5 ->->- V5 | 6 |
*---*->-- | / 4 \ | ->--*---*
2 \ | / \ | / 5
*---* *---*
| 3 |---->----| 5 |
*---* 1 *---*
Grafo 7