Algoritmos em Grafos
Celso C. Ribeiro
Caroline T. Rocha
PARTE 4: PROBLEMA DO FLUXO MÁXIMO
Algoritmos em Grafos
2
Problema do Fluxo Máximo
Dados: Grafo G=(X,U) orientado
u  U: capacidade c(u)
0 ≤ f(u) ≤ c(u)
fonte
S
f
sumidouro
P
Problema: Obter um fluxo máximo de S a P respeitando as
restrições de capacidade e as restrições de conservação de
fluxo em cada nó.
Algoritmos em Grafos
3
Problema do Fluxo Máximo
Inserindo-se um arco de retorno, transforma-se um
fluxo em uma “circulação”:
S
P
f
Exemplo:
1, 1
0, 5
1, 2
S
capacidades c
fluxos f
a
P
3, 3
2, 4
3, 
Algoritmos em Grafos
4
Problema do Fluxo Máximo
v, x = S
f (u )   f (u ) 

uI u x
uT u x
: ( )
: ( )
I(u)
u
0, x  S, x  P
-v, x  P
T(u)
Com o arco de retorno:
f (u )   f (u )  0, x  X

uI u x
uT u x
: ( )
: ( )
Algoritmos em Grafos
5
Problema do Fluxo Máximo
Exemplo:
a

3
S
e
1
2

c
2
1

1
7
P

5

Capacidades associadas aos nós:
2
3
2
x
8
x1
7
8
3
c(x)
x2
7
Algoritmos em Grafos
6
Problema do Fluxo Máximo
Algoritmo de rotulação de Ford e Fulkerson (idéia básica)
Início: fluxo viável (por exemplo um fluxo nulo)
Iteração:
Determinar um caminho C de S a P ao longo do
qual nenhum arco esteja saturado.
(isto é, f(u) = c(u))
Circuito  = C  {(P,S)}
Aumentar o fluxo ao longo dos arcos de  do
valor  = minu[c(u)-f(u)]
Algoritmos em Grafos
7
Problema do Fluxo Máximo
Exemplo:
a
1
1
5
2
S
P
1
3
4
32
1
2
3
Este fluxo (f=3) é máximo?
Por que?
Fluxo máximo = 4
Algoritmos em Grafos
8
Problema do Fluxo Máximo
A inexistência de um caminho aumentante no grafo original
não quer dizer que não seja possível aumentar o fluxo.
Obter uma cadeia ligando S e P que, em conjunto com o arco de
retorno (P,S) defina um ciclo :
+: arcos de  orientados como (P,S)
-: arcos de  orientados no sentido oposto a (P,S)
1= minu+ [c(u) – f(u)] (aumento possível nos arcos de +)
2= minu- [f(u)]
(redução possível nos arcos de -)
Melhorar a solução (aumentar o fluxo) somando
 = min{1, 2} aos fluxos nos arcos de + e subtraindo  aos
fluxos nos arcos de -.
Algoritmos em Grafos
9
Problema do Fluxo Máximo
Exemplo:
f(u) c(u)
a
+
1, 1
S
+
+1
-
X
1, 2
0
+1
1
X 5
0,

P
-1
3, 3
X
2, 4
3
+
3, 
+1 X
4
1 = 2
2 = 1
=1
Algoritmos em Grafos
10
Problema do Fluxo Máximo
Algoritmo
Procedimento de rotulação para obter um ciclo :
Nó x  rótulo (x)
Quantidade pela qual pode ser
aumentado o fluxo de S a x seguindo
uma cadeia cujo último arco é A(x)
Rotulação direta:
x marcado (x)
com u = (x,y)
f(u) < c(u)
y não marcado
x
(y)
u
y
= min { (x),
c(u)-f(u) }
(x)
A(y) = u
Algoritmos em Grafos
11
Problema do Fluxo Máximo
Rotulação inversa:
x marcado (x)
arco u = (y,x)
f(u) > 0
y não marcado
u
x
y
(y)
= min { (x),
f(u) }
(x)
A(y) = u
f(u)  0 u
ROTULAR(f,,A,Y)
Enquanto  > 0 faça
ALTERAR_FLUXOS(f,,A)
ROTULAR(f,,A,Y)
fim-enquanto
Algoritmos em Grafos
12
Problema do Fluxo Máximo
ROTULAR(f,,A,Y)
, (S)  +
Y  {S}
Enquanto P  Y e  > 0 faça
Se u =(x,y): x  Y, y  Y e f(u) < c(u) então
Y  Y  {y}
A(y)  u
(y)  min {(x), c(u)-f(u)}
Senão
Se u =(y,x): x  Y, y  Y e f(u) > 0 então
Y  Y  {y}
A(y)  u
(y)  min {(x), f(u)}
Senão
  0
fim-enquanto
Se P  Y então   (P)
FIM-ROTULAR
Algoritmos em Grafos
13
Problema do Fluxo Máximo
ALTERAR_FLUXOS(f,,A)
x  P
f(P,S)  f(P,S) + 
Enquanto x  S faça
u  A(x)
Se x = T(u) então
f(u)  f(u) + 
x  I(u)
Senão
f(u)  f(u) - 
x  T(u)
fim-enquanto
FIM-ALTERAR_FLUXOS
Algoritmos em Grafos
14
Problema do Fluxo Máximo
a
Exemplo:
1, 1
1,
0, 5
1, 2
0,
S
P
3, 3
2,
3, 4
3, 
4,
Marcação:
f(P,S) = 4
(S) = +
Y = {S}
A(S) = (P,S)
(b) = 2
Y = {S, b}
A(b) = (S,b)
(a) = 1
Y = {S, b, a}
A(a) = (a,b)
(P) = 1
Y = {S, b, a, P} A(P) = (a,P)
=1
f(a,P) = 1
f(a,b) = 0
f(S,b) = 3
f(S,a) = 1
f(b,P) = 3
Algoritmos em Grafos
15
Problema do Fluxo Máximo
a
Exemplo:
1, 1
1, 5
0, 2
S
P
3, 3
3, 4
4, 
Marcação:
(S) = +
Y = {S}
(b) = 1
Y = {S, b}
 = 0, P  Y
FIM
Algoritmos em Grafos
16
Problema do Fluxo Máximo
2
15
Exemplo:
15 15
6
20
5
1
5
12
3
15
7
8
6
8
10
15
4
4
9
8
12
8
15

(1) = +
Y = {1}
A(1) = (7,1)
(2) = 20
Y = {1, 2}
A(2) = (1,2)
(6) = 15
Y = {1, 2, 6}
A(6) = (2,6)
(7) = 15
Y = {1, 2, 6, 7} A(7) = (6,7)
 = 15
f(6,7) = 15
f(2,6) = 15
f(1,2) = 15
f(7,1) = 15
Algoritmos em Grafos
17
Problema do Fluxo Máximo
15
Exemplo:
2
15 15
6
20
5
12
1
10
5
3
15
7
8
6
8
8
15
4
8
9
4
8 8
8
12
8
15
23

(1) = +
Y = {1}
A(1) = (7,1)
(3) = 10
Y = {1, 3}
A(3) = (1,3)
(4) = 9
Y = {1, 3, 4}
A(4) = (3,4)
(8) = 9
Y = {1, 3, 4, 8} A(8) = (4,8)
(7) = 8
Y = {1, 3, 4, 8, 7} A(7) = (8,7)
=8
f(8,7) = 8
f(4,8) = 8
f(3,4) = 8
f(1,3) = 8
f(7,1) = 23
Algoritmos em Grafos
18
Problema do Fluxo Máximo
2
15
20
Exemplo:
15 15
6
20
5
12
1
4
5
5
5
10
3
7
5 8
6
8
8
15
15
8
9
4
8 8
8
12
8
23
28

(1) = +
Y = {1}
A(1) = (7,1)
(2) = 5
Y = {1, 2}
A(2) = (1,2)
(3) = 5
Y = {1, 2, 3}
A(3) = (2,3)
(5) = 5
Y = {1, 2, 3, 5} A(5) = (3,5)
(7) = 5
Y = {1, 2, 3, 5, 7} A(7) = (5,7)
=5
f(5,7) = 5
f(3,5) = 5
f(2,3) = 5
f(1,2) = 20
f(7,1) = 28
Algoritmos em Grafos
19
Problema do Fluxo Máximo
2
20
Exemplo:
15 15
6
20
5
12
1
4
5
5
5
7
10
10
8
7
7
5 8
6
8
3
15
15
8
9
4
8 8
8
12
8
28
30

(1) = +
Y = {1}
A(1) = (7,1)
(3) = 2
Y = {1, 3}
A(3) = (1,3)
(5) = 2
Y = {1, 3, 5}
A(5) = (3,5)
(7) = 2
Y = {1, 3, 5, 7} A(7) = (5,7)
=2
f(5,7) = 7
f(3,5) = 7
f(1,3) = 10
f(7,1) = 30
Algoritmos em Grafos
20
Problema do Fluxo Máximo
2
20
Exemplo:
15 15
6
20
5
12
1
4
5
5
7
10
10
7
7 8
6
8
3
15
15
8
9
4
8 8
8
12
8
30

(1) = +
Y = {1}
 = 0, P  Y
FIM
Algoritmos em Grafos
21
Problema do Fluxo Máximo
Teorema do Corte Mínimo
Um conjunto de arcos C é chamado de corte separando P de S
se  Y  X com S  Y e P  Y tal que
C = { u  U: I(u)  Y, T(u)  Y }
Um corte separando P de S corta qualquer caminho de S a P
no grafo G = (X,U).
Capacidade de um corte separando P de S:
c(C) = uC c(u)
Algoritmos em Grafos
22
Problema do Fluxo Máximo
Exemplo:
5
1
8
4
S
P
2
7
3
6
C = { (1,5), (2,4), (2,6)
(2,6),}(S,3) }
Y = { S, 1, 2,
2 }3}
Algoritmos em Grafos
23
Problema do Fluxo Máximo
Teorema:
fluxo viável f
corte C
f(P,S)  c(C)
Y
Y
f sp  f ps  f (P , S )
fSP
S
fPS
P
f ps  0  f (P , S )  f sp 

f (u )

u C

c (u )  c (C )

u C

Algoritmos em Grafos
24
Problema do Fluxo Máximo
Corolário:
Quando o algoritmo de rotulação termina com um fluxo f
sem que seja possível marcar o nó P, f é a solução ótima
do problema de fluxo máximo de S a P.
PY
u
Y
T(u)
Y
senão a extremidade u
estaria marcada
Y
I(u)
u
Y
f(u) = c(u),
f(u) = 0,
senão a extremidade u
estaria marcada
Algoritmos em Grafos
25
Problema do Fluxo Máximo
Corolário:
Se as capacidades são inteiras, então o algoritmo de Ford e
Fulkerson obtém em um número finito de iterações uma
solução ótima do problema de fluxo máximo.
Algoritmos em Grafos
26
Problema do Fluxo Máximo
Teorema:
O valor do fluxo máximo é igual à capacidade do corte
mínimo separando P de S.
Ao final do procedimento de rotulação:
Y
Y
fSP
S
fPS = 0
P
fPS
fSP = fPS + f*(P,S)
fSP = c(C)
f*(P,S) = c(C)
f(P,S)  c(C)
f*(P,S)
corte é mínimo.
Algoritmos em Grafos
27
Problema do Fluxo Máximo
2
20
Exemplo:
15 15
6
20
5
12
1
4
5
5
7
10
10
7
7 8
6
8
3
15
15
8
9
4
8 8
8
12
8
30

Corte mínimo
Capacidade = 30
Fluxo máximo = 30
(1) = +
Y = {1}
 = 0, P  Y
FIM
Algoritmos em Grafos
28