En la teoría de grafos surgen varios problemas relacionados con los caminos que existen entre pares de vértices, ya sea, encontrar los caminos más cortos de un grafo (dirigido y no dirigido), ver si el grafo es conexo, etc. En este trabajo hablaremos de la clausura transitiva(o cierre transitivo) de un grafo dirigido, tema que surgió para resolver un problema específico de grafos, pero que tiene aplicaciones en problemas reales.
El concepto de transitividad es el mismo que se utiliza en teoría matemática el cual postula que si "a" es menor a "b" y "b" es menor a c, entonces "a" es menor 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.
La clausura transitiva de una relación binaria es la relación binaria más pequeña que siendo transitiva contiene al conjunto de pares de la relación binaria original.
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}.
Dado el siguiente grafo dirigido, encontrar la clausura transitiva de él:
La clausura transitiva del grafo asociado es:
Algoritmo: El algoritmo utilizado para encontrar la clausura transitiva de un grafo dirigido es muy parecido al algoritmo de Floyd_Warshall, 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. Ahora presentaré el algoritmo propuesto:
Como podemos ver, el algoritmo tiene como entrada el grafo y como salida la matriz de alcance asociada a ese grafo. Desde la línea 1 hasta la 6, lo que hace es completar la matriz de adyacencia del grafo, notar que ésta matriz en la diagonal se le asigna el valor 1, ya que supone que hay un camino desde un vértice a él mismo en la matriz de alcance. Luego desde la línea 7 a la 10 calcula las diferentes matrices, para este proceso va guardando la matriz anterior que es con la que hace el trabajo, la matriz actual sólo sirve para guardar los resultados, el n que se indica es el número de vértices que tiene el grafo, por lo tanto calcula tantas matrices como vértices tiene el grafo. Luego en la línea final(11), retorna la matriz de alcance asociada al grafo, que es la clausura transitiva del grafo.
Ahora veremos cómo trabaja el algoritmo, a través del ejemplo anterior. Teníamos que el grafo era:
El primer paso es completar la matriz de adyacencia del grafo (recordando que la diagonal se rellena con 1), por lo tanto nos queda que:
0- Matriz de Adyacencia, con la diagonal cambiada por uno.
1- Esta matriz indica si existe un camino desde el nodo i al nodo j, pasando por el nodo 1.
2- Esta matriz indica si existe un camino desde el nodo i al nodo j, pasando por el nodo 2.
3- Esta matriz indica si existe un camino desde el nodo i al nodo j, pasando por el nodo 3.
4- Esta es la matriz de alcanze que nos muestra la clausura transitiva del grafo.
El dibujo es:
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.
http://www.slideshare.net/guest4b1d8bc/clausura-transitiva-de-un-grafo-dirigido
Disculpa si entendi tu ejemplo en lo de las matrices pero hace referencia a "i" y "j" pero no supe quienes eran "i" y "j", me podrias decir quienes son?
ResponderEliminarMe hubiera gustado que les contesten a los que preguntan sobre sus blogs...
ResponderEliminar