Flujos De Transporte

Red de transporte N = (D,c)
a 5 e 5 3 s 5 2 4 2 3 2 b d t

Flujos
Gregorio Hernández Peñalver UPM
Teoría de Grafos

c: A → Z+ CAPACIDAD
2

a 32 s 53 20

52

e 54 32 t 31 s 53

a

52

e 54

41

2 1

20

41

2 1 31

t

22 b

d

22 b

d

FLUJO en una red N 1. 2. f(x,y) ≤ c(x,y)
xv∈A

f : A → Z+ VIABILIDAD Para todo v ≠ s, t CONSERVACIÓN
3

VALOR DELFLUJO f OBJETIVO

val(f) = f+(s) = f-(t)

∑ f ( x, v ) = ∑ f ( v, z )
vz∈A

Dada una red N, hallar el valor máximo del flujo y un flujo de valor máximo

4

a 32 s 53 20

52

e 54 32 t 31 s 53

a

52

e 54

41

2 1

20

41

2 1 31

t

22 b

d

22 b

d

CORTE en N es una partición de V =S∪T, con s∈S, t∈T Capacidad de un corte cap(S,T) =
cap(azul)=11cap(verde)=12
5

Flujo neto de S a T

x∈S , y∈T

∑ c( x , y )

x∈S , y∈T

∑ f ( x, y) − ∑ f ( v, u) = val(f )
v∈T , u∈S
x∈S , y∈T

val(f ) ≤

x∈S , y∈T

∑ f ( x, y) ≤ ∑ c( x, y) = cap(S, T )
6

1

Corolario max val(f) ≤ min cap(S,T)

¿Cómo aumentar un flujo de s a t? Caminos dirigidos de s a t
32 52 b α =min αi e 54 t

Teorema de Ford-Fulkerson (1955) max val(f) = min
fflujo

s

cap(S,T)

residuo αi = c(xi,xi+1) – f(xi,xi+1)

(S,T) corte

P es camino de f-aumento si α>0
33 s
7

53 a e

55 t
8

¿Y si en el camino de s a t hay arcos hacia atrás?
53 s residuo b 41 e 21 d 31 33 t s 54

a

53

e 55

20

42

2 0 32

t

αi = c(xi,xi+1) – f(xi,xi+1) αi = f(xi+1,xi)

α =min αi

22 b

d

P es camino de f-aumento si α>0
54 s b 42 e20 d 32 t
9

Si un flujo f es máximo, entonces la red NO puede tener caminos de f-aumento
10

Método de Ford-Fulkerson 1. Partir de f≡0 2. Mientras exista P camino de f-aumento en la red N, aumentar f a lo largo de P 3. Devolver f

Teorema de Ford-Fulkerson El valor máximo de un flujo en una red N es igual a la mínima capacidad de los cortes de N
Dem. Si f es un flujo de valor máximo, nohay caminos de f-aumento de s a t. Construiremos un corte de capacidad val(f)

¿Este proceso acaba? Al final, ¿se obtiene un flujo máximo?

S={x∈V/ existe un camino de f-aumento de s a x}

T=V-S

val(f ) =
11

x∈S , y∈T

∑ f ( x, y) − ∑

f ( v, u ) =

u∈S , v∈T

x∈S , y∈T

∑ c(x, y) − 0 = cap(S, T)
12

2

a 33 s 54 20

53

e 55

1. Se supone que existe un flujo devalor máximo 2. Si las capacidades son enteras el método de Ford-Fulkerson puede necesitar analizar val(f) caminos. Como el análisis de cada camino tiene un coste O(q), la complejidad es O(val(f)q)

42

2 0 32

t

a 22 b d s 1000 b
13 14

1000 1

1000 t 1000 max flujo=2000

val(f)=7 El corte S={s,a,b,e} T=V-S tiene capacidad cap(S,T)=7

a 1 s b 1 1 s t 1

a 1 0 t

ALGORITMO DEETIQUETADO (Edmonds, Karp)
Estrategia • Partir de un flujo cualquiera, f≡0 • Usar búsqueda en anchura para construir un árbol de caminos de f-aumento con raíz en s • Si el árbol alcanza t, aumentar f a lo largo del camino correspondiente y volver al paso 2) con el nuevo flujo f • Si el árbol no alcanza t, FIN del algoritmo, el flujo considerado es máximo. Un corte de capacidad mínima es (S,T)donde S={vértices que se alcanzan en el árbol con caminos de f- aumento}, T=V-S

b

Tras 2000 caminos como los anteriores alcanzamos el flujo máximo a 1000 s 1000 b
15

1000 0 1000 t

16

f≡0

s

f1

s
f2

a+3

b+5

a+0

b+5

e+3

d+2
Camino: s, a, e, t Camino: s, b, d, t Residuo 2
17

a-0

d+2

e+4

t+3

Residuo 3

t+2
18

3

s s
f3

f3
NO haycamino de aumento para f3

a+0 a+0 b+3 a-0 a-0
Camino: s, b, e, t Residuo 2

b+1

d+0

e+1

d+0

e+2
t+0 t+2
19 20

a-1

a 33 s 54 20

53

e 55

Teorema (1972)
t

42

2 0 32

El algoritmo de etiquetado de Edmonds y Karp calcula un flujo maximal en O(nq2)
Dem. El algoritmo construye una sucesión de flujos f0, f1, ..., fM , ¿cuántos flujos se construyen? y ¿cuál es...