Estructura de Datos : Grafos - Algoritmos


Algoritmo Arbol Contenido de Mínimo Costo

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 :
  1. Comenzar
  2. Ordenar los arcos del grafo, en órden creciente de su costo, en una estructura de datos
  3. Mientras el árbol contenido en el grafo tenga menos que n - 1 arcos ...
    1. Elegir el arco de mínino costo desde la estructura de datos
    2. Eliminar el arco elegido de la estructura de datos de arcos seleccionables
    3. El arco elegido cierra un ciclo en el árbol contenido ...
      1. Si - Descartar el arco elegido
      2. No - Agregar el arco elegido al arbol contenido
  4. Terminar
   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


Algoritmo Fuente Simple a Todos los Destinos

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 :

  1. ¿ Hay un camino para ir desde esta ciudad a tal ciudad ?
  2. ¿ Si hay más de un camino entre ambas ciudades, cual es el más corto ?
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 :
  1. Comenzar
  2. Determinar los vértices destino
  3. Agregar a una estructura de datos los vértices destinos
  4. Mientras existan vértices destinos en la estructura de datos ...
    1. Leer el primer vértice destino desde la estructura de datos
    2. Eliminar el vértice leido de la estructura de datos
    3. Determinar todos los pasos entre la fuente y el destino leído
    4. Ordenar los pasos determinados de menor a mayor
    5. Seleccionar el paso menor
  5. Terminar
                     ........>.......
                     .    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


Algoritmo de Todos los Pares Más Cortos

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. Comenzar
  2. Agregar a una estructura de datos todos los vértices
  3. Mientras existan vértices en la estructura de datos ...
    1. Leer el primer vértice desde la estructura de datos
    2. Eliminar el vértice leido de la estructura de datos
    3. Ejecutar el Algoritmo Fuente Simple a Todos los Destinos a partir del vértice leído
  4. Terminar
                                                                     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.


Algoritmo Cierre Transitivo

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.


Algoritmo de Clasificación Topológica

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


Algortimo de Paso Crítico

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


Algoritmo de Enumeración de Todos los Pasos

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