Flujo Mximo
Training Camp Argentina 2013
Nicols lvarez
naa [at] cs uns edu ar
Idea
Idea
Idea
Idea
Un source s
Un sink t
Nodos intermedios
Arcos dirigidos con una capacidad dada
Objetivo: Enviar el mximo flujo posible de
s a t, cumpliendo las restricciones de
capacidad.
Definicin: Red de Flujo
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.
Se distinguen dos nodos s y t llamados fuente y
destino, tal que ningn arco llega a la fuente o
sale del destino.
Adems, por conveniencia, si (u,v)A entonces
se supone c(u,v) = 0
Tambin que para todo u, existe un camino
S ---> u ---> T
Definicin: Flujo
Un ujo en G es una funcin f : N x N -> R que
satisface:
restriccin de capacidad:
f(u,v) <= c(u,v) para todo u,v N.
simetra oblicua:
f(u,v) = -f(v,u) para todo u,v N
conservacin de ujo:
Para todo u N - {s,t}
v N f(u,v) = 0
Definicin: Problema Flujo Mximo
El valor de un ujo | f | se dene como
| f | = v N f(s,v) = v N f(v,t)
Dada una red de ujo G, el Problema de
Flujo Mximo consiste en encontrar el ujo
de mximo valor que admite G
Repaso
Mtodo de Ford-Fulkerson
Es un mtodo general, no un algoritmo
especfico.
Se basa en 3 conceptos claves:
redes residuales
caminos de aumento
cortes
Mtodo de Ford-Fulkerson
El mtodo comienza con una red de flujo vaca.
En cada iteracin se busca un camino de
aumento en la red residual para incrementar el
valor del flujo.
Se puede demostrar mediante el teorema de
max-flow min-cut que, cuando termina, el flujo
obtenido es mximo
Redes residuales
Intuitivamente, la red residual es una nueva red
de flujo que representa cmo podemos
cambiar el flujo.
Formalmente, la red residual de G = <N,A> es
Gf = <N,Af>, donde las capacidades de los
arcos estn dadas por:
cf(u,v) = c(u,v) - f(u,v)
Caminos de aumento
Como vimos, dada una red de flujo G = <N,A>
y un flujo f, podemos obtener una red residual
Gf
Un camino de aumento es, sencillamente, un
camino simple de s a t en la red residual.
Si existe un camino de aumento en la red
residual, el flujo puede aumentarse a lo largo
de dicho camino con un valor igual a la menor
capacidad de los arcos del camino.
Aumento de flujo
Cortes
Dada una red de flujo G = <N,A>. Un corte es
una particin de N en S y T = N-S tal que s S
y t T.
Dado un corte (S,T).
El flujo neto a travs del corte es:
f(S,T) = u S v T f(u,v) - u S v T f(v,u)
Y la capacidad del corte es:
c(S,T) = u S v T c(u,v)
Cortes
Teorema max-flow min-cut
Los 3 siguientes condiciones son equivalentes:
1. f es un flujo mximo
2. La red residual Gf no contiene caminos de aumentos
3. | f | = c(S,T) para algn corte (S,T) de G
Este teorema prueba que el mtodo de FordFulkerson es correcto.
Max-flow min-cut: Demostracin
1 => 2
Si el flujo es mximo entonces no pueden
existir caminos de aumento. De otro modo,
sera posible aumentar el valor del flujo
2 => 3
Si no existen caminos de aumento en la red
residual, s y t estn desconectados. Por lo
tanto si S es el conjunto de los nodos
alcanzables desde s y T = N - S. El corte (S,T)
est saturado
Max-flow min-cut: Demostracin
3 => 1
Se puede observar que todo flujo tiene un valor
menor o igual que la capacidad de cualquier
corte. Es decir, todo corte implica una cota
superior al valor de un flujo vlido.
Si el flujo satura algn corte (S,T), esto quiere
decir que el flujo tiene el mximo valor posible.
Adems, el corte (S,T) es el corte de capacidad
mnima (o min-cut) de la red de flujo.
Ford-Fulkerson: Pseudo-cdigo
FORD-FULKERSON(G, s, t):
para cada arco (u,v) G.E:
(u,v).f = 0
mientras exista camino de aumento p en Gf:
cf(p) = min {cf(u,v) : (u,v) P}
para cada arco (u,v) p:
(u,v).f += cf(p)
(v,u).f -= cf(p)
Algoritmo de Edmonds-Karp
Algoritmo de Edmonds-Karp
Como se vi en la figura anterior, si no elegimos los
caminos de aumento de manera inteligente el tiempo de
ejecucin puede no estar acotado polinomialmente sobre el
tamao de la entrada.
Afortunadamente, si buscamos el camino de aumento ms
corto con un BFS, se puede demostrar una cota polinomial:
O(m2n)
Esta implementacin de Ford-Fulkerson recibe el nombre
de algoritmo de Edmonds-Karp
Problemas
Hooligans - Regional Latinoamrica 2009
goo.gl/3EoOPO
Dado un torneo entre N <= 40 equipos, dnde
juegan todos contra todos durante M <= 4
rondas y algunos partidos ya jugados. Donde
en cada partido se reparten 2 puntos (2 para el
ganador, 1 si hay empate y 0 para el perdedor).
Determinar si un cierto equipo puede salir
campen.
Problemas
Optimal Marks - SPOJ
goo.gl/X4fX5Q
Dado un grafo no dirigido donde algunos nodos
tienen asignado un nmero de 31 bits. La tarea
es asignar nmeros al resto de los nodos de
manera que la suma de los xor de nodos
adyacentes sea mnima. O sea, para todo (u,v)
G, minimizar (u,v) marca(u) ^ marca(v)
Bipartite Matching
Existen problemas combinatorios que, en
principio, parecen no guardar relacin con el
problema de Flujo Mximo pero que pueden
ser reducidos a ste.
Uno de los ejemplos ms conocidos es el
problema del matching bipartito.
Bipartite Matching
Dado un grafo G = <N,A>, un matching es un
subconjunto M A tal que para todo vrtice
v M existe a lo sumo un arco de M incidente
a v.
Se puede pensar como un "apareamiento" de
los nodos, en los que cada nodo se aparea con
a lo sumo un nodo, y la relacin es simtrica.
Bipartite Matching
El problema de Maximum Matching consiste en
encontrar un matching vlido de mxima
cardinalidad en un grafo.
Este problema resulta ms sencillo para una
clase restringida de grafos llamados grafos
bipartitos.
Grafo bipartito
Un grafo bipartito es un grafo G = <N,A> donde
el conjunto de nodos N puede ser particionado
en 2 conjuntos N = L R donde L y R son
disjuntos y los arcos unen nodos entre L y R.
El problema de hallar un matching mximo en
un grafo bipartito se conoce como maximum
bipartite matching.
Maximum bipartite matching
Este problema puede reducirse a un problema
de flujo mximo.
Para ello, construimos una red de flujo donde
se agregan 2 nodos: un source s y un sink t.
Se agrega un arco de capacidad 1 entre el
source y cada nodo de L y se agrega un arco
de capacidad 1 entre cada nodo de R y el sink.
Maximum bipartite matching
Problemas
Rook Attack - Topcoder. TCO Semifinal R4
http://goo.gl/Aoe4gW
Dado un tablero de ajedrez de m x n (1 <= m,n
<= 300) donde algunas casillas fueron
eliminadas (o prohibidas). Determinar cul es
la mxima cantidad de torres que se pueden
colocar de manera que no existan 2 que se
amenacen.
Problemas
Stock Charts - Google Code Jam R2 (2009)
goo.gl/lpVuZN
Dados varios charts, representados como
polilneas. Dos charts se pueden combinar en
una sola hoja si no se intersectan. Determinar
la mnima cantidad de hojas necesarias para
dibujar todos los charts.
Ms problemas!
Inspection: goo.gl/iYho0F
Super Watch: goo.gl/Y1h5zY
Oil Company: goo.gl/XW3jSp
Shogui Tournament: goo.gl/KRz3Yi
Graduation: goo.gl/hnCwOU
Parking: goo.gl/21ZJqC
"Shortest" pair of paths: goo.gl/ardYaY
Angels and Devils: goo.gl/sCkd30
Cdigo fuente
Para los problemas dados pueden utilizar el
cdigo fuente en el siguiente repositorio:
https://github.com/nicalvarez/flujo
Hay implementaciones de:
Bipartite Matching (DFS)
Edmonds-Karp
Dinic
Preflow-push
Bibliografa
Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest. Introduction to Algorithms 3ed. Captulo 26
Ravindra K. Ahuja, Thomas L. Magnanti, and James B.
Orlin. Network Flows: Theory, Algorithms, and
Applications
Topcoder Tutorials:
Max flow: goo.gl/luDODH
Min-cost max-flow: goo.gl/XfRWjS
Preguntas?
