Jodete

Flujo Máximo
Agustín J. González ELO320: Estructura de Datos y Algoritmos 1er. Sem. 2002

1

Introducción
• Así como modelamos los enlaces de una red y sus nodos como un grafo dirigido, podemos interpretar el grafo como una red de flujo de algún material. • Una fuente produce material en forma estacionaria y un resumidero lo consume. • Cada arco puede ser considerado como un conducto decierta capacidad. • Como con la ley de corrientes de Kirchhoff, la suma de flujos entrantes a un vértice debe ser igual a la saliendo del vértice. • Problema de flujo máximo: Cual es la tasa mayor a la cual el material puede ser transportado de la fuente al resumidero sin violar ninguna restricción de capacidad?

2

Redes de flujo
• Una red de flujo es un grafo dirigido G=(V,E) en donde cadaarco (u,v)∈E tiene una capacidad no negativa c(u,v)≥0. • Se distinguen dos vértices: la fuente s y el resumidero t. • Se asume que cada vértice se encuentra en alguna ruta de s a t. • Un flujo en G es una función f: VxV----> R tal que
– Restricción de capacidad: ∀ u,v en V, f(u,v) ≤ c(u,v) – Simetría: f(u,v) = - f(v,u) – Conservación: ∀ u en V-{s,t} ∑v en Vf(u,v) = 0

• El valor del flujo es |f|= ∑v en Vf(s,v) • El problema del flujo máximo trata de maximizar este flujo.
3

Ejemplo
12 16 s 13 v2 14 12/12 11/16 s 8/13 v2 11/14
4

v1

v3

20 t

10

4

9

7 4 v4

v1

v3

15/20 t

10

1/4

4/9

7/7 4/4 v4

f(u,v)/c(u,v) si f(u,v) ≤ 0 no se anota

Múltiples fuentes y resumideros
• Si hay múltiples fuentes y resumideros, el problema se puede reducir alcaso simple previo de una fuente y un resumidero. • Supongamos que se tiene {s1,s2,s3,..sm} fabricas y {t1,t2,t3,..,tn} puntos de venta.
s1 ∞ ∞ s ∞ ∞ s3 t3 s4 s2 t2 t1 ∞ ∞ ∞ t

5

Método de Ford-Fulkerson
• Este método depende de tres ideas importantes: Camino de aumento y red residual. • Este método es iterativo. Se comienza con f(u,v) =0 para cada par de nodos. • En cada iteración seincrementa el valor del flujo buscando un camino de aumento, el cual es un camino desde la fuente al resumidero que puede conducir mas flujo. Ford-Kulkerson_method(G,s,t) inicializar flujo f a 0; while (existe un camino de aumento p) do aumentar el flujo f a lo largo de p; return f; • Se repite el proceso previo hasta no encontrar un camino de aumento. • Capacidad residual: es la capacidad adicionalde flujo que un arco puede llevar: cf(u,v)= c(u,v) - f(u,v) • Dado una red de flujo G=(v,E) y un flujo f, la red residual: inducida por f es Gf=(V,Ef), con Ef={(u,v) ∈ VxV: cf(u,v)>0} 6

Ejemplo: Red residual / camino de aumento
Red previa Red residual para a)

Capacidad residual

Flujo resultante al aumentar capacidad residual

Red residual inducida por c)

• Capacidad residual: es lacapacidad adicional de flujo que un arco puede llevar: cf(u,v)= c(u,v) - f(u,v) • Dado una red de flujo G=(v,E) y un flujo f, la red residual: inducida por f es Gf=(V,Ef), con Ef={(u,v) ∈ VxV: cf(u,v)>0}
7

Camino de aumento
• Es un camino de aumento p es un camino simple de s a t en el grafo residual Gf • Por definición de red residual, cada arco (u,v) sobre el camino aumentado admite algúnflujo neto positivo desde u a v sin violar la restricción de capacidad. • El flujo adicional máximo está dado por: cf(p)= min{cf(u,v) : (u,v) está sobre p}

8

Algoritmo básico Ford-Fulkerson
• Ford-Fulkerson(G,s,t){ for (cada arco (u,v) de E) { f[u,v]= 0; f[v,u]= 0; } while (exista un camino p desde s at en la red residual Gf) { cf(p) = min{cf(u,v) : (u,v) está sobre p}; for (cada arco(u,v) en p) { f[u,v]= f[u,v] + cf(p) ; f[v,u]= - f[u,v]; } } }

9

Ford-Fulkerson(G,s,t){ for (cada arco (u,v) de E) { Ejemplo: f[u,v]= 0; f[v,u]= 0; } while (exista un camino p desde s at en la red residual Gf) { cf(p) = min{cf(u,v) : (u,v) está sobre p}; for (cada arco (u,v) en p) { f[u,v]= f[u,v] + cf(p) ; f[v,u]= - f[u,v]; } } } a) a d) son las iteraciones del loop while. Lado izquierdo...