8/18/2019 12 - Flujo Máximo
1/40
Flujo MáximoTraining Camp Argentina 2014
Nicolás Álvarez
naa [at] cs uns edu ar
8/18/2019 12 - Flujo Máximo
2/40
Idea
8/18/2019 12 - Flujo Máximo
3/40
Idea
8/18/2019 12 - Flujo Máximo
4/40
Idea
● Un source s● Un sink t● Nodos intermedios● Arcos dirigidos con unacapacidad dada● Objetivo: Enviar elmáximo flujoposible de
s a t, cumpliendo las restricciones decapacidad.
8/18/2019 12 - Flujo Máximo
5/40
● Una red de flujo es un grafo dirigido G = donde cada arco (u,v)∈ A tiene asociado unacapacidad c(u,v) >= 0.
● Se distinguen dos nodos s yt llamados fuente ydestino , tal que ningún arco llega a la fuente osale del destino.
● Además, por conveniencia, si (u,v)∉A entoncesse supone c(u,v) = 0
● También que para todo u, existe un camino
S ---> u ---> T
Definición: Red de Flujo
8/18/2019 12 - Flujo Máximo
6/40
Definición: Flujo
Unujo en G es una función f : N x N -> R quesatisface:● restricción de capacidad :
○ f(u,v)
8/18/2019 12 - Flujo Máximo
7/40
Definición: Problema Flujo Máximo
● Elvalor de un ujo | f | se dene como
| f | = Σv∈ N f(s,v) = Σv∈ N f(v,t)● Dada una red de ujo G, elProblema de
Flujo Máximoconsiste en encontrar el ujode máximo valor que admite G
8/18/2019 12 - Flujo Máximo
8/40
Repaso
8/18/2019 12 - Flujo Máximo
9/40
Método de Ford-Fulkerson
Es un método general, no un algoritmoespecífico.
Se basa en 3 conceptos claves:● redes residuales● caminos de aumento● cortes
8/18/2019 12 - Flujo Máximo
10/40
Método de Ford-Fulkerson
El método comienza con una red de flujo vacía.
En cada iteración se busca un camino deaumento en la red residual para incrementarel valor del flujo.
Se puede demostrar mediante el teorema demax-flow min-cutque, cuando termina, el flujoobtenido es máximo
8/18/2019 12 - Flujo Máximo
11/40
Redes residuales
Intuitivamente, la red residual es una nuevared de flujo que representa cómo podemoscambiar el flujo.
Formalmente, la red residual de G = esGf = , donde las capacidades de los arcosestán dadas por:
cf (u,v) = c(u,v) - f(u,v)
8/18/2019 12 - Flujo Máximo
12/40
8/18/2019 12 - Flujo Máximo
13/40
Aumento de flujo
8/18/2019 12 - Flujo Máximo
14/40
Cortes
Dada una red de flujo G = . Un corte esuna partición de N en Sy T = N-S tal que s∈ Sy t ∈ T.
Dado un corte (S,T).Elflujo neto a través del corte es:
f(S,T) = Σu ∈ S Σv∈ T f(u,v) - Σu ∈ S Σv∈ T f(v,u)Y lacapacidad del corte es:c(S,T) = Σu ∈ S Σv∈ T c(u,v)
8/18/2019 12 - Flujo Máximo
15/40
Cortes
8/18/2019 12 - Flujo Máximo
16/40
Teorema max-flow min-cut
Los 3 siguientes condiciones son equivalentes:1. f es un flujo máximo
2. La red residual Gf no contiene caminos de aumentos
3. | f | = c(S,T) para algún corte (S,T) de G
Este teorema prueba que el método de Ford-Fulkerson es correcto.
8/18/2019 12 - Flujo Máximo
17/40
Max-flow min-cut: Demostración
1 => 2 Si el flujo es máximo entonces no pueden existircaminos de aumento. De otro modo, sería posibleaumentar el valor del flujo2 => 3Si no existen caminos de aumento en la redresidual, s y t están desconectados. Por lo tanto siS es el conjunto de los nodos alcanzables desde sy T = N - S. El corte (S,T) está saturado
8/18/2019 12 - Flujo Máximo
18/40
Max-flow min-cut: Demostración
3 => 1Se puede observar que todo flujo tiene unvalor menor o igual que la capacidad decualquier corte. Es decir, todo corte implicauna cota superior al valor de un flujo válido.Si el flujo satura algún corte (S,T), esto quieredecir que el flujo tiene el máximo valorposible. Además, el corte (S,T) es el corte decapacidad mínima (omin-cut ) de la red de
flujo.
8/18/2019 12 - Flujo Máximo
19/40
Ford-Fulkerson: Pseudo-código
FORD-FULKERSON(G, s, t):
para cada arco (u,v) ∈ G.E:
(u,v).f = 0
mientras exista camino de aumento p en G f :
cf(p) = min {c
f(u,v) : (u,v) ∈ P}
para cada arco (u,v) ∈ p :
(u,v).f += c f (p)(v,u).f -= c
f(p)
8/18/2019 12 - Flujo Máximo
20/40
Algoritmo de Edmonds-Karp
8/18/2019 12 - Flujo Máximo
21/40
Algoritmo de Edmonds-Karp
Como se vió en la figura anterior, si no elegimos loscaminos de aumento de manera inteligente el tiempo deejecución puede no estar acotado polinomialmente sobreel tamaño de la entrada.
Afortunadamente, si buscamos el camino de aumento máscorto con un BFS, se puede demostrar una cotapolinomial:O(m2n)
Esta implementación de Ford-Fulkerson recibe el nombrede algoritmo de Edmonds-Karp
8/18/2019 12 - Flujo Máximo
22/40
Problemas
Necklace - Regional China 2008 (Hefei)http://goo.gl/xIFUBV
Dado un grafo no dirigido (n
8/18/2019 12 - Flujo Máximo
23/40
Generalización de Conectividad
● Vimos el concepto de conectividad.Componentes conexas y fuertemente
conexas● También vimos el concepto de
componentes biconexas● Se puede generalizar a k-conectividad
8/18/2019 12 - Flujo Máximo
24/40
Generalización de Conectividad
● Un grafo es k-vertex connected si no existeningún conjunto de k-1 vértices tal que aleliminarlos nos deja el grafo desconectado
● A partir de lo anterior, podemos definircomponentes k-vertex connected de ungrafo como los subconjuntos maximalesque cumplen la propiedad
● Existe una definición similar para k-edgeconnectivity
8/18/2019 12 - Flujo Máximo
25/40
Como calcular k-connectivity?
● A alguien se le ocurre una idea?
●
Con el teorema de Max Flow - Min Cutpodemos obtener la k-edge connectivity
● Y cuando queremos calcular k-vertex.QUE HACEMOS???
8/18/2019 12 - Flujo Máximo
26/40
Problemas
Optimal Marks - SPOJgoo.gl/X4fX5Q
Dado un grafo no dirigido donde algunosnodos tienen asignado un número de 31 bits.La tarea es asignar números al resto de losnodos de manera que la suma de los xor denodos adyacentes sea mínima. O sea, paratodo (u,v)∈ G, minimizar ∑(u,v) marca(u) ^
marca(v)
http://goo.gl/X4fX5Q
8/18/2019 12 - Flujo Máximo
27/40
Bipartite Matching
Existen problemas combinatorios que, enprincipio, parecen no guardar relación con elproblema de Flujo Máximo pero que puedenser reducidos a éste.
Uno de los ejemplos más conocidos es elproblema del matching bipartito .
8/18/2019 12 - Flujo Máximo
28/40
Bipartite Matching
Dado un grafo G = , unmatching es unsubconjunto M ⊆ A tal que para todo vérticev∈ M existe a lo sumo un arco de M incidentea v.
Se puede pensar como un "apareamiento" delos nodos, en los que cada nodo se aparea cona lo sumo un nodo, y la relación es simétrica.
8/18/2019 12 - Flujo Máximo
29/40
Bipartite Matching
El problema de Maximum Matching consiste enencontrar un matching válido de máximacardinalidad en un grafo.
Este problema resulta más sencillo para unaclase restringida de grafos llamados grafosbipartitos.
8/18/2019 12 - Flujo Máximo
30/40
Grafo bipartito
Un grafo bipartito es un grafo G = donde el conjunto de nodos N puede serparticionado en 2 conjuntos N = L∪ R donde Ly R son disjuntos y los arcos unen nodos entreL y R.
El problema de hallar un matching máximo enun grafo bipartito se conoce como maximumbipartite matching .
8/18/2019 12 - Flujo Máximo
31/40
Maximum bipartite matching
Este problema puede reducirse a un problemade flujo máximo.
Para ello, construimos una red de flujo dondese agregan 2 nodos: un source s y un sink t.
Se agrega un arco de capacidad 1 entre elsource y cada nodo de L y se agrega un arco decapacidad 1 entre cada nodo de R y el sink .
8/18/2019 12 - Flujo Máximo
32/40
Maximum bipartite matching
8/18/2019 12 - Flujo Máximo
33/40
Problemas
Attacking Rooks - Regional Latam 2013http://goo.gl/oph4Q8
Dado un tablero de ajedrez de m x n (1
8/18/2019 12 - Flujo Máximo
34/40
Teorema de Dilworth
● Caracteriza el ancho de un POS (PartiallyOrdered Set) u Orden Parcial.
● El tamaño de la mayoranticadena es igual alde la partición del POS en la mínimacantidad de cadenas posibles
● Se puede ver relativamente fácilconstruyendo un bipartite matching
8/18/2019 12 - Flujo Máximo
35/40
Teorema de Dilworth
8/18/2019 12 - Flujo Máximo
36/40
Problemas
Stock Charts - Google Code Jam R2 (2009)goo.gl/lpVuZN
Dados varios charts, representados comopolilíneas. Dos charts se pueden combinar enuna sola hoja si no se intersectan. Determinarla mínima cantidad de hojas necesarias paradibujar todos los charts.
http://goo.gl/lpVuZN
8/18/2019 12 - Flujo Máximo
37/40
Más problemas!
● Inspection: goo.gl/iYho0F● Super Watch: goo.gl/Y1h5zY● Oil Company:goo.gl /XW3jSp● ShoguiTournament: goo.gl/KRz3Yi● Graduation: goo.gl/hnCwOU● Parking:goo.gl/21ZJqC●
"Shortest" pair of paths: goo.gl/ardYaY● Angels and Devils:goo.gl/sCkd30
http://goo.gl/ardYaYhttp://goo.gl/21ZJqChttp://goo.gl/hnCwOUhttp://goo.gl/hnCwOUhttp://goo.gl/XW3jSphttp://goo.gl/Y1h5zYhttp://goo.gl/iYho0Fhttp://goo.gl/iYho0Fhttp://goo.gl/sCkd30http://goo.gl/ardYaYhttp://goo.gl/21ZJqChttp://goo.gl/hnCwOUhttp://goo.gl/KRz3Yihttp://goo.gl/XW3jSphttp://goo.gl/Y1h5zYhttp://goo.gl/iYho0F
8/18/2019 12 - Flujo Máximo
38/40
Código fuente
Para los problemas dados pueden utilizar elcódigo fuente en el siguiente repositorio:https://github.com/nicalvarez/flujo
Hay implementaciones de:
● Bipartite Matching (DFS)● Edmonds-Karp● Dinic● Preflow-push
https://github.com/nicalvarez/flujo
8/18/2019 12 - Flujo Máximo
39/40
Bibliografía
● Thomas H. Cormen, Charles E. Leiserson, Ronald L.Rivest. Introduction to Algorithms 3ed. Capítulo 26
●
Ravindra K. Ahuja, Thomas L. Magnanti, and James B.Orlin.Network Flows: Theory, Algorithms, andApplications
● Topcoder Tutorials:○ Max flow:goo.gl/luDODH○ Min-cost max-flow:goo.gl/XfRWjS
http://goo.gl/XfRWjShttp://goo.gl/luDODH
8/18/2019 12 - Flujo Máximo
40/40
Preguntas?
Top Related