Algoritmos de Grafos

Tema: Algoritmos de GrafosCatedra: Algoritmos y Complejidad

Mg. Martın M. Perez

Facultad de Ciencias de la AdministracionUniversidad Nacional de Entre Rıos

Noviembre de 2015

Intro Representacion de Grafos Recorridos Camino y Circuito de Euler Bibliografıa

En la clase de hoy: Algoritmos de Grafos

1 Introduccion

2 Representacion de Grafos

3 RecorridosRecorrido en Profundidad: Grafos No Dirigidos

Puntos de ArticulacionRecorrido en Profundidad: Grafos Dirigidos

Grafos Acıclicos: Orden TopologicoRecorrido por Niveles

4 Camino y Circuito de EulerAlgoritmo de Fleury

5 Bibliografıa

Martın Perez (FCAD – UNER) Algoritmos de Grafos Noviembre de 2015 2 / 19


Introduccion

Los grafos son estructuras muy importantes en las cienciasde la computacion. Con ellos se puede encontrar la soluciona una inmensa variedad de problemas.

Hoy veremos tecnicas generales que pueden usarse cuandono se requiere ningun orden particular para visitar cadanodo.



Representacion de Grafos No Dirigidos (GND)

Memoria GND =

{Θ(n2) Matriz de AdyacenciaΘ(n + 2a) = Θ(max(n, a)) Lista de Adyacencia



Representacion de Grafos Dirigidos (GD)

Memoria GD =

{Θ(n2) Matriz de AdyacenciaΘ(n + a) = Θ(max(n, a)) Lista de Adyacencia



Recorridos

Un recorrido es un algoritmo que visita todos los nodos deun grafo.

Los algoritmos mas comunes generalizan las tecnicas pararecorrer arboles:

Pre-ordenIn-ordenPost-orden



Recorridos






Recorridos



Pre-orden

In-ordenPost-orden



Recorridos



Pre-ordenIn-orden

Post-orden



Recorridos






Recorrido en Profundidad: Grafos No Dirigidos

Procedimiento de Recorrido en Profundidad: GND

Se elige un nodo v ∈ N como punto de partida.Se marca el nodo v como visitado.Si hay un nodo no visitado adyacente a v , se elige comonuevo punto de partida.Se sigue el proceso recursivamente, hasta que todos losnodos de G esten marcados.




Ejemplo

Para el siguiente grafo, ¿como procederıa el recorrido enprofundidad?




Ejemplo

1. dfs(1) llamada inicial2. dfs(2) llamada recursiva3. dfs(3) llamada recursiva4. dfs(6) llamada recursiva5. dfs(5) llamada recursiva; se bloquea6. dfs(4) vecino del nodo 1 no visitado7. dfs(7) llamada recursiva8. dfs(8) llamada recursiva; se bloquea9. − no hay mas nodos para visitar




Ejemplo

Arbol de cubrimiento asociado al recorrido




Definiciones

Punto de ArticulacionUn nodo v de un grafo conexo es un punto de articulacionsi el subgrafo obtenido por la eliminacion de v y todos susarcos incidentes deja de ser conexo.

Grafo BiconexoUn grafo G es biconexo si es co-nexo y no tiene puntos de articu-lacion.

Grafo BicoherenteUn grafo G es bicoherente si ca-da punto de articulacion se conec-ta por medio de al menos dos ar-cos a cada componente de los sub-grafos restantes.




Definiciones







Definiciones






Recorrido en Profundidad: Grafos Dirigidos

Procedimiento de Recorrido en Profundidad: GD

El algoritmo es el mismo. La unica diferencia reside en lainterpretacion de la palabra “adyacente”

¿Como procederıa el recorridoen profundidad en este grafodirigido?¿Cuales serıan los arboles decubrimiento resultantes?




Procedimiento de Recorrido en Profundidad: GD

El algoritmo es el mismo. La unica diferencia reside en lainterpretacion de la palabra “adyacente”

¿Como procederıa el recorridoen profundidad en este grafodirigido?¿Cuales serıan los arboles decubrimiento resultantes?




Grafos Acıclicos: Orden Topologico

Los grafos dirigidos acıclicos pueden usarse para repre-sentar muchas relaciones interesantes.

Orden TopologicoEs un listado de los nodos de un GDA donde, si existe un arco (i , j) enel grafo, entonces el nodo i precede al j en la lista.

¿Como se puede adaptar el procedimiento dfs para quemuestre el orden topologico de un grafo?




Grafos Acıclicos: Orden Topologico

Los grafos dirigidos acıclicos pueden usarse para repre-sentar muchas relaciones interesantes.

Orden TopologicoEs un listado de los nodos de un GDA donde, si existe un arco (i , j) enel grafo, entonces el nodo i precede al j en la lista.

¿Como se puede adaptar el procedimiento dfs para quemuestre el orden topologico de un grafo?



Recorrido por Niveles


Cuando una busqueda por niveles llega a cierto nodov , primero visita todos los vecinos de v . Solo entoncescomienza a visitar los nodos mas lejanos.

Para el grafoPaso Nodo Visitado Q

1. 1 2, 3, 42. 2 3, 4, 5, 63. 3 4, 5, 64. 4 5, 6, 7, 85. 5 6, 7, 86. 6 7, 87. 7 88. 8 −





Cuando una busqueda por niveles llega a cierto nodov , primero visita todos los vecinos de v . Solo entoncescomienza a visitar los nodos mas lejanos.

Para el grafoPaso Nodo Visitado Q

1. 1 2, 3, 42. 2 3, 4, 5, 63. 3 4, 5, 64. 4 5, 6, 7, 85. 5 6, 7, 86. 6 7, 87. 7 88. 8 −





Actividades¿Como quedarıa el arbol de cubrimiento generado porel recorrido de la diapositiva anterior?¿Te animas a aplicar el algoritmo de recorrido por ni-veles al grafo dirigido de la Figura 5 de los apuntes declase?En http://visualgo.net/dfsbfs.html se puede ver comoevolucionan los recorridos en profundidad y por niveles,tanto para GD como para GND. ¡A experimentar!


http://visualgo.net/dfsbfs.html


Camino y Circuito de Euler

Un camino de Euler en un GND es un camino donde cadaarco aparece exactamente una vez .

Si el nodo inicial y el final son el mismo nodo, entonces elcamino es un circuito de Euler.

Euler enuncio dos Teoremas:Teorema 1: Existencia de un Camino de Euler.Teorema 2: Existencia de Circuitos de Euler.



Camino y Circuito de Euler

Los puentes de Konigsberg y su grafo asociado

¿Existe en este caso camino y/o circuito de Euler?



Algoritmo de Fleury

Algoritmo de Fleury

Pasos para encontrar caminos de Euler:1 Verificar que el grafo cumpla con las hipotesis de los

teoremas de caminos o circuitos de Euler.2 Elegir un vertice de grado impar. En caso de que no

exista, se puede elegir cualquier vertice.3 En cada paso, recorrer cualquier arco disponible, eli-

giendo un puente o istmo solo cuando no haya alterna-tiva.

4 Al recorrer el arco, borrarlo y continuar el proceso hastaque todos lo vertices tengan grado cero.



Referencias Bibliograficas

Brassard, G. and Bratley, P. (1995).Fundamentals of Algorithmics.Pearson, 1ra. edition.Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009).Introduction to Algorithms.The MIT Press, 3ra. edition.Diestel, R. (2005).Graph Theory.Springer-Verlag Heidelberg, 3ra. edition.


Software

Algoritmos de Grafos