Fluxo máximo P.O II

Prévia do material em texto

Fluxo ma´ximo
Raphael Ramos
Raphael Ramos Fluxo ma´ximo 1 / 27
Problema
Durante os anos da Guerra Fria, no in´ıcio da de´cada de 50, foi
formulado um problema devido ao interesse que o exe´rcito dos
Estados Unidos tinha sobre a malha ferrovia´ria do Leste Europeu e
Oeste da Unia˜o Sovie´tica. T.E Harris formulou o seguinte:
“Considere uma rede ferrovia´ria conectando duas cidades atrave´s de
um nu´mero de cidades intermedia´rias, onde cada ligac¸a˜o entre cada
cidade tenha associado um valor de capacidade de transporte.
Encontre um fluxo ma´ximo de uma dada cidade ate´ outra”. T.E
Harris em conjunto com Gal. F. S. Ross formulou um relato´rio a
partir de estudos da regia˜o e fotos de sate´lite sobre as capacidades
operacionais de abastecimento da regia˜o atrave´s dessa malha
ferrovia´ria e formas de interromper o abastecimento dessa regia˜o
pelos trilhos.
Raphael Ramos Fluxo ma´ximo 2 / 27
Problema
Foi esse relato´rio que inspirou as ideias de “Fluxo Ma´ximo e Corte
M´ınimo” de Ford-Fulkerson, onde ao descobrir o corte m´ınimo da
malha ferrovia´ria poderia minimizar os esforc¸os da forc¸as armadas dos
Estados Unidos para desabastecer a regia˜o, no caso de um poss´ıvel
embate com o exe´rcito vermelho. Por questo˜es pol´ıticas o
memorando foi apresentado apenas em 1955.
Raphael Ramos Fluxo ma´ximo 3 / 27
Definic¸a˜o de Fluxo em rede
O fluxo e´ o envio de entidades de um no´ (origem) ate´ outro no´
(destino), percorrendo alguns dos arcos da rede onde aqueles no´s
fazem parte.
Raphael Ramos Fluxo ma´ximo 4 / 27
Fluxo em redes
Um fluxo em rede G=(V,E) e´ um grafo orientado em que cada aresta
(u,v) � E e tem uma capacidade na˜o negativa c(u,v) ≥ 0. Onde u
equivale a origem e v o destino. Em uma rede G=(V,E), cada ve´rtice
reside em algum caminho de u ate´ v.
Raphael Ramos Fluxo ma´ximo 5 / 27
Fluxo em redes
O Fluxo em redes deve respeitar as treˆs propriedades seguintes:
1 Restric¸a˜o de capacidade
2 Anti-simetria obl´ıqua
3 Conservac¸a˜o de fluxo
Raphael Ramos Fluxo ma´ximo 6 / 27
Restric¸a˜o de capacidade
O fluxo que circulara´ em um grafo deve ser igual ou menor que a
capacidade ma´xima deste fluxo.
f(u,v) ≤ c(u,v).
Raphael Ramos Fluxo ma´ximo 7 / 27
Anti-simetria obl´ıqua
O fluxo em uma direc¸a˜o deve ser igual ao seu fluxo na direc¸a˜o
oposta. Essa propriedade e´ va´lida para grafos na˜o orientados.
f(u,v)=-f(u,v)
Raphael Ramos Fluxo ma´ximo 8 / 27
Conservac¸a˜o de fluxo
O fluxo que entra deve ser igual ao que sai, exceto na origem e no
sorvedouro.
Raphael Ramos Fluxo ma´ximo 9 / 27
Capacidade residual
A Capacidade Residual e´ representada por: (cf), onde e´ a capacidade
restante em uma aresta ou arco apo´s passar um fluxo f na mesma. A
Capacidade Residual e´ dada pela equac¸a˜o:
-cf (u, v) = c(u,v) -f (u, v)
Raphael Ramos Fluxo ma´ximo 10 / 27
Aplicac¸o˜es
O problema do fluxo ma´ximo serve para enumeras situac¸o˜es, como
por exemplo:
O envio de produtos do produtor ao distribuidor;
A deslocac¸a˜o das pessoas das suas casas para os locais de
trabalho;
A expedic¸a˜o de cartas desde a estac¸a˜o de correio ate´ os seus
destinata´rios;
Modelagem de l´ıquidos fluindo por tubos;
Pec¸as por linha de montagem;
Informac¸o˜es por redes de comunicac¸o˜es;
Correntes por redes ele´tricas, entre outras;
Raphael Ramos Fluxo ma´ximo 11 / 27
Fluxo ma´ximo
Para resolver o problema do fluxo ma´ximo foram propostos os
seguintes algoritmos:
O me´todo dos caminhos de aumento de Ford e Fulkerson.
Goldberg e Tarjan propuseram um novo me´todo conhecido como
me´todo do pre´-fluxo.
Algoritmo de Edmonds-Karp propoˆs o algoritmo dos caminhos
de aumento de comprimento m´ınimo.
Raphael Ramos Fluxo ma´ximo 12 / 27
Algoritmo de Ford-Fulkerson
Escolhe-se um caminho qualquer desde a origem ate´ ao destino,
mas em que os arcos orientados que os constituem tenham
capacidade positiva (> 0).
Procurar nesse caminho o arco orientado com menor capacidade,
c.
Diminuir de c a capacidade de fluxo em cada arco do caminho
no sentido considerado.
Regressar ao 1o passo. Se ja´ na˜o existir nenhum caminho em
que todos os arcos tenham capacidade positiva, tal significa que
ja´ se determinou o fluxo ma´ximo.
Raphael Ramos Fluxo ma´ximo 13 / 27
Fluxo Ma´ximo
A
B
C
D
E
F
16
13
12
4
14
20
9
7
4
Raphael Ramos Fluxo ma´ximo 14 / 27
Fluxo Ma´ximo
Qual o fluxo ma´ximo entre A e F?
Raphael Ramos Fluxo ma´ximo 15 / 27
Fluxo Ma´ximo
Atribui 0 para o fluxo enviado
A
B
C
D
E
F
0(16)
0(13)
0(12)
0(4)
0(14)
0(20)
0(9)
0(7)
0(4)
Raphael Ramos Fluxo ma´ximo 16 / 27
Fluxo Ma´ximo
Escolhe-se um caminho
A
B
C
D
E
F
0(16)
0(13)
0(12)
0(4)
0(14)
0(20)
0(9)
0(7)
0(4)
Raphael Ramos Fluxo ma´ximo 17 / 27
Fluxo Ma´ximo
Encontra o menor valor
A
B
C
D
E
F
12(4)
0(13)
12(0)
0(4)
0(14)
12(8)
0(9)
0(7)
0(4)
Raphael Ramos Fluxo ma´ximo 18 / 27
Fluxo Ma´ximo
Encontre outro caminho
A
B
C
D
E
F
12(4)
0(13)
12(0)
0(4)
0(14)
12(8)
0(9)
0(7)
0(4)
Raphael Ramos Fluxo ma´ximo 19 / 27
Fluxo Ma´ximo
Menor valor
A
B
C
D
E
F
12(4)
4(9)
12(0)
0(4)
4(10)
12(8)
0(9)
0(7)
4(0)
Raphael Ramos Fluxo ma´ximo 20 / 27
Fluxo Ma´ximo
Outro caminho
A
B
C
D
E
F
12(4)
4(9)
12(0)
0(4)
4(10)
12(8)
0(9)
0(7)
4(0)
Raphael Ramos Fluxo ma´ximo 21 / 27
Fluxo Ma´ximo
Menor valor
A
B
C
D
E
F
12(4)
11(2)
12(0)
0(4)
11(3)
19(1)
0(9)
7(0)
4(0)
Raphael Ramos Fluxo ma´ximo 22 / 27
Fluxo Ma´ximo
Resposta
Fluxo ma´ximo igual a 23
A
B
C
D
E
F
12(4)
11(2)
12(0)
0(4)
11(3)
19(1)
0(9)
7(0)
4(0)
Raphael Ramos Fluxo ma´ximo 23 / 27
Fluxo Ma´ximo
A a F
A
B
C
D
E
F
5
4
10
2
1
5
7
4
6
8
Raphael Ramos Fluxo ma´ximo 24 / 27
Fluxo Ma´ximo
A a F
A
B
C
D
E
F
(2)3
(0)4
(0)10
(2)0
(0)1
(0)5
(0)7
(0)4
(0)6
(2)6
Raphael Ramos Fluxo ma´ximo 25 / 27
Fluxo Ma´ximo
A a F
A
B
C
D
E
F
(2)3
(0)4
(6)4
(2)0
(0)1
(0)5
(0)7
(0)4
(6)0
(2)6
Raphael Ramos Fluxo ma´ximo 26 / 27
Fluxo Ma´ximo
A a F
A
B
C
D
E
F
(2)3
(4)0
(6)4
(2)0
(0)1
(4)1
(0)7
(0)4
(6)0
(6)2
FM = 12
Raphael Ramos Fluxo ma´ximo 27 / 27