tema 1

Flujo máximo: Redes de flujo y
método de Ford-Fulkerson

Jose Aguilar

Algoritmos de Flujos
Los algoritmos de flujos resuelven el problema de
encontrar el flujo máximo de una fuente a un sumidero
respetando una serie de restricciones.
•

Los flujos se miden como el flujo que sale de un nodo,
si así ocurriera el flujo se considera positivo, en caso
contrario tenemos un flujonegativo.
• La fuente tiene un flujo neto positivo, el sumidero tiene
un flujo neto negativo y los nodos intermedios en los
caminos que van de la fuente al sumidero tienen un
flujo neto igual a cero.
propiedad de conservación del flujo
Σfi = Σfo (por nodo).
Equivalente a las leyes de conservación de la materia en
física y leyes de Kirchoff en electricidad.

Algoritmos de Flujos
Usos: modeladode flujo en tuberías, piezas a través de
líneas de ensamblado, corrientes en redes eléctricas,
información en redes de comunicación, etc.
Problema del flujo máximo: encontrar la rata máxima a la
cual el material puede ser transportado de una fuente (s) a
un destino (t), sin violar las restricciones de capacidad de la red.

Una red de flujo G=(N,A) es un grafo dirigido tal que cada arco(u,v)∈A posee una capacidad c(u,v)≥0. Si (u,v)∉A, c(u,v)=0.
• Se distinguen 2 vértices, el fuente “s” y el destino “t”. Cada vértice
v∈N esta en algún s~>v~>t.
• El grafo es conexo ⇒|A|≥|N|-1
peso de las aristas representa la capacidad máxima de
transportar un flujo.

Flujo
El flujo está dado por una función con imagen en
los reales. f:NxN→R que satisface:
•
•
•

Restricción decapacidad: ∀u,v ∈ N, f(u,v)≤c(u,v).
Simetría distorsionada: ∀u,v ∈ N, f(u,v)=-f(v,u).
Conservación de flujo: ∀u,v ∈ N-{s,t} se requiere
que ∀v∈N Σf(u,v) = 0
f(u, u) = 0

Sea f(u,v) el flujo desde u hasta v, el valor de ese
flujo se define como |f|= Σf(s,v) ∀v∈N

El problema del flujo máximo
Se define como: dado G, s (fuente) y t (destino)
encontrar el flujo neto total máximo desde s hasta tFlujo neto positivo entrando a un nodo v es
Σu∈N F(u,v)
y el que sale se define simétricamente.

Flujo residual
Es el flujo disponible en una determinada arista una
vez que se ha enviado flujo por ella (en ningún caso el
flujo neto residual debe ser mayor a la capacidad de
dicha arista ni menor que cero).
flujo residual = capacidad – flujo_actual,

Dada una red de flujo G=(N,A) confuente s y destino t
Sea f el flujo en G, y considere un par de vertices u,v
∈N.
La cantidad de flujo adicional que se puede verter
sobre u,v es la capacidad residual.
cf(u,v) = c(u,v) – f(u,v)

Red residual
Un camino de flujo residual es aquel camino de la
fuente al sumidero donde todas las aristas en el
camino tienen un flujo residual mayor a cero
red residual consiste en arcos queadmiten más flujo
(en ella aparecen los caminos de flujo residual)
Un arco (u, v) aparece en Gf solo si (u,
v)∈A y si hay una flujo neto positivo o
flujo residual de u a v o (v, u)∈A y esta
pasando un flujo actual entre (v, u)

s

s

G con flujo f

0

11/16

10

1

Gf
8/13

2

5

1
12

4/9

| Af | ≤ 2|A|

11/14

7/7

3
4/4

5 t

4
15/20

5

10 8

23

1/4
12/12

0

11

4
5

3

7

3

4

15
5

5
t

11

4

Algoritmo de Ford-Fulkerson
FORD-FULKERSON( f, s)
Para cada arista (u, v) en el grafo
f[u][v] = 0
f[v][u] = 0
Mientras exista un camino de flujo residual entre f y s
incremento = min(cap(u,v) tal que (u,v) está en el
camino)
para cada arista (u,v) en el camino
f[u][v] = f[u][v] + incremento
f[v][u]= -f[u][v]

s
0

2

1

2

3

2

1

1

1
1

3

4
5
t

3

Cmin = 2

3

3

1
1
1

3

3

4
2

5
t

s
0

2

2

1

1

3

2

s
0

3

Cmin = 1

1

2

3

1

3

4
2

3
5
t
Cmin = 3

¿Qué pasa si las aristas (4,1) o (3,2) cambian de signo?

Algoritmo de Ford-Fulkerson
Es un método iterativo que depende de tres...