Clausura Transitiva
La clausura transitiva de un grafo G se define como el grafo G* = (V, E*), donde E*={(i, j): hay un camino desde el vértice i al vértice j en G}.
Definición Formal:
Optimización: ¿Cuáles son los caminos existentes entre pares de nodos?
Recordemos transitividad:
El concepto de transitividad es el mismo que se utiliza en teoría matemática el cual postula que si a<b<c Þ a<c, en el caso de clausura transitiva, el concepto se refiere a que existe un camino que une el vértice i con el vértice j, no importando que para llegar desde i a j tengamos que visitar otros vértices del grafo. Por esta razón es que el algoritmo fue diseñado para grafos dirigidos, donde si es importante hacia donde están apuntando los vértices, ya que en digrafos muy grandes, el problema de encontrar caminos entre pares de vértices es demasiado complicado, sólo siguiendo el trazado del dibujo del mismo, de ahí la importancia de este algoritmo y el interés que generó su estudio.
Trabaja sobre grafos orientados, i G es no orientado, se sustituye cada arco, si G es orientado, se dice que el vértice B es alcanzable desde A si existe en G un camino desde A hasta B.
A | B | C | D | |
A | 1 | 0 | 0 | 1 |
B | 0 | 1 | 1 | 1 |
C | 0 | 0 | 1 | 0 |
D | 1 | 0 | 1 | 1 |
Proposición: Hay un camino de largo k desde A hasta B en un grafo G=(V, E) si y sólo si (A,B) Є EK, donde EK es la composición k-ésima de la relación E k veces, siendo E0 la relación identidad.
El algoritmo recibe una matriz de adyacencia que sería el grafo inicial, y regresa una matriz de alcance la cual se agregan aristas indicando si es posible llegar del nodo A al nodo B.
La matriz de alcance indica la existencia de caminos entre pares de nodos.
El algoritmo utilizado para encontrar la clausura transitiva de un grafo dirigido es muy parecido al algoritmo de Floyd_Warshall, con la diferencia que este utiliza las operaciones lógicas Ú y Ù, sustituyendo las aritméticas min y + usadas por Floyd_Warshall, además que rellena la matriz de adyacencia sólo con 0 y 1, a diferencia del otro que les asocia un peso a cada arista que está en el grafo, y si no hay conexión entre los vértices, entonces le asigna ¥.
Generalizando los pasos:
- A los 0 de la matriz de adyacencia los ponemos como infinitos.
- Floyd intenta sacar un camino
- Al final sustituimos costos por 1s e infinitos por 0s.
Algoritmo Propuesto:
transclosure( int adjmat[max][max], int path[max][max])
{
for(i = 0; i < max; i++)
for(j = 0; j < max; j++)
path[i][j] = adjmat[i][j];
for(i = 0;i <max; i++)
for(j = 0;j < max; j++)
if(path[i][j] == 1)
for(k = 0; k < max; k++)
if(path[j][k] == 1)
path[i][k] = 1;
}
{
for(i = 0; i < max; i++)
for(j = 0; j < max; j++)
path[i][j] = adjmat[i][j];
for(i = 0;i <max; i++)
for(j = 0;j < max; j++)
if(path[i][j] == 1)
for(k = 0; k < max; k++)
if(path[j][k] == 1)
path[i][k] = 1;
}
El costo asociado a este algoritmo es de 0(n3), ya que el costo de encontrar la matriz de alcance está íntimamente ligado con los ciclos que se necesitan para recorrer la matriz, además por ser un algoritmo de programación dinámica el costo tiene que ser polinomial.
Una vez aplicado el algoritmo la matriz de alcance del ejemplo sería:
A | B | C | D | |
A | 1 | 0 | 1 | 1 |
B | 1 | 1 | 1 | 1 |
C | 0 | 0 | 1 | 0 |
D | 1 | 0 | 1 | 1 |
A continuación adjunto un archivo con el contenido del reporte con su respectiva codificación en c++.
http://groups.google.com/group/algcomp/web/Proyecto%205%20-%20Transitive%20Closure.zip
Bibliografía:
