View
120
Download
3
Category
Preview:
Citation preview
Algoritmos de Fluxo Máximo
Verlani Timm Hinzvertimm@gmail.com
UNIVERSIDADE CATÓLICA DE PELOTASEscola de Informática
Programa de Pós-Graduação em InformáticaMestrado em Ciência da Computação
Prof. Dr. Paulo Roberto Gomes Luzzardi
2
Sumário
Aplicações Conceitos Fluxo em redes Fluxo máximo Método de Ford-Fulkerson
Redes residuais Caminhos de aumento Cortes
Referências Bibliográficas
3
Aplicações
Considere a seguinte situação modelada por um grafo: – Cada arco representa uma rua de mão única. – O peso de cada arco indica o maior fluxo possível ao longo da rua (veículos/hora).• Qual o maior número possível de veículos que pode viajar de u a v em uma hora?
4
Aplicações
Outra situação: Imagine que uma empresa deseja transportar a
maior quantidade possível de produtos de uma cidade para outra, através da rede rodoviária.
A restrição do transporte é que cada estrada da rede suporta um número finito de caminhões. Então como determinar o fluxo máximo
permitido na rodovia?
5
Outras aplicações
O envio de produtos do produtor ao distribuidor;
A deslocação das pessoas das suas casas para os locais de trabalho;
A expedição de cartas desde a estação de correio até os seus destinatários;
Modelagem de líquidos fluindo por tubos; Peças por linha de montagem; Informações por redes de comunicações,
Correntes por redes elétricas, …
6
Conceitos
Capacidadede um arco
c(o,a)
fluxof(o,a) arcos ou arestas
nó
origem destino
No caso acima, verifica-se que existe uma capacidade de 5 unidades de fluxo do nó O para o nó A e de 4 unidades de fluxo do nó A para o O.
7
O que são fluxos?
Em termos de grafo:
O fluxo é o envio de entidades de um nó(origem) até outro nó (destino), percorrendo alguns dos arcos da rede onde aqueles nós fazem parte.
8
Fluxo em redes
Um fluxo em rede G=(V,E) é um grafo orientado em que cada aresta (u,v) E e tem uma capacidade não negativa c(u,v) 0.
● u=origem e v=destino;
● Cada vértice reside em algum caminho de u a v.
9
Fluxo em Redes
Deve satisfazer as três propriedades seguintes: Restrição de capacidade: o fluxo que circulará em um
grafo deve ser igual ou menor que a capacidade máxima deste fluxo.
f(u,v) c(u,v) Anti-simetria oblíqua: o fluxo em um direção deve ser
igual ao seu fluxo na direção oposta.
f(u,v)=-f(u,v) Conservação de fluxo: O fluxo que entra deve ser igual ao
que sai.
10
Fluxo em Redes
Redes de fluxo com múltiplas fontes e/ou destinos
Definir super-fonte que liga a todas as fontes; Definir super-destino ao qual todos os destinos
se ligam; Capacidades infinitas entre super-fonte e fontes,
e entre destinos e super-destino.
11
12
Fluxo Máximo
Número máximo de unidades de fluxo que é possível enviar através da rede desde o nó origem até o nó destino.
Considera-se que há conservação de fluxo, ou seja, que o fluxo que parte da origem chega totalmente ao destino não havendo, portanto perdas no caminho.
13
Problema do Fluxo Máximo
Para resolver o problema do fluxo máximo foram propostos os seguintes algoritmos:
O célebre método dos caminhos de aumento de Ford e Fulkerson, que foi o primeiro algoritmo proposto;
Goldberg e Tarjan propuseram um novo método conhecido como método do pré-fluxo.
Algoritmo de Edmonds-Karp propôs o algoritmo dos caminhos de aumento de comprimento mínimo.
Obs.: Neste trabalho foi enfatizando o Método de Ford-Fulkerson
14
Método de Ford-Fulkerson
Depende de três idéias importantes: Redes residuais: Consiste em arestas que
podem admitir mais fluxo. Caminhos em ampliação: Consiste de um
caminho simples desde a origem até a rede residual.
Cortes: um corte é um conjunto de arcos orientados contendo, pelo menos, um ramo de cada caminho da origem ao destino.
15
Redes residuais - conceito
Seja G = (V;E). Dado um fluxo f(s; v) em G, a capacidade residual cf é a
quantidade de fluxo adicional que pode passar por (s; v) sem exceder a capacidade c(s; v):
cf (u; v) = c(u; v) - f(u; v)
Assim, se por exemplo c(s; v) = 5 e f(s; v) = 4, ainda pode-se aumentar o fluxo de s para v em cf = 1 unidades antes que a restrição de capacidade seja excedida.
16
Redes residuais - Exemplo
5-4=1
Rede residual
17
Caminhos em ampliação - conceito
Dado um fluxo em rede G = (V;E) e um fluxo f, um caminho em ampliação (ou caminhos de aumento) é um caminho simples de s a t na rede residual Gf . A quantidade máxima pela qual o fluxo pode ser aumentado em um caminho de ampliação é chamada de capacidade residual de p, é expressa por:
cf (p) = minfcf (u; v) : (u; v) está em pg
Isso quer dizer que a capacidade residual de um caminho em ampliação p corresponde à menor dentre as capacidades das arestas que fazem parte de p.
18
Algoritmo de Ford-Fulkerson
O problema do fluxo máximo pode resolver-se por Programação Linear, mas o algoritmo, devido a Ford-Fulkerson, que se vai descrever é muito mais expedito.
Os passos de cada iteração do algoritmo podem ser resumidos do seguinte modo:
1º - Escolhe-se um caminho qualquer desde a origem até ao destino, mas em que os arcos orientados que o constituintes tenham capacidade positiva (>0).
2º - Procurar nesse caminho o arco orientado com menor capacidade, c,
3º - Diminuir de c a capacidade de fluxo em cada arco do caminho no sentido considerado e aumentar de c a capacidade dos arcos no sentido inverso.
Regressar ao 1º passo. Se já não existir nenhum caminho em que todos os arcos tenham capacidade positiva, tal significa que já se determinou o fluxo máximo.
19
Algoritmo de Ford-Fulkerson
20
Caminhos de aumento - Exemplo
21
Exemplo:Vamos aplicar este algoritmo à rede dada.1º passo - Considere-se, por exemplo, o caminho que passa pelos
nós 1, 2, 5 e 7.2º passo - Verifica-se que a menor capacidade destes arcos
orientados, no sentidode 1 para 7, é de 3 = Min(7,3,8), ver fig 1.2.3º passo - Subtrai-se este valor de 3 a 7 (= 4 no arco 12), a 3
(=0 no arco 2 5) e a 8 (= 5 no arco 5 7); soma-se o mesmo valor a 2 (= 5 no arco 2 1), a 1 (=4 no arco 5 2) e a 4 (= 7 no arco 7 5) e atualizam-se os valores das capacidades.
Caminhos de aumento - Exemplo
22
Caminhos de aumento - Exemplo
Caminho: 1,2,5,7Min(7,3,8)=3
7-3=4
3-3=0
8-3=5
23
Caminhos de aumento - Exemplo
1ª interaçãoCaminho: 1,4,6,7Min(5,4,9)=4
5-4=1
4-4=0
9-4=5
24
Caminhos de aumento - Exemplo
3+4=7
2ª interaçãoCaminho: 1,3,5,7Min(9,3,5)=3
9-3=6
3-3=0
5-3=27+3=1
0
25
Caminhos de aumento - Exemplo
3ª interaçãoCaminho: 1,3,6,7Min(6,2,5)=2
6-2=4
2-2=0
5-2=3
10+2=12
3ª interação
26
Caminhos de aumento - Exemplo
4ª interaçãoNão existe nenhum caminho com capacidade positiva. Os arcos 25, 3 5, 3 6 e 4 6 têm todos capacidade nula, pelo que não é possível constituir qualquer caminho de 1 a 7 com capacidade maior que zero.
Está, portanto, encontrado o fluxo máximo possível de deslocar desde o nó origem até ao nó destino, 12 unidades de fluxo.
4-5=-1
27
Teorema do Fluxo Máximo
Apesar deste algoritmo ser bastante simples, se apenas se quisermos conhecer o valor do fluxo máximo do nó origem para o nó destino e se tratar de uma rede com grandes dimensões, é possível resolver este problema através do Teorema do Fluxo Máximo:
“Para toda a rede com uma só origem e um só destino o fluxo máximo é igual ao valor mínimo de corte
entre todos os cortes possíveis da rede”.
28
Cortes de fluxo - conceito
Um corte(S,T) de um fluxo em rede G = (V;E) é uma separação do conjunto de vértices V em dois conjuntos S e T = V - S, de forma que a origem s 2 S e o depósito t 2 T.
Se f é um fluxo, então o fluxo líquido pelo corte (S; T) é definido como f(S; T). A capacidade do corte (S; T) é c(S; T).
Um corte mínimo de uma em rede é um corte cuja capacidade é mínima dentre todos os cortes da rede.
29
3
3
2
4
Cortes de fluxo - exemplo
Utilizado em redes de grandes dimensões
Fluxo máximo é igual ao valor mínimo de corte entre todos os cortes possíveis da rede.
7 9
5
8
9
7+9+5=21
7+1+3+2+2+5=20
3+3+2+4=12
12
8+9=173
172
5
2
30
O professor Ademar tem dois filhos que, infelizmente, não gostam nem um pouco um do outro. O problema é tão grave que eles não só se recusam a caminhar até a escola juntos, mas de fato cada um se recusa a passar por qualquer quadra que o outro filho tenha percorrido no mesmo dia. Os filhos não tem nenhum problema com o fato de seus percursos se cruzarem em uma esquina. Felizmente, tanto a casa do professor quanto a escola estão em esquinas, mas além disso ele não está certo de que vai ser possível enviar ambos os filhos à mesma escola. O professor tem um mapa da sua cidade. Mostre como formular o problema de determinar se os dois filhos do professor podem freqüentar a mesma escola como um problema de fluxo máximo.
Um problema para pensar ...
31
Referências
CORMEN, T. H. et al. Algoritmos: teoria e prática. Rio de Janeiro: Campus, 2002
.
Sites:http://www.engprod.ufjf.br/fernando/epd015/fluxo_maximo.pdf
http://descartes.ucpel.tche.br/WFC/2002/apa_grupo6-FluxoMaximo.pdf
Demonstração:http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/maxflow/MaxflowApp.shtml?demo1
Recommended