Upload
internet
View
105
Download
0
Embed Size (px)
Citation preview
ESCOLA DE ENGENHARIA
C++Ford-Fulkerson
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Fonte, Sumidouro, Fonte, Sumidouro, Capacidade e FluxoCapacidade e Fluxo
22 33
11 66
44 55
20, 520, 5
11, 811, 8
5, 25, 2
7, 47, 4
4, 34, 3
3, 33, 3
13, 613, 6
10, 410, 4
FonteFonte( s )( s )
SumidourSumidouroo
( t )( t )
CapacidadCapacidadee
( c )( c )
FluxoFluxo( f )( f )
exemplos:exemplos:cc52 52 = 4= 4 ff52 52 = 3= 3
cc36 36 = 13= 13 ff36 36 = 6= 6
2/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
CondiçõesCondições
0 0 f fijij c cijij
(fluxo não supera (fluxo não supera capacidade) capacidade)
0 < c0 < cijij
(capacidade não negativa)(capacidade não negativa)
nos arcos:nos arcos:
ii jjccijij, f, fijij
nos vértices:nos vértices:
iiffijij
(sai)(sai)
ffkiki
(entra)(entra)
0, se e
, se
, se ij ki
j k
i s i t
f f F i s
F i t
(conservaç(conservação) ão)
soma soma dos que dos que
saemsaem
soma soma dos que dos que entramentram
3/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
CortesCortes
22 33
11 66
44 55
20, 520, 5
11, 811, 8
5, 25, 2
7, 47, 4
4, 34, 3
3, 33, 3
13, 613, 6
10, 410, 4
corte corte (A, (A, B)B)
c(A, B) = 5 + 13 = 18c(A, B) = 5 + 13 = 18f(A, B) = - 5 - 3 + 2 + 6 = 0f(A, B) = - 5 - 3 + 2 + 6 = 0
(A, B)(A, B)A = {2, 3}A = {2, 3}B = {1, 4, 5, B = {1, 4, 5, 6}6}
c(C, D) = 7c(C, D) = 7f(C, D) = - 4 + 4 = 0f(C, D) = - 4 + 4 = 0
(C, D)(C, D)C = {4}C = {4}D = {1, 2, 3, 5, D = {1, 2, 3, 5, 6}6}
este simeste simxx este nãoeste não
++ ++
--
--
não contém a não contém a fonte e nem o fonte e nem o
sumidourosumidouro
não contém a não contém a fonte e nem o fonte e nem o
sumidourosumidouro
xx xx
xx
xx
capacidacapacidade do de do corte corte (A, B)(A, B)
fluxo fluxo do do
corte corte (A, B)(A, B)
4/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Cortes (continuação)Cortes (continuação)22 33
11 66
44 55
20, 520, 5
11, 811, 8
5, 25, 2
7, 47, 4
4, 34, 3
3, 33, 3
13, 613, 6
10, 410, 4
contém contém o o
sumidousumidouroro
c(E, F) = 20 + 7 = 27c(E, F) = 20 + 7 = 27f(E, F) = 5 + 4 = 9f(E, F) = 5 + 4 = 9
(G, H)(G, H)G = {5, 6}G = {5, 6}H = {1, 2, H = {1, 2, 3, 4}3, 4}
contém contém a fontea fonte
(E, F)(E, F)E = {1, 4}E = {1, 4}F = {2, 3, 5, F = {2, 3, 5, 6}6}
c(G, H) = 4c(G, H) = 4f(G, H) = 3 - 2 - 6 - 4 = -9f(G, H) = 3 - 2 - 6 - 4 = -9
5/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Cortes (continuação)Cortes (continuação)
22 33
11 66
44 55
20, 520, 5
11, 811, 8
5, 25, 2
7, 47, 4
4, 34, 3
3, 33, 3
13, 613, 6
10, 410, 4
c(I, J) = 20 + 10 = 30c(I, J) = 20 + 10 = 30f(I, J) = 5 + 4 - 6 - 3 = 0f(I, J) = 5 + 4 - 6 - 3 = 0
contém a contém a fonte e o fonte e o
sumidourosumidouro
(I, J)(I, J)I = {1, 6}I = {1, 6}J = {2, 3, 4, J = {2, 3, 4, 5}5}
xx
este simeste simxx este nãoeste não
xx
xx xx
6/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Cortes do Tipo (S, T)Cortes do Tipo (S, T)
22 33
11 66
44 55
20, 520, 5
11, 811, 8
5, 25, 2
7, 47, 4
4, 34, 3
3, 33, 3
13, 613, 6
10, 410, 4
c(Sc(S11, T, T11) = 20 + 10 = 30) = 20 + 10 = 30f (Sf (S11, T, T11) = 5 + 4 = 9) = 5 + 4 = 9
contém contém a a
fontefonte
contém contém o o
sumidousumidouroro
SS11
SS33
SS44
c(Sc(S22, T, T22) = 11 + 10 = 21) = 11 + 10 = 21f (Sf (S22, T, T22) = 8 – 3 + 4 = 9) = 8 – 3 + 4 = 9
c(Sc(S33, T, T33) = 13 + 3 = 16) = 13 + 3 = 16f (Sf (S33, T, T33) = 6 + 3 = 9) = 6 + 3 = 9
c(Sc(S44, T, T44) = 11 + 7 = 18) = 11 + 7 = 18f (Sf (S44, T, T44) = 8 - 3 + 4 = 9) = 8 - 3 + 4 = 9
SS22
7/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Cortes (S, T) e não (S, T)Cortes (S, T) e não (S, T)
44 55
22 33
11 66
20, 520, 5
11, 811, 8
5, 25, 2
7, 47, 4
4, 34, 3
3, 33, 3
13, 613, 6
10, 410, 4
fontefonte sumidourosumidouro
0, se (s X,X' t Y,Y')
( , ) ( ', ') 0, se (s Y,Y' t X,X')
0, nos outros casos
f X Y f X Y
8/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Caminhos de Aumento de Caminhos de Aumento de FluxoFluxo
22 33
11 66
44 55
20, 520, 5
11, 811, 8
5, 25, 2
7, 47, 4
4, 34, 3
3, 33, 3
13, 613, 6
10, 410, 4
No contra-No contra-fluxo fluxo
considere considere apenas o apenas o
fluxofluxo
1212 = 20 – 5 = 15 = 20 – 5 = 15
2323 = 11 – 8 = 3 = 11 – 8 = 3
3636 = 13 – 6 = 7 = 13 – 6 = 7
1414 = 10 – 4 = 6 = 10 – 4 = 6 4545 = 7 – 4 = 3 = 7 – 4 = 3
3535 =
2 =
2
3636 = 13 – 9 = 4 = 13 – 9 = 420, 820, 8
11, 1111, 11
13, 913, 9
10, 610, 6 7, 67, 6
5, 05, 0
13, 1113, 11
fluxo máximo = 8 + 6 = 14?fluxo máximo = 8 + 6 = 14?
9/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Alguns Resultados para o Alguns Resultados para o Algoritmo de Ford-FulkersonAlgoritmo de Ford-Fulkerson
#1#1: qualquer fluxo em uma rede é sempre um fluxo de : qualquer fluxo em uma rede é sempre um fluxo de um corte (S, T);um corte (S, T);
#2#2: um fluxo em uma rede não excede a capacidade: um fluxo em uma rede não excede a capacidade de qualquer corte (S, T);de qualquer corte (S, T);
#3#3: um fluxo da fonte ao sumidouro em uma rede é: um fluxo da fonte ao sumidouro em uma rede é máximo se, e somente se, não existe um caminhomáximo se, e somente se, não existe um caminho de aumento de fluxo;de aumento de fluxo;
#4#4: o fluxo máximo em uma rede é igual à capacidade: o fluxo máximo em uma rede é igual à capacidade mínima dentre os cortes (S, T).mínima dentre os cortes (S, T).
10/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=+S=+
Algoritmo de Ford-FulkersonAlgoritmo de Ford-Fulkerson
2020
1111
55
77
44
33
1133
1100
22 33
11 66
44 55
ΔΔ==–– A=0 A=0 S=+S=+
20, 20, 55
11, 11, 88
13, 13, 66
5, 5, 22
3, 33, 3
7, 47, 4
10, 10, 44
4, 4, 33
fluxo fluxo inicialinicial
ΔΔ== A=0 S=+ A=0 S=+
ΔΔ=15 A=1 =15 A=1 S=+S=+
ΔΔ=6 A=1 =6 A=1 S=+S=+
ΔΔ=3 A=2 =3 A=2 S=+S=+
ΔΔ=3 A=2 =3 A=2 S=S=––
atingiu atingiu o o
sumidousumidouroro
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ=3 A=3 =3 A=3 S=+S=+
ΔΔ==–– A=0 A=0 S=+S=+
13, 13, 99
11, 11, 1111
20, 20, 88
ΔΔ=12 A=1 =12 A=1 S=+S=+
ΔΔ=6 A=1 =6 A=1 S=+S=+
ΔΔ=0 A=2 =0 A=2 S=+S=+
ΔΔ=3 A=2 =3 A=2 S=S=––
ΔΔ=2 A=5 =2 A=5 S=S=––
ΔΔ=0=0 A=5 A=5 S=+S=+
ΔΔ=2=2 A=3 A=3 S=+S=+
atingiu atingiu o o
sumidousumidouroro
13, 13, 1111
5, 5, 00
4, 4, 11
20, 20, 1010
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=S=++
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ==–– A=0 A=0 S=S=++
ΔΔ==–– A=0 A=0 S=+S=+
ΔΔ=10 A=1 =10 A=1 S=+S=+
ΔΔ=6 A=1 =6 A=1 S=+S=+
ΔΔ=0=0 A=2 A=2 S=S=++
ΔΔ=1 A=2 =1 A=2 S=S=––
ΔΔ=3 A=4 =3 A=4 S=+S=+
ΔΔ=0=0 A=5 A=5 S=+S=+
atingiu atingiu o o
sumidousumidouroro
o fluxo não o fluxo não pode ser pode ser
mais mais aumentadoaumentado
fluxo máximo = 14fluxo máximo = 14
11/14
capacidcapacidadeade
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
ExercíciosExercícios#1#1: Encontre o fluxo máximo para a rede seguinte.: Encontre o fluxo máximo para a rede seguinte.
11
22 44
33 55
44
55
22 77
22
6633
fluxo máximo = 7fluxo máximo = 7
12/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
ExercíciosExercícios#2#2: Encontre o fluxo máximo para a rede seguinte.: Encontre o fluxo máximo para a rede seguinte.
11
22 44
33 55
55
1010
99
33
55
2244
66
77
44
221010
33
fluxo máximo = compare com outrasfluxo máximo = compare com outras respostas da classerespostas da classe
13/14
C++ - Ford-FulkersonC++ - Ford-Fulkerson Prof. Lincoln Cesar ZamboniProf. Lincoln Cesar Zamboni
Ford-FulkersonFord-Fulkersoninícioinício
Estabeleça osEstabeleça osfluxos iniciaisfluxos iniciais
(zeros, por exemplo).(zeros, por exemplo).
11
Marque os outrosMarque os outrosvérticesvértices
ΔΔ==-- A=0 S= A=0 S=+.+.
Expanda o vérticeExpanda o vérticecom maior ‘com maior ‘ΔΔ’.’.
11
O ‘O ‘ΔΔ’ do’ dosumidourosumidouro
é nulo?é nulo?
simsim
fimfim
Um corte queUm corte quecontenha a fontecontenha a fontefornecerá o fluxofornecerá o fluxo
máximo.máximo.
simsim22
22
nãonãoRetire as (menosRetire as (menosda fonte), volte uti-da fonte), volte uti-lizando os ‘As’ e re-lizando os ‘As’ e re-
calcule os fluxos.calcule os fluxos.
Atingiu oAtingiu osumidouro?sumidouro?
nãonão
Marque a fonteMarque a fonteΔΔ== A=0 S= A=0 S=++,, . .
14/14