Programación 3: Ordenación topológica, matriz de caminos y algoritmo Warshall

Esta presentación le pertenece a Christian Paul Salinas
Introducción
Ordenación Topológica
Relación de Precedencia
Grafo Dirigido Aciclico
Complejidad
Pasos
Implementación del algoritmo de ordenación topológica(Ejemplo en Java)
Matriz de caminos, Algoritmo de Warshall
Matriz Cierre Transitivo
Complejidad
Ejemplo Paso a paso, e Implementación del algoritmo en Java

1. Facultad de Ingenieria Capitulo 16: Grafos , algoritmos Fundamentales Realizado por : Christian Paul Salinas 4to Ciclo – Ingeniería en Sistemas

2. Contenido Introducción Ordenación Topológica Relación de Precedencia Grafo Dirigido Aciclico Complejidad Pasos Implementación del algoritmo de ordenación topológica(Ejemplo en Java) Matriz de caminos, Algoritmo de Warshall Matriz Cierre Transitivo Complejidad Ejemplo Paso a paso, e Implementación del algoritmo en Java

3. Introducción Los grafos nos permiten modelar numerosos problemas, por ejemplo, encontrar rutas de menor longitud entre dos puntos, calcular caminos mas rápidos, planificar tareas que completan un proyecto, entre otras. Analizar cada arista y nodo del grafo que representa el problema,

4. Ordenación Topológica Modela las relaciones que existen entre diferentes tareas, para poder terminar un proyecto. Relaciones de Precedencia Se presentan mediante un grafo dirigido, donde los vértices son tareas y existe aristas de un vértice a otro, donde es necesario que se completa la arista inicial para que comience la siguiente

5. Relaciones de Precedencia Una vez se dispone del grafo interesa obtener una planificación de las tareas que constituyen el proyecto . En definitiva, se debe encontrar la ordenación topológica de los vértices que forman el grafo, siendo el final un grafo dirigido. Grafo final acíclico, única dependencia.

6. Importante La ordenación topológica se aplica sobre grafos dirigidos sin ciclos. Es una ordenación lineal tal que si un nodo llamando A es anterior a otro nodo B entonces existe un camino de A hacia B La ordenación topológica no se puede realizar en grafos con ciclos

7. Grafo dirigido Aciclico Un grafo dirigido y sin ciclos se denomina un gda o grafo acíclico. Los gda aparecen en modelos donde no tiene sentido que un vértice tenga un camino directo a él mismo Los grafos dirigidos aciclicos pueden utilizarse para modelar muchos tipos diferentes de información las cuales pueden ser una colección de las tareas que pueden ordenarse en una secuencia determinada.

8. El grafo anterior es un ejemplo de un grafo dirigido acíclico , donde se modela la estructura de prerrequisito de 8 cursos Un arista cualquiera (R,S) significa que el curso R debe completarse antes de empezar el curso S. Por ejemplo, el curso M21 se puede empezar sólo cuando se terminen los cursos E11 y T12. M21 es el paso que sigue o sucesor de E11 y T12

9. Una ordenación topológica de estos cursos es cualquier secuencia de cursos que cumple los prerrequisitos y tenga los pasos sucesores correctos. Para un grafo dirigido acíclico no tiene por qué existir una única ordenación topológica E11 - T12 - M21 - C22 - R23 - S31 - S32 - T41 T12 - E11 - R23 - C22 - M21 - S31 - S32 - T41

10. ordenación topológica Complejidad La complejidad del algoritmo O rdenación T opológica de un grafo. Representación del grafo con Listas de A dyacencia , es O( a+n ), siendo ‘ a ’ el número de arcos y ‘ n ’ el de vértices. R epresentación del grafo con una Matriz de Adyacencia , la complejidad es O(n2 ) .

11. Algoritmo de una ordenación topológica Pasos: Busca una tarea ( vértice V) la cual no tenga Sucesores. Este vértice V pasa a formar parte de la Ordenación T. Ya que el vértice que no tiene sucesores se añadió a la Ordenación T, este vértice es eliminado del grafo inicial. Se repite el proceso. Se toma otro vértice W, que no tenga sucesores. Se incorpora a la Ordenación T. Se eliminan el vértice W del grafo anterior. Se repite el proceso . Se sigue hasta completar la Ordenación. En el próximo ejemplo de utiliza un array para guardar la Ordenación T. Cada vez que se encuentre un vértice que no tenga sucesores, se agrega desde el final del array hasta el principio .

12. Algoritmo de Ordenación Topológica con un grafo representado por su matriz de Adyacencia

13. I mplementación del algoritmo de ordenación topológica Para representar el siguiente grafo se utilizara una Matriz de Adyacencia, y aplicar el Algoritmo de Ordenación Topológica C F D B E A H G

14. Matriz de Caminos: Algoritmo de Warshall Normalmente se suele confundir este Algoritmo con el Algoritmo de Floyd Warshall Floy Warshall encuentra el camino mínimo de grafos dirigidos ponderados Algoritmo de Warshall trabaja sobre grafos dirigidos no ponderados, y encuentra caminos entre un par de vértices

15. Matriz de Caminos: Algoritmo de Warshall Recibe una matriz de Adyacencia de un grafo de n vértices y retorna la matriz de caminos llamada Cierre Transitivo. La estrategia que sigue el algoritmo consiste en definir, a nivel lógico, una secuencia de matrices n-cuadradas P0, P1, P2, P3 ... P n A cada nodo del grafo lo convierte en un ‘’puente’’ para comunicar las diferentes aristas.

16. Algoritmo de Warshall El nodo puente mencionado ayudara a encontrar caminos mediante el mismo e ira aumentado los caminos posible según se acaben los nodos. El nodo seleccionado para cada conexión mediante un puente, se lo define como nodo de orden k Los elementos de cada una de las matrices Pk [ i,j ] tienen el valor 0 si no hay camino y 1 si existe un camino del vértice i y al j .

17. 1 - Si existe un arco del vértice i al j 0 - En otro caso P k=0 1 - Si existe un camino simple de i a j que no pasa por ningún otro vértice a no ser por los vértices creados en P k=0 0 - En otro caso P k=1 1 - Si existe un camino simple de i a j que no pasa por ningún otro vértice a no ser por los vértices creados en P k=1 y P k=0 0 - En otro caso P k=2 1 - Si existe un camino simple de i a j que no pasa por ningún otro vértice a no ser por el vértice creado en P k=0 , P k=1 y P k=2 0 - En otro caso P k=3 k = 0, 1, 2, 3……n (Numero de vértices)

18. Representación de un Grafo por Matriz y Lista de Adyacencia Matriz de Adyacencia

19. Matriz de Adyacencia

20. Lista de Adyacencia

21. Lista de Adyacencia

22. Algoritmo de Warshall

23. Algoritmo de Warshall Complejidad La complejidad del algoritmo de Warshall es cúbica , O(n3) siendo n el número de vértices . Esta característica hace que el tiempo de ejecución crezca rápidamente para grafos con, relativamente, muchos nodos.

24. Ejemplo e Implementación en Java Se tiene el siguiente grafo dirigido no ponderado con su respectiva matriz adyacente, Matriz Adyacente Se mostrara paso a paso cual es el procedimiento ah seguir en este Algoritmo para entenderlo mejor y después su implementación en Java   A B C D E F A 1 1 B 1 C 1 D 1 1 E F A B C D F E

25. Algoritmo de Warshall A B C D F E   A B C D E F A 1 1 B 1 C 1 D 1 1 E F   A B C D E F A 1 1 B 1 C 1 D 1 1 E F Se realiza una matriz con k=0, en esta caso será el vértice A el cual servirá como puente Cuando exista dos números 1 en la fila y columna amarilla, en este caso k=0 (Vértice A), que una ambos vértices por el puente amarillo, se pondrá 1 donde exista un camino y 0 caso contrario. k= 0

26. Algoritmo de Warshall A B C D F E Se realiza una matriz con k=1, en esta caso será el vértice B el cual servirá como puente Cuando exista dos números 1 en la fila y columna amarilla, que una ambos vértices por el puente amarillo, se pondrá 1 donde exista un camino y 0 caso contrario. k= 1   A B C D E F A 1 1 B 1 C 1 D 1 1 E F   A B C D E F A 1 1 1 B 1 C 1 1 D 1 1 E F

27. Algoritmo de Warshall A B C D F E Se realiza una matriz con k=2, en esta caso será el vértice C el cual servirá como puente Cuando exista dos números 1 en la fila y columna amarilla, que una ambos vértices por el puente amarillo, se pondrá 1 donde exista un camino y 0 caso contrario. k= 2   A B C D E F A 1 1 1 B 1 C 1 1 D 1 1 E F   A B C D E F A 1 1 1 B 1 C 1 1 D 1 1 1 1 E F

28. Algoritmo de Warshall A B C D F E Se realiza una matriz con k=3, en esta caso será el vértice D el cual servirá como puente Cuando exista dos números 1 en la fila y columna amarilla, que una ambos vértices por el puente amarillo, se pondrá 1 donde exista un camino y 0 caso contrario. k= 3   A B C D E F A 1 1 1 B 1 C 1 1 D 1 1 1 1 E F   A B C D E F A 1 1 1 1 1 B 1 1 1 1 C 1 1 1 1 D 1 1 1 1 E F

29. Algoritmo de Warshall A B C D F E Se realiza una matriz con k=4, en esta caso será el vértice E el cual servirá como puente Cuando exista dos números 1 en la fila y columna amarilla, que una ambos vértices por el puente amarillo, se pondrá 1 donde exista un camino y 0 caso contrario. k= 4   A B C D E F A 1 1 1 1 1 B 1 1 1 1 C 1 1 1 1 D 1 1 1 1 E F   A B C D E F A 1 1 1 1 1 B 1 1 1 1 C 1 1 1 1 D 1 1 1 1 E F

30. Algoritmo de Warshall A B C D F E Se realiza una matriz con k=5, en esta caso será el vértice F el cual servirá como puente Cuando exista dos números 1 en la fila y columna amarilla, que una ambos vértices por el puente amarillo, se pondrá 1 donde exista un camino y 0 caso contrario. k= 5   A B C D E F A 1 1 1 1 1 B 1 1 1 1 C 1 1 1 1 D 1 1 1 1 E F   A B C D E F A 1 1 1 1 1 B 1 1 1 1 C 1 1 1 1 D 1 1 1 1 E F

31. Algoritmo de Warshall, Matriz de Caminos A B C D F E   A B C D E F A 1 1 1 1 1 B 1 1 1 1 C 1 1 1 1 D 1 1 1 1 E F Matriz de Caminos A B C D F E   A B C D E F A 1 1 B 1 C 1 D 1 1 E F Matriz de Adyacencia

32. Conclusiones En la Ordenación T opológica se tiene relaciones de precedencia que se representan mediante un grafo dirigido en el que los vértices son las tareas o hitos y existe una arista del vértice r al t si el inicio de la tarea t depende de la terminación de r. Una vez se dispone del grafo interesa obtener una planificación de las tareas que constituyen el proyecto; en definitiva, encontrar la ordenación topológica de los vértices que forman el grafo. Algoritmo de Warshall devuelve una matriz de Camino, llamada de Cierre Transitivo, la cual indica TODOS los caminos posible de un vértice a otro, aun así pasando por otros vértices, siempre y cuando se respete el sentido cuando es un grafo dirigido