12 - flujo máximo

8/18/2019 12 - Flujo Máximo

1/40

Flujo MáximoTraining Camp Argentina 2014

Nicolás Álvarez

naa [at] cs uns edu ar


2/40

Idea


3/40

Idea


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.


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


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)


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/40

Repaso


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


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


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)


12/40


13/40

Aumento de flujo


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)


15/40

Cortes


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.


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


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.


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)


20/40

Algoritmo de Edmonds-Karp


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


22/40

Problemas

Necklace - Regional China 2008 (Hefei)http://goo.gl/xIFUBV

Dado un grafo no dirigido (n


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


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


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???


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


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 .


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.


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.


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 .


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 .


32/40

Maximum bipartite matching


33/40

Problemas

Attacking Rooks - Regional Latam 2013http://goo.gl/oph4Q8

Dado un tablero de ajedrez de m x n (1


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


35/40

Teorema de Dilworth


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


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


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


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


40/40

Preguntas?

12 - flujo máximo

Documents