ALGORITMO DE WARSHALL
OBJETIVO
Encontrar
la clausura transitiva de un grafo por medio de las matrices de adyacencia.
Esto mejoraría el método de la matriz de caminos.
Características del algoritmo de warshall
- Es un ejemplo de algoritmo booleano
- Se obtiene una matriz de adyacencia
- Clausura transitiva (Cierre transitivo)
La
clausura transitiva o cierre transitivo
de una relación binaria es encontrar la relación binaria mas pequeña, que
siendo esta transitiva contiene al conjunto de pares de la relación binaria
original .
Conociendo
ya que es una clausura transitiva vamos a hacer un ejemplo paso a paso
Ejemplo
Se tiene un grafo dirigido de cuatro nodos
Se hace una matriz de adyacencia
•Lo siguiente es tomar uno de los nodos,
podemos tomar el
que queramos
•Cuando se
toma como referencia es como si el nodo que
elegimos ya no estuviera
•Volvemos a realizar la matriz de
adyacencia
•Los unos que ya obtuvimos en las
matrices
se mantienen en
la siguiente, no cambian
•Tendremos que hacer este proceso según la cantidad de
nodos que se tenga
•Ahora tomamos como base el nodo b y
hallamos M2
•Como nos podemos dar cuenta el nodo c no
esta
apuntando hacia ningún otro nodo por lo tanto la
M4 va a quedar igual a la
M3
•M4 es la que nos va a permitir ver los
caminos
posibles
•A esta ultima matriz se le conoce como
matriz de
clausura transitiva
BIBLIOGRAFIA
1 comentario:
QUE BUEN BLOG
Publicar un comentario