Upload
cleilton-pereira
View
232
Download
0
Embed Size (px)
Citation preview
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
1/17
Fluxo Máximo em Redes
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
2/17
2 Algoritmos em Grafos
Sumário
• Aplicações• Conceitos • Fluxo em redes
• Fluxo máximo• Método de Ford-Fulkerson
– Redes residuais – Caminhos de aumento
– Cortes
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
3/17
3 Algoritmos em Grafos
Aplicações
• Considere a seguintesituação modelada por umgrafo – Cada arco representa uma rua
de mão única – A capacidade de cada arcoindica o maior fluxo possívelao longo da rua (veículos/hora)
• Qual o maior númeropossível de veículos quepode viajar de v para w emuma hora?
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
4/17
4 Algoritmos em Grafos
Aplicações
• Outros exemplos –
Envio de produtos da fábrica para odistribuidor
– Transporte de peças em linhas de
montagem –
Líquidos em redes hidráulicas – Dados em redes de comunicação – Correntes em redes elétricas
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
5/17
5 Algoritmos em Grafos
Fluxo em Redes
• Uma rede G =(V, E) é um grafo orientado emque cada aresta (u, v) ! E tem umacapacidade não-negativa c (u, v) " 0
•
Existe sempre um vértice origem s e umvértice destino t• Um fluxo representa o envio de entidades da
origem para o destino, percorrendo alguns dosarcos da rede
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
6/17
6 Algoritmos em Grafos
Fluxo em Redes
capacidade
c( s,v1)
fluxo
f ( s,v1)
No caso acima, verifica-se que existe uma capacidade de 16 unidades defluxo do nó s para o nó v
1, das quais apenas 11 estão sendo usadas no
momento.
Perceba a conservação
de fluxo nos vértices v 1,v 2 , v 3 e v 4.
s t
1 6
12
2 0
7 9 4
1 3
14
4
Edmonton
Calgary
Saskatoon
Regina
Vancouver Winnipeg
s t 1 1 / 1
6
12/121 5 / 2 0
7 / 7
4 / 9
1 / 4
8 / 1 3
11/14
4 / 4
v1 v1
v2 v2
v3 v3
v4v4
j j
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
7/17
7 Algoritmos em Grafos
Fluxo em Redes
• Deve satisfazer três propriedades – Restrição de capacidade: o fluxo que circulará
em um arco deve ser igual ou menor que a suacapacidade
f (u,v) c (u,v)
– Anti-simetria: o fluxo em um direção deve serigual ao seu fluxo na direção oposta
f (u,v) = -f (v,u)
– Conservação de fluxo: o fluxo que entra deveser igual ao que sai (exceto para s e t )
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
8/17
8 Algoritmos em Grafos
Fluxo Máximo
•
É o número máximo de unidades de fluxopossível através da rede desde o nóorigem até o nó destino
•
Considera-se que há conservação defluxo: o que parte da origem chegatotalmente ao destino, sem perdas nocaminho.
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
9/17
9 Algoritmos em Grafos
Método de Ford-Fulkerson
•
Depende das ideias de:
– Rede residual: formada pelas arestas da
rede que podem admitir mais fluxo (ou seja,onde existe capacidade residual ) – Caminho aumentante: um caminho
simples desde a origem até o destino narede residual
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
10/17
10 Algoritmos em Grafos
Rede Residual
Dado uma rede G = (V , E ) e um fluxo f(u,v) em G , acapacidade residual c f é a quantidade de fluxoadicional que pode passar por (u, v) sem exceder acapacidade c (u, v) :
c f (u, v) = c (u, v) – f (u, v)
Assim, se por exemplo c(u,v) = 5 e f(u,v) = 4, aindapode-se aumentar o fluxo de u para v em c f = 1unidades antes que a restrição de capacidade sejaexcedida.
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
11/17
11 Algoritmos em Grafos
Rede Residual
5-4=1
Rede residual
•
Exemplo
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
12/17
12 Algoritmos em Grafos
Caminho Aumentante
Dado um caminho aumentante P em uma rede residualG f , a quantidade máxima pela qual o fluxo pode seraumentado no caminho é chamada de capacidaderesidual c f (P) , e é expressa por
c f (P) = min {c f (u,v) : (u,v) está em P }
A capacidade residual de um caminho aumentante P corresponde à menor dentre as capacidades residuaisdas arestas de P.
• Em outras palavras, é a quantidade que ainda pode serenviada ao longo de P .
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
13/17
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
14/17
14 Algoritmos em Grafos
Algoritmo de Ford-Fulkerson
FOR D-FULKERSON.G;s;t/
1 for each edge .u; / 2 G: E
2 .u; /: f D 0
3 while there exists a path p from s to t in the residual network Gf 4 cf .p/ D min fcf .u; / W .u; / is in pg
5 for each edge .u; / in p
6 if .u; / 2 E
7 .u; /: f D .u; /: f C cf .p/
8 else .;u/: f D .;u/: f cf .p/
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
15/17
15 Algoritmos em Grafos
Exercício
•
Forneça os fluxos e a rede residualobtida a cada iteração do algoritmo deFord-Fulkerson para a rede abaixo:
A
B
C
D
E
F
16
1314
12
20
4
794
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
16/17
16 Algoritmos em Grafos
Resolução
1 2
4 4
4 / 4
4
v1
4
1 6
4
10
s t
1 612
2 0
7 9
4
1 3
14
4
v1
s t
4 / 1 6
4/122 0
7
4 / 9
1 3
4/14
4 / 4
s t 7 5
4
4
v18
4
1 3
2 0
v1
s t
4 / 1 6
8/124 / 2 0
7
4 / 9
4 / 1 3
4/14
4 / 4
4
10
s t 7 5
8
4
v14
9
v1
s t
8 / 1 6
8/128 / 2 0
7 9
4 / 1 3
4/14
4 / 4
v2 v2
v2v2
v2 v2
v3 v3
v3v3
v3 v3
v4 v4
v4v4
v4v4
(b)
(a)
(c)
1 2
4
4
4
4
4
8/18/2019 Teoria Dos Grafos - Fluxo Maximo
17/17
17 Algoritmos em Grafos
Resolução
4
1 2
1 1
2
1 1
2
8
8
9
4
4
9
8
4
4
9
8 s t
1 2
7
4
4
v1
s t
8 / 1 6
8/121 5 / 2 0
7 / 7
9
1 1 / 1 3
11/14
4 / 4
v1
10
1 9 s t
121
7
11
43
v2
v3 v3
v3
v4v4
v4
(d)
(f)
4
9
8
4
4
1 5 s t
5
7
11
4
v1
s t
1 2 / 1
6
12/121 9 / 2 0
7 / 7
9
1 1 / 1 3
11/14
4 / 4
v1
3v2
v3 v3
v4v4
(e) 4
v2
v2
v1
v2
8
8