Date post: | 31-Dec-2015 |
Category: |
Documents |
Upload: | rene-rafael-cordero |
View: | 85 times |
Download: | 1 times |
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Algoritmos y ComplejidadAlgoritmos sobre Grafos
Pablo R. Fillottrani
Depto. Ciencias e Ingeniería de la ComputaciónUniversidad Nacional del Sur
Primer Cuatrimestre 2009
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Algoritmos sobre Grafos
1 Introducción
2 Recorridos
3 Ordenamiento topológico
4 Componentes fuertemente conexos
5 Puntos de articulación y puentes
6 Flujo máximo
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
los grafos constituyen una de las más importantes Estructuras deDatos en las Ciencias de Computación. Un inmensa variedad deproblemas basan su solución en el uso de grafos
en esta materia sólo nos interesaremos en aquellos problemasdónde es posible una representación total del grafo en lamemoria de la máquina
las heurísticas para el manejo de grafos implícitos se ven enInteligencia Artificial
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Representación de grafos
Representación de Grafos
{Matriz de AdyacenciaLista de Adyacencia
los arcos pueden o no tener peso y/o etiquetas
los arcos pueden o no ser dirigidos
se pueden permitir o no varios arcos entre los mismos nodos(multigrafos)
se pueden permitir o no arcos hacia el mismo nodo
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Representación grafos no dirigidos
Memoria
{matriz de adyacencia Θ(n2)lista de adyacencia Θ(n + 2a) = Θ(max(n,a))
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Representación grafos dirigidos
Memoria
{matriz de adyacencia Θ(n2)lista de adyacencia Θ(n + a) = Θ(max(n,a))
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
un recorrido es un algoritmo que visita todos los nodos de ungrafo
supondremos los grafos representados por matrices deadyacencia
los algoritmos más usados para recorrer grafos generalizan losrecorridos de árboles
para el caso de grafo se necesita guardar información sobre losnodos que ya han sido visitados, de modo de no volver avisitarlos
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
para recorrer grafos, se etiquetarán dinámicamente los nodoscomo:
nodos blancos: todavía no han sido visitadosnodos grises: ya han sido visitados, pero no se ha controlado lavisita a todos sus adyacentesnodos negros: ya han sido visitados, al igual que todos susadyacentes
esta caracterización implica que ningún nodo negro tiene unnodo blanco como adyacente
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Recorrido por niveles
el recorrido por niveles, o breadth-first search (BF), basa el ordende visita de los nodos del grafo en una E.D. Cola, incorporándoleen cada paso los adyacentes al nodo actual
esto implica que se visitarán todos los hijos de un nodo antes deproceder con sus demás descendientes
las operaciones sobre la E.D. Cola se suponen implementadasen tiempo Θ(1)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Algoritmo recorrido por niveles
el algoritmo que se presenta a continuación es no determinístico:la elección de los nodos en cada ciclo puede hacerse en formaarbitraria, o dependiente del contexto si es necesario
puede aplicarse tanto a grafos dirigidos y como a no dirigidosestá dividido en dos procedimientos
bfs inicializa las estructuras de datos, inicia el recorrido ycontrola que todos los nodos hayan sido visitadosvisitaBF realiza el recorrido propio a partir de un nodo yaelegido
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
PROCEDURE bfs(G=N,A)FOR cada vértice v en N
color[v]::=blancoENDFORQ.ColaVacía()FOR cada vértice v en N
IF color[v]=blancocolor[v]::=grisQ.insertar(v)visitarBF(G,Q)
ENDIFENDFOR
costo veces
a n
a 1
a na ≤ na ≤ n
TvBF (n) ≤ n
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
PROCEDURE visitarBF(G,Q)WHILE no Q.vacía()
u::=Q.primero()IF existe w adyacente a u
tal que color[w]=blancocolor[w]::=grisQ.insertar(w)
ELSEcolor[u]::=negroQ.sacarDeCola()
ENDIFENDWHILE
costo veces
b ≤ nb ≤ n
b ≤ a×n
b ≤ a×n
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Análisis del tiempo de ejecución
TBF (n) ≤n
∑i=1
(a + TvisitarBF (n)) =n
∑i=1
(a + O(a×n)) ∈ O(n4)
la cota obtenida es muy mala
una análisis más detallado resulta en una cota mejor
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
se puede probar por inducción sobre el número de iteracionesque todo nodo es coloreado blanco, gris y negro exactamente unavez, y en ese ordenque todos los nodos en Q son grises y solamente estan una vezen Qque los controles de adyacencia se hace exactamente una vezpor cada arco.
esto resulta TBF (n) = Θ(max(n,a)), tomando como barómetroslas operaciones sobre la E.D. Cola
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo de BFS (I)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo de BFS (II)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo de BFS (III)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo de BFS (IV)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo de BFS (V)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Propiedades
al mismo tiempo que se hace un recorrido por niveles de un grafose pueden calcular algunos datos adicionales que serán útilespara las aplicaciones de este algoritmo
la foresta del recorrido es el subgrafo de G formado por todos losarcos utilizados en el recorrido
se puede probar que siempre es una foresta (conjunto deárboles)
se representa a través de un arreglo adicional padre[1..n]donde cada nodo guarda su antecesor en la foresta; sipadre[i] = 0 entonces el nodo es una raíz
este arreglo se inicializa en 0
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
el Nivel de cada nodo es la distancia (cantidad de arcos) quedeben recorrerse en la foresta para llegar desde la raíz al nodocorrespondiente
se representa por un arreglo adicional nivel[1..n], inicializadoen 0
se debe recordar que la raíz es en principio un nodo arbitrario
se pueden calcular esta información adicional al mismo tiempoque se hace el recorrido; esto no agrega tiempo adicional alorden del algoritmo
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
PROCEDURE visitarBF(G,Q)WHILE no Q.esVacía()
u::=Q.primero()IF existe w adyacente a u
tal que color[w]=blancocolor[w]::=grispadre[w]::=u; nivel[w]::=nivel[u]+1Q.insertar(w)
ELSEcolor[u]::=negroQ.sacarDeCola()
ENDIFENDWHILE
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
se pueden probar las siguientes propiedades sobre los recorridospor nivel
LemaSi el grafo es conexo, entonces la foresta de recorrido es un árbol
en el caso de un grafo dirigido, conexo significa que existe uncamino de ida y de vuelta entre cada par de nodos
Lema
al finalizar un recorrido BF, nivel[v ] contiene la mínima distanciadesde la raíz del árbol de v en la foresta de recorrido hasta v
ejercicio: comparar con el algoritmo de Dijkstra
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
el recorrido permite clasificar los arcos del grafo en las siguientescategorías:
arcos de la foresta son los arcos (padre[v ],v) utilizados en elrecorridoarcos hacia atrás son arcos (u,v) en donde v es un ancestro deu en la foresta del recorridoarcos hacia adelante son arcos (u,v) en donde v esdescendiente de u en la foresta del recorridoarcos que cruzan son los demás arcos que no entran en las otrascategorías. Los extremos pueden estar en el mismo árbol o enárboles diferentes
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
si el grafo es no dirigido, como cada arco es considerado dosveces esta clasificación puede ser ambigua. Se toma la primerade las categorías posibles según el orden dado
estas categorías pueden calcularse en el mismo algoritmo delrecorrido, sin aumentar el orden del tiempo de ejecución (lademostración queda como ejercicio)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Propiedades
TeoremaSi el grafo es dirigido, entonces un recorrido BF no genera arcos haciaadelante
TeoremaSi el grafo es no dirigido, entonces un recorrido BF no genera arcoshacia atrás ni hacia adelante
las demostraciones se hacen por el absurdo (ejercicio)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Recorrido por profundidad
el recorrido por profundidad, o depth-first search (DF), basa elorden de visita de los nodos del grafo en una E.D. Pila,agregando en cada paso los adyacentes al nodo actual
esto hace que agote los nodos accesibles desde un hijo antes deproceder con sus hermanos
las operaciones sobre la E.D. Pila se suponen de tiempo en Θ(1)
al igual que el recorrido por profundidad, se presenta unalgoritmo no determinístico que puede modificarse para incluir unorden en la elección de los nodos
puede aplicarse tanto a grafos dirigidos como a grafos nodirigidos
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Algoritmo
PROCEDURE dfs(G=N,A)FOR cada vértice v en N
color[v]::=blancoENDFORP.pilaVacía()FOR cada vértice v en N
IF color[v]=blancocolor[v]::=grisP.apilar(v)visitarDF(G,P)
ENDIFENDFOR
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
PROCEDURE visitarDF(G,P)WHILE no P.esVacía()
u::=P.tope()IF existe nodo w adyacente a u
tal que color[w]=blancocolor[w]::=grisP.apilar(w)
ELSEcolor[u]::=negroP.desapilar()
ENDIFENDWHILE
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
en forma análoga al recorrido por niveles, se prueba porinducción que
todo nodo es coloreado blanco, gris y negro exactamente unavez, y en ese ordentodos los nodos en P son grises y solamente estan una vez en Plos controles de adyacencia se hace exactamente una vez porcada arco
resultando en un algoritmo Θ(n + a)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (I)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (II)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (III)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (IV)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (V)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (VI)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (VII)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo (VIII)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Propiedades
al igual que en los recorridos por niveles, es posible obtener laforesta del recorrido de un recorrido por profundidad
en cambio, la numeración nivel[u] no tiene sentido
sí es posible en este tipo de recorrido numerar a los nodos deacuerdo al tiempo del evento de descubrimiento (numeraciónpreorden), o de finalización (numeración postorden)
la numeración en preorden se hace simultáneamente con lacoloración en gris; y se guarda en un arreglo d[1..n]
la numeración en postorden coincide con la colaración en negro;y se guarda en un arreglo f[1..n]
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Cálculo de numeración
PROCEDURE dfs(G=N,A)FOR cada vértice v en N
color[v]::=blancoENDFORP.pilaVacía(); tiempo::=0FOR cada vértice v en N
IF color[v]=blancocolor[v]::=gristiempo++; d[v]::=tiempoP.apilar(v)visitarDF(G,P)
ENDIFENDFOR
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
PROCEDURE visitarDF(G,P)WHILE no P.esVacía()
u::=P.tope()IF existe nodo w adyacente a u
tal que color[w]=blancocolor[w]::=gristiempo++; d[w]::=tiempoP.apilar(w)
ELSEcolor[u]::=negrotiempo++; f[u]::=tiempoP.desapilar()
ENDIFENDWHILE
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Lema
Sea G = 〈N,A〉 un grafo, y d[],f[] la numeración de descubrimiento yfinalización obtenida mediante un recorrido DF. Entonces
(u,v) es un arco de la foresta o hacia adelante si y solo si
d[u] < d[v ] < f[v ] < f[u]
(u,v) es un arco hacia atrás si y solo si
d[v ] < d[u] < f[u] < f[v ]
(u,v) es un arco que cruza si y solo si
d[v ] < f[v ] < d[u] < f[u]
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Ejemplo numeración y arcos
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
muchas propiedades surgen a partir de la información obtenidaen un recorrido DF
TeoremaEn un recorrido DF de un grafo no dirigido G, todos sus arcos son dela foresta o hacia atrás
Demostración.
Sea (u,v) un arco del grafo, y supongamos que u es descubiertoantes que v . Luego v es descubierto y finalizado antes de finalizar u.Si el nodo v tiene como padre a u entonces (u,v) es un arco de laforesta; si el nodo v tiene otro padre, entonces (u,v) es un arco haciaatrás. En forma similar se prueba si v es descubierto antes que u.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Lema
En un recorrido DF de un grafo G, para cualquier par de nodosdistintos u,v vale exactamente uno de:
los intervalos [d[u],f[u]] y [d[v ],f[v ]] son totalmente disjuntos
[d[u],f[u]]⊂ [d[v ],f[v ]] y u es descendiente de v
[d[v ],f[v ]]⊂ [d[u],f[u]] y v es descendiente de u
Demostración.
Analizando caso por caso si d[u] < d[v ] < f[u], d[u] < f[u] < d[v ],d[v ] < d[u] < f[v ] y d[v ] < f[v ] < d[u]
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Corolario (anidamiento de descendientes)
v es un descendiente propio de u en la foresta de recorrido si y solo sid[u] < d[v ] < f[v ] < f[u]
Demostración.Inmediato del lema 7.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Recorrido por NivelesRecorrido por profundidad
Teorema (caminos blancos)
En un recorrido DF de un grafo G, un nodo v es descendiente de unnodo u si y solo si en el momento d[u] cuando u es descubierto existeun camino de u a v que consiste totalmente de nodos blancos.
Demostración.Para el solo si basta con aplicar el teorema 8 a todos los nodosintermedios.Para el si supongamos por el absurdo que v es alcanzable desde upor un camino de nodos blancos en el momento d[u], pero v no esdescendiente de u. Se toma el primer nodo en el camino de u a v queno es descendiente de u, y se demuestra que su intervalo estácontenido en [d[u],f[u]], contradiciendo el teorema 8.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Definición del problema
Problema: dado un grafo dirigido acíclico G, un orden topológicoes un ordenamiento lineal de sus nodos de forma que si el arco(u,v) ∈ G entonces u aparece antes de v en el ordenamiento
si el grafo tiene ciclos, entonces tal ordenamiento no existe
el orden topológico es usado para planificar una serie deacciones que tienen precedencias: cada nodo representa unaacción, y cada arco (u,v) significa que la acción u debeejecutarse necesariamente antes de v
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
la numeración de los nodos en un recorrido DFS da una idea delalgoritmo para resolver el problema
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
PROCEDURE OrdenTopológico(G)array f[1..n]DFS(G,f) % calculando f[v]L::= lista de nodos ordenada
por f en forma decrecienteRETURN L
el tiempo de ejecución de este algoritmo claramente esΘ(n logn), pero es posible reducirlo a Θ(n + a) cambiandolevemente el algoritmo del recorrido (ejercicio)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Correctitud
LemaUn grafo dirigido G es acíclico si y solo si cualquier recorrido DFS deG no produce arcos hacia atrás.
Demostración.El solo si es inmediato. Para el si basta aplicar el teorema 9 al primernodo del ciclo.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
TeoremaEl resultado del algoritmo anterior es un orden topológico.
Demostración.
Basta con mostrar que para todo arco (u,v) en G dirigido acíclico,f [v ] < f [u].
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Definición del problema
dado un grafo dirigido G = 〈N,A〉 un componente fuertementeconexo (CFC) es un conjunto U ⊆ N maximal tal que para todou,v ∈ U valen u G v y v G u (donde a G b significa queexiste en G un camino de a a b)
Problema: encontrar todos los CFC de un grafo dirigido G
para el caso de grafos no dirigidos, el problema se denominacomponentes conexos y puede resolverse directamente a partirde cualquiera de los recorridos vistos
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
sea G un grafo, su grafo traspuesto GT se define comoGT = 〈N,{(u,v) : (v ,u) ∈ A}〉es interesante observar que G y GT tienen los mismos CFC(ejercicio)
el algoritmo para CFC hace dos recorridos: uno del grafo G y otrodel grafo GT
en el segundo recorrido, los nodos se consideran en ordendecreciente de f[]
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
PROCEDURE CFC(G)array f[1..n]DFS(G,f)calcular GT % el traspuesto de Garray padre[1..n]DFS(GT, padre, f)
% padre es la foresta del recorrido,% tomando los nodos por f decreciente
RETURN padre
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
cada Árbol de la foresta representado en padre contieneexactamente los elementos de un CFC
suponiendo una representación del grafo mediante lista deadyacencia, el tiempo y espacio del algoritmo anterior es deΘ(n + a) (ejercicio)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Ejemplo
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Correctitud
para demostrar la correctitud del algoritmo, se usará el conceptode grafo de componentes GCFC = 〈NCFC ,ACFC〉 que estáformado por un nodo que representa a cada componentefuertemente conexo en G, y para cada par de CFC u,v seagrega un arco (u,v) si en G existe en el componente u un nodoque presenta un arco hacia otro nodo en el componente v
la principal propiedad de GCFC es que siempre se trata de un dag(ejercicio)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Lema
Sean u,v ∈ NCFC entonces la existencia de (u,v) ∈ ACFC implica que(v ,u) 6∈ ACFC
Demostración.Si existen los dos arcos, entonces u y v serían el mismo CFC enG.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
se extiende la numeración de descubrimiento y finalización paraconjuntos de nodos de la forma:
d[C] = minu∈C(d[u])
f[C] = maxu∈C(f[u])
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Lema
Sean u,v ∈ NCFC tal que (u,v) ∈ ACFC . Entonces f[u] > f[v ].
Demostración.Se distinguen dos casos de acuerdo a cual componente u o v esencontrado primero en el primer recorrido. Si primero se encuentra uentonces v es descendiente de u.Si primero se encuentra v , dado queexiste (u,v) entonces no existe (v ,u) por el lema 12. Esto significaque en el momento f[v ] todos los nodos en u son blancos, por lo quef[u] > f[v ].
Corolario
Sea C,C′ dos CFC distintos de un grafo G = 〈N,A〉, entonces siexiste (u,v) ∈ AT tal que u ∈ C y v ∈ C′ vale que f[C] < f[C′].
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
TeoremaEl algoritmo calcula correctamente los CFC de cualquier grafo G.
Demostración.Por inducción sobre la cantidad de árboles en la foresta del segundorecorrido. Para el caso inductivo se muestra que si u es la raíz delk -ésimo árbol del segundo recorrido, entonces todos los nodos delCFC de u pertenecen a ese árbol. Además, por el corolario 13cualquier arco que toca el CFC de u debe ser tal que conecta undescendiente de u con un nodo en un árbol anterior en la foresta.Luego el árbol con raíz u contiene exactamente el CFC de u.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Definición del problema
sea G no dirigido, conexo. Un punto de articulación es un nodode G cuya eliminación (junto con todos sus arcos incidentes) dejaal grafo resultante disconexo
un puente es un arco de G cuya eliminación deja al graforesultante disconexo
Problema: dado un grafo no dirigido conexo G = 〈N,A〉 encontrartodos sus puntos de articulación
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
se pueden determinar los puntos de articulación mediante unsolo recorrido DFS de G
los siguientes resultados permiten definir el algoritmo
LemaSea G un grafo no dirigido conexo, y consideremos n ∈ N el nodoinicial de un recorrido DF. Entonces n es un punto de articulación si ysolo tiene al menos dos hijos.
Demostración.Es claro el si. Para el solo si, sean n1,n2 dos descendientes de n. Si nno fuera punto de articulación existiría un camino blanco entre n1 y n2
en el momento de visitar el primero de ellos, con lo que el segundosería descendiente del primero.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
LemaSea G un grafo no dirigido conexo, y consideremos n ∈ N un nodo noinicial en un recorrido DF. Entonces n ∈ N es punto de articulación si ysolo existe un hijo u de n tal que ningún descendiente v de u tiene unarco (v ,w) donde w es ancestro propio de n.
Demostración.Es claro que si n es punto de articulación entonces tal arco no puedeexistir. Para el solo si, suponemos que existe u hijo de n tal queninguno de sus descendientes v tiene un arco hacia un ancestropropio w de n. Entonces, removiendo n del grafo no existe ningúncamino posible de u a w , por lo que n es punto de articulación.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
de acuerdo al lema anterior, para saber si un nodo n es un puntode articulación es suficiente con verificar si se puede acceder aun ancestro propio desde un descendiente de n por un arco fuerade la foresta
teniendo en cuenta la numeración de descubrimiento generadapor un recorrido DFS, se puede computar para cada nodo elancestro más viejo que se alcanza a través de arcos hacia atrás
masviejo[v ] = min
d[v ]d[w ] : (v ,w) es un arco hacia atrásmasviejo[w ] : (v ,w) es un arco
de la foresta
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
PROCEDURE PuntosArticulación(G)array d[1..n], masviejo[1..n], pa[1..n]DFS(G,d)calcular masviejo en otro recorrido DFS de Gpa[1]::= tiene más de un hijo en la forestaFOR cada v en N-{1}
pa[v]::= existe un hijo u de vtal que d[v]<=masviejo[u]
ENDFORRETURN pa
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
el tiempo de ejecución es de Θ(a) (dos recorridos más unaiteración sobre todos los nodos)
se podrían mejorar las constantes realizando el cálculo completoen un sólo recorrido (ejercicio)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Puentes
para determinar los puentes es útil la siguiente propiedad
Lema
Sea G = 〈N,A〉 un grafo no dirigido. Un arco (u,v) ∈ A es un puenteen G si y solo si (u,v) no pertenece a ningún ciclo simple en G.
Demostración.
⇒): entonces removiendo (u,v) existiría un otro camino de u a v , conlo que el grafo resultante sería conexo, contradiciendo el hecho deque es puente. ⇐): luego el grafo obtenido removiendo (u,v) esconexo por lo que existe un camino de u a v que no use (u,v).Tomando ese camino más (u,v) se forma un ciclo simple, con lo seobtiene una contradicción.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
se puede obtener entonces un algoritmo en tiempo O(a) queencuentre los puentes, a partir de un recorrido DF del grafo
ejercicio: especificar un algoritmo para encontrar los puentes enun sólo recorrido del grafo
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Definición del problema
una red de flujo es un grafo dirigido G = 〈N,A〉 donde cada arco(u,v) ∈ A tiene asociado una capacidad c(u,v)≥ 0, y sedistinguen dos nodos s y t llamados fuente y destino, tal queningún arco llega a la fuente, o sale del destino
además, por conveniencia, si (u,v) 6∈ A entonces se suponec(u,v) = 0
también que para todo n ∈ N, s G n G t
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
un flujo en G es una función f : N×N −→ R que satisface:restricción de capacidad: f (u,v)≤ c(u,v) para todo u,v ∈ Nsimetría oblicua: f (u,v) =−f (v ,u) para todo u,v ∈ Nconservación de flujo: ∑v∈N−{s,t} f (u,v) = 0
el valor de un flujo |f | se define como|f |= ∑v∈N f (s,v) = ∑v∈N f (v , t).
Problema: dada una red de flujo G, el problema MAXFLUJOconsiste en encontrar el máximo flujo que admite G
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Ejemplo de flujo
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
en el flujo sólo se representan los valores positivos
también se cancelaran flujos opuestos entre dos nodos, de formaque el flujo representado sea positivo en a lo sumo uno de lossentidos
se supondrá que todas las capacidades son enteros
si las capacidades son racionales, se pueden escalar para quese consideren enteros
también usaremos en la notación la sumatoria implícita,
f (U,V ) = ∑x∈U
∑y∈V
f (x ,y)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Propiedades
LemaSea G una red de flujo, y f un flujo en G. Entonces valen:
para todo X ⊆ N, f (X ,X) = 0
para todo X ,Y ⊆ N, f (X ,Y ) =−f (Y ,X)
para todo X ,Y ,Z ⊆ N tal que X ∩Y = /0, valenf (X ∪Y ,Z ) = f (X ,Z ) + f (Y ,Z ) yf (Z ,X ∪Y ) = f (Z ,X) + f (Z ,Y )
Demostración.ejercicio, usando las propiedades de flujo
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Corolario
| f |= f (V , t)
Demostración.
| f |= f (s,V ) = f (V ,V )− f (V −s,V ) =−f (V −s,V ) = f (V ,V −s) =f (V , t) + f (V ,V − s− t) = f (V , t)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Método de Ford-Fulkerson
el método de Ford-Fulkerson permite resolver el problemaMAXFLUJO
lo llamamos método porque produce distintos algoritmos, condistintos tiempos de ejecución de acuerdo a la implementación
se basa en los conceptos de red residual, camino de aumento, ycorte
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Red residual
sea G una red de flujo, y f un flujo sobre G. Una red residual esun grafo Gf = 〈N,Ef 〉, donde los arcos sonEf = {(u,v) : c(u,v)− f (u,v) > 0} y la capacidad esprecisamente c(u,v)− f (u,v)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Lema
Sea G una red de flujo, f un flujo sobre G, Gf la red residual y f ′ unflujo sobre Gf . Entonces el flujo sum f + f ′, definido(f + f ′)(u,v) = f (u,v) + f ′(u,v), es un flujo en G tal que| f + f ′ |=| f |+ | f ′ |.
Demostración.Se debe verificar que cumple con las tres propiedades de flujo, y quesu valor es exactamente la suma de los valores de f y f ′ (ejercicio).
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Camino de aumento
sea G una red de flujo, y f un flujo sobre G. Un camino deaumento es un camino s Gf t en la red residual Gf
la capacidad residual de s Gf t es la mínima capacidad de losarcos que pertenecen al camino, y se nota cf (p)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Lema
Sea G una red de flujo, f un flujo sobre G y p un camino de aumentoen Gf . Entonces existe un flujo fp definido
fp(u,v) =
cf (p) si (u,v) está en p−cf (p) si (v ,u) está en p
0 sino
con valor | fp |= cf (p) > 0.
Demostración.Es suficiente con probar las tres propiedades de flujo, y verificar elvalor de fp.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Corte de una red de flujo
G una red de flujo, y f un flujo sobre G. Un corte es una particiónde N en S y T = N−S tal que s ∈ S y t ∈ T
el flujo neto a través el corte (S,T ) es f (S,T ). La capacidad deun corte (S,T ) es c(S,T )
el corte mínimo de una red es un corte cuya capacidad esmínima entre todos los cortes
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Teorema (Máximo flujo, mínimo corte)
Sea G una red de flujo, y f un flujo en G. Entonces son equivalentes:1 f es un flujo máximo de G2 la red residual Gf no contiene caminos de aumento3 | f |= c(S,T ) para algún corte (S,T ) de G
Demostración.1)⇒ 2): si f es el máximo flujo y Gf tiene camino de aumento p existeun flujo fp (lema 22) y f + fp es un flujo en G de mayor valor que f .2)⇒ 3): entonces sea S = {v ∈ N : s Gf v} y T = N−S. Se puedever que (S,T ) es un corte y que | f |= f (S,T ) = c(S,T ). 3)⇒ 1):para todos los cortes (S,T ) se puede ver que | f |≤ c(S,T ). Luego| f |= c(S,T ) implica que f es un flujo máximo.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Algoritmo
el teorema anterior permite definir un algoritmo iterativo, a partirde un flujo nulo, que compute el flujo máximo de una red de flujo
se denomina Ford-Fulkerson, y en cada iteración encuentra uncamino de aumento, obtiene el flujo de ese camino y se lo sumaal flujo anterior, resultando en un flujo con valor mayor
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
PROCEDURE FordFulkerson (G,s,t,c)FOR cada arco (u,v) en A
f[u,v]::=0; f[v,u]::=0ENDFORWHILE existe un camino de aumento p en Gf
cf(p)::=min{(c[u,v]-f[u,v])para todo (u,v) en p}
FOR cada arco (u,v) en pf[u,v]::=f[u,v]+c_f(p)f[v,u]::=-f[u,v]
ENDFORENDWHILERETURN f
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Ejemplo (I)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Ejemplo (II)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Ejemplo (III)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Ejemplo (IV)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Ejemplo (V)
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Análisis del tiempo de ejecución
PROCEDURE FordFulkerson (G,s,t,c)FOR cada arco (u,v) en A
f[u,v]::=0; f[v,u]::=0ENDFORWHILE existe un camino de
aumento p en Gfcf(p)::= capacidad mínima de pFOR cada arco (u,v) en p
f[u,v]::=f[u,v]+cf(p)f[v,u]::=-f[u,v]
ENDFORENDWHILE; RETURN f
costo veces
b a
Θ(n + a) O(|f ∗|)
O(a) O(|f ∗|)
b O(a|f ∗|)b O(a|f ∗|)
f ∗ es el resultado
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
la dependencia del tiempo de ejecución en el valor del flujo, y noen la longitud de su representación, no es bueno
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Algoritmo de Edmonds-Karp
el algoritmo de Edmonds-Karp es una instancia del método deFord-Fulkerson en donde la búsqueda del camino de aumento pse hace mediante una búsqueda por niveles comenzando por s
el recorrido por niveles permite encontrar los caminos mínimos(en cuanto a cantidad de arcos) desde el origen a cada nodo
entonces en la red residual, el camino mínimo ya no existe. Estopermite ajustar la cantidad de iteraciones del ciclo WHILE
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
Lema
En el algoritmo EK, si v ∈ N−{s, t} entonces la distancia mínimanivel[v ] en la red residual Gf aumenta con cada aumento de flujo.
Demostración.Sea v el nodo con menor nivel de todos los w tal queniveli [w ] > niveli+1[w ], y s fi+1 u→ v el camino mínimo queredujo el nivel de v . Sabemos que niveli+1[u] = niveli+1[v ]−1 yque niveli+1[u]≥ niveli [u] (por la elección de v ). Se deduce que(u,v) 6∈ Efi y (u,v) ∈ Efi+1 , y como el camino de aumento es elcamino más corto (por el algoritmo), entonces (v ,u) pertenece alcamino de aumento en la iteración i + 1. Luegoniveli [v ] = niveli [u]−1≤ niveli+1[u]−1 = niveli+1[v ]−2lo que contradice la disminución de la distancia mínima.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
TeoremaEl número total de iteraciones del algoritmo EK en una red de flujoG = 〈N,A〉 es a lo sumo O(na).
Demostración.
Primero se muestra que la cantidad de veces que cada arco (u,v)puede ser crítico (ie coincide con la capacidad residual) es n/2−1veces. Sea i la iteración donde (u,v) es arco crítico, y j la iteracióndonde (v ,u) es arco crítico. Entoncesniveli [u] = niveli [v ] + 1≤ nivelj [v ] + 1 = nivelj [v ] + 2, conlo que la distancia mínima disminuye al menos en 2 entre cada parade iteraciones donde (u,v) es arco crítico. Y (n−2) es una cota de lamáxima distancia mínima. Entonces como hay O(a) arcos posibles aser arcos críticos, no puede haber más de O(na) iteraciones.
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
como cada iteración (construir el grafo residual, hacer el recorridoBFS, encontrar el camino de aumento y la capacidad residual, yactualizar el flujo) del algoritmo EK toma de O(a), de acuerdo alteorema anterior el tiempo total de ejecución es de O(na2)
se elimina de esta forma la dependencia del tiempo de ejecuciónen f ∗
existen algoritmos asintóticamente mejores (O(n2a), O(n3)) parael mismo problema
Pablo R. Fillottrani Algoritmos y Complejidad
IntroducciónRecorridos
Ordenamiento topológicoComponentes fuertemente conexos
Puntos de articulación y puentesFlujo máximo
Red residualCamino de aumentoCorteMétodo de Ford-Fulkerson
otras variantes del problema de máximo flujo se pueden reducir ala versión analizada. Por ejemplo, si se tienen múltiples orígeneso destinos
Pablo R. Fillottrani Algoritmos y Complejidad