ESCOLA DE ENGENHARIA
C++
Ford-Fulkerson
Fonte, Sumidouro,
Capacidade e Fluxo
Capacidade
(c)
20, 5
1
2
4
4, 3
7, 4
exemplos:
c52 = 4
c36 = 13
C++ - Ford-Fulkerson
3
13, 6
Fonte
(s)
10, 4
11, 8
Fluxo
(f )
5, 2
6
Sumidouro
(t)
3, 3
5
f52 = 3
f36 = 6
Prof. Lincoln Cesar Zamboni
2/14
Condições
nos arcos:
i
cij, fij
nos vértices:
fki
j
soma dos
que saem
0 < cij
(capacidade não negativa)
0  fij  cij
(fluxo não supera capacidade)
C++ - Ford-Fulkerson
i
(entra)
fij
(sai)
soma dos
que entram
 f 
ij
j
k
0, se i  s e i  t

f ki   F , se i  s
  F , se i  t

(conservação)
Prof. Lincoln Cesar Zamboni
3/14
Cortes
20, 5
1
2
11, 8
(A, B)
A = {2, 3}
B = {1, 4, 5, 6}
3
4
4, 3
7, 4
(C, D)
C = {4}
D = {1, 2, 3, 5, 6}
5, 2
capacidade
do corte
(A, B)
6
3, 3
c(A, B) = 5 + 13 = 18
f(A, B) = - 5 - 3 + 2 + 6 = 0
5
este sim
x este não
+
+
x
-
c(C, D) = 7
f(C, D) = - 4 + 4 = 0
C++ - Ford-Fulkerson
corte
(A, B)
13, 6
não contém a fonte
e nem o sumidouro
10, 4
não contém a fonte
e nem o sumidouro
Prof. Lincoln Cesar Zamboni
x
x
fluxo do
corte
(A, B)
x
4/14
Cortes (continuação)
20, 5
2
11, 8
13, 6
4, 3
1
10, 4
contém a
fonte
4
5, 2
6
3, 3
7, 4
5
(E, F)
E = {1, 4}
F = {2, 3, 5, 6}
c(E, F) = 20 + 7 = 27
f(E, F) = 5 + 4 = 9
C++ - Ford-Fulkerson
3
(G, H)
G = {5, 6}
H = {1, 2, 3, 4}
contém o
sumidouro
c(G, H) = 4
f(G, H) = 3 - 2 - 6 - 4 = -9
Prof. Lincoln Cesar Zamboni
5/14
Cortes (continuação)
20, 5
2
x
1
10, 4
11, 8
4
4, 3
x
7, 4
contém a fonte
e o sumidouro
3
x
5, 2
x
13, 6
6
3, 3
5
(I, J)
I = {1, 6}
J = {2, 3, 4, 5}
este sim
x este não
c(I, J) = 20 + 10 = 30
f(I, J) = 5 + 4 - 6 - 3 = 0
C++ - Ford-Fulkerson
Prof. Lincoln Cesar Zamboni
6/14
Cortes do Tipo (S, T)
20, 5
S1
S3
S4
2
11, 8
S2
4, 3
4
7, 4
5, 2
contém a
fonte
6
3, 3
5
c(S2, T2) = 11 + 10 = 21
f (S2, T2) = 8 – 3 + 4 = 9
c(S1, T1) = 20 + 10 = 30
f (S1, T1) = 5 + 4 = 9
c(S3, T3) = 13 + 3 = 16
f (S3, T3) = 6 + 3 = 9
C++ - Ford-Fulkerson
3
13, 6
1
10, 4
contém o
sumidouro
Prof. Lincoln Cesar Zamboni
c(S4, T4) = 11 + 7 = 18
f (S4, T4) = 8 - 3 + 4 = 9
7/14
Cortes (S, T) e não (S, T)
20, 5
fonte
2
11, 8
3
13, 6
4, 3
1
10, 4
4
7, 4
6 sumidouro
5, 2
3, 3
5
 0, se (s  X,X'  t  Y,Y')

f ( X , Y )  f ( X ', Y ')  0, se (s  Y,Y'  t  X,X')
 0, nos outros casos

C++ - Ford-Fulkerson
Prof. Lincoln Cesar Zamboni
8/14
Caminhos de Aumento de
Fluxo
23 = 11 – 8 = 3
20, 58
2
11, 811
4, 3
14 = 10 – 4 = 6
36 = 13 – 6 = 7
13,
13,
96
13,11
1
10,
10, 46
3
4
35 = 2
12 = 20 – 5 = 15
7,
7,64
5,
5, 02
36 = 13 – 9 = 4
6
3, 3
5
45 = 7 – 4 = 3
No contra-fluxo
considere apenas
o fluxo
fluxo máximo = 8 + 6 = 14?
C++ - Ford-Fulkerson
Prof. Lincoln Cesar Zamboni
9/14
Alguns Resultados para o
Algoritmo de Ford-Fulkerson
#1: qualquer fluxo em uma rede é sempre um fluxo de
um corte (S, T);
#2: um fluxo em uma rede não excede a capacidade
de qualquer corte (S, T);
#3: um fluxo da fonte ao sumidouro em uma rede é
máximo se, e somente se, não existe um caminho
de aumento de fluxo;
#4: o fluxo máximo em uma rede é igual à capacidade
mínima dentre os cortes (S, T).
C++ - Ford-Fulkerson
Prof. Lincoln Cesar Zamboni
10/14
Algoritmo de Ford-Fulkerson
Δ=15 A=0
Δ=12
Δ=10
A=1 S=+
Δ=–
capacidade
20
20,
20,1085
2
Δ=3
Δ=–
A=0
Δ=0
Δ=2 A=2
A=5 S=+
S=–
11,
11
11,118
3
atingiu o
sumidouro
13
13,
13,1196
fluxo inicial
Δ= A=0 S=+
44, 31
1
55, 02
10
10, 4
3 3
3,
6
Δ=3 A=3
Δ=2
Δ=0
A=5 S=+
Δ=–
A=0
fluxo máximo = 14
77, 4
4
Δ=6 A=0
A=1 S=+
Δ=–
C++ - Ford-Fulkerson
5
o fluxo não pode
ser mais
aumentado
Δ=3
Δ=3
Δ=1 A=4
A=2 S=+
S=–
Δ=–
A=0
Prof. Lincoln Cesar Zamboni
11/14
Exercícios
#1: Encontre o fluxo máximo para a rede seguinte.
5
2
4
2
4
7
2
1
3
3
6
5
fluxo máximo = 7
C++ - Ford-Fulkerson
Prof. Lincoln Cesar Zamboni
12/14
Exercícios
#2: Encontre o fluxo máximo para a rede seguinte.
10
2
4
4
6
3
5
2
1
5
9
4
3
2
5
10
3
7
fluxo máximo = compare com outras
respostas da classe
C++ - Ford-Fulkerson
Prof. Lincoln Cesar Zamboni
13/14
Ford-Fulkerson
1
Expanda o vértice
com maior ‘Δ’.
início
Estabeleça os
fluxos iniciais
(zeros, por exemplo).
Atingiu o
sumidouro?
não
2
sim
Marque a fonte
Δ= A=0 S=+,
2
Marque os outros
vértices
Δ=- A=0 S=+.
.
O ‘Δ’ do
sumidouro
é nulo?
sim
Um corte que
contenha a fonte
fornecerá o fluxo
máximo.
não
Retire as
(menos
da fonte), volte utilizando os ‘As’ e recalcule os fluxos.
fim
1
C++ - Ford-Fulkerson
Prof. Lincoln Cesar Zamboni
14/14