Algoritmos para Grafos | Índice
Este capítulo descreve o algoritmo dos pseudocaminhos aumentadores para o problema do fluxo máximo. O algoritmo foi publicado por L.R. Ford e D.R. Fulkerson (e independentemente por A. Kotzig) em 1956.
Sumário:
Um pseudocaminho num grafo é uma sequência de vértices dotada da seguinte propriedade: para cada par v w de vértices consecutivos,
No primeiro caso, dizemos que v–w é um arco direto (= forward arc) do pseudocaminho. No segundo caso, dizemos que w–v é um arco reverso (= backward arc) do pseudocaminho. Um pseudocaminho sem arcos reversos é um caminho.
Exemplo A. Considere o grafo definido pelo conjunto de arcos 0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5. A sequência de vértices 0 2 3 1 4 5 é um pseudocaminho. Ele pode ser indicado assim:
0-2-3=1-4-5
O arco 1-3 é reverso. Todos os demais arcos são diretos.
Suponha dado um grafo capacitado e um fluxo que respeita as capacidades dos arcos. Dizemos que um arco v–w está cheio se o fluxo no arco é igual à capacidade do arco. Dizemos que um arco v–w está vazio se o fluxo no arco é nulo.
Em relação a esse fluxo, um pseudocaminho é aumentador (= augmenting) se vai do vértice inicial ao final do grafo e tem as seguintes propriedades:
Pseudocaminhos aumentadores são uma generalização dos caminhos aumentadores que usamos para obter um emprelhamento máximo num grafo não-dirigido bipartido.
Dado um pseudocaminho aumentador relativo a um fluxo f, a operação de enviar ε unidades de fluxo ao longo do pseudocaminho consiste em calcular um novo fluxo da seguinte maneira:
É fácil verificar que o resultado dessa operação é um fluxo. Ademais, a operação acrescenta ε à intensidade do fluxo. A operação de envio de ε unidades de fluxo ao longo de um pseudocaminho aumentador é análoga à operação M⊕P usada para aumentar um emprelhamento num grafo não-dirigido bipartido.
Exemplo B.
Considere o grafo capacitado definido pela tabela abaixo
(o mesmo do exemplo A).
A segunda linha da tabela dá as capacidades dos arcos
e a terceira define um fluxo
(com -
no lugar de 0).
O vértice inicial é 0 e o final é 5.
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 20 30 30 10 10 10 20 30 20 10 20 0 0 10 20 10
A sequência 0-2-3=1-4-5 é um pseudocaminho aumentador. Se enviarmos 10 unidades de fluxo ao longo desse pseudocaminho, teremos um novo fluxo:
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 20 20 10 10 10 10 20 20
A intensidade do novo fluxo é maior que a intensidade do original.
Suponha dado um grafo capacitado com vértice inicial e vértice final. Seja f um fluxo no grafo que respeita a capacidade c. Suponha dado um pseudocaminho aumentador relativo a f. A capacidade residual de um arco direto v–w do pseudocaminho é a diferença
cvw − fvw ,
sendo cvw a capacidade e fvw o fluxo no arco v–w. A capacidade residual de um arco reverso w–v do pseudocaminho é
fwv .
A capacidade residual do pseudocaminho todo é a menor das capacidades residuais dos seus arcos. É claro que a capacidade residual de um pseudocaminho aumentador é estritamente positiva.
Digamos que δ é a capacidade residual de um pseudocaminho aumentador P e ε é um número entre 0 e δ. Se enviarmos ε unidades de fluxo ao longo de P, produziremos um novo fluxo que respeita as capacidades dos arcos. A intensidade do novo fluxo será ε unidades maior que a intensidade do fluxo original.
Exemplo C. Considere o grafo capacitado definido pela tabela (o mesmo dos exemplos A e B). O vértice inicial é 0 e o final é 5. A segunda linha da tabela dá as capacidades dos arcos e a terceira define um fluxo.
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 20 30 30 10 10 10 20 30 20 10 20 0 0 10 20 10
As capacidades residuais dos arcos do pseudocaminho aumentador 0-2-3=1-4-5 estão indicadas a seguir:
0-2 2-3 1-3 1-4 4-5 20 10 20 10 20
A capacidade residual do pseudocaminho todo é 10.
0-1 0-2 1-2 1-3 2-3 20 20 20 20 20 20 - 20 - 20
O algoritmo de Ford-Fulkerson, também conhecido como algoritmo dos pseudocaminhos aumentadores, resolve o problema do fluxo máximo. Cada iteração começa com um fluxo f que respeita as capacidades dos arcos. A primeira iteração começa com o fluxo nulo. O processo iterativo consiste no seguinte: enquanto existe pseudocaminho aumentador,
Por incrível que pareça, esse simples algoritmo produz um fluxo de intensidade máxima! A prova desse fato, será discutida na próximo capítulo, depois que tivermos introduzido o conceito de capacidade de um corte.
Eis uma propriedade importante do algoritmo: se as capacidades dos arcos são números inteiros, o fluxo em cada arco também permanecerá inteiro ao longo da execução do algoritmo.
Exemplo D. Calculemos um fluxo máximo no grafo capacitado descrito a seguir tomando 0 como vértice inicial e 5 como vértice final.
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 20 30 30 10 10 10 20 30
Comece com fluxo nulo. Considere o pseudocaminho aumentador 0-1-3-5 , que tem capacidade residual 20. Envie 20 unidades de fluxo ao longo do pseudocaminho para obter um segundo fluxo:
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 20 - 20 - - - 20 -
Agora considere o pseudocaminho aumentador 0-2-4-5 relativo ao segundo fluxo. Esse pseudocaminho tem capacidade residual 10. Envie 10 unidades de fluxo ao longo desse pseudocaminho para obter um terceiro fluxo:
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 20 10 20 - - 10 20 10
Agora considere o pseudocaminho aumentador 0-2-3=1-4-5 relativo ao terceiro fluxo. Esse pseudocaminho tem capacidade residual 10. Envie 10 unidades de fluxo ao longo desse pseudocaminho para obter um quarto fluxo:
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 20 20 10 10 10 10 20 20
Não há pseudocaminho aumentador para esse quarto fluxo.
Exemplo E. Veja outra sequência de pseudocaminhos aumentadores (coluna direita da tabela abaixo) para o grafo capacitado do exemplo D. Cada um dos pseudocaminhos aumentadores tem capacidade residual 10. A sequência transforma um fluxo inicial de intensidade 0 em um fluxo final de intensidade 40 (parte esquerda da tabela):
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5
20 30 30 10 10 10 20 30
- - - - - - - - 0-1-4-5
10 - - 10 - - - 10 0-2-4=1-3-5
10 10 10 - - 10 10 10 0-2-3-5
10 20 10 - 10 10 20 10 0-1-4-5
20 20 10 10 10 10 20 20
Note que todos os fluxos da sequência respeitam as capacidades. O último fluxo é máximo pois não há pseudocaminho aumentador para ele.
Exemplo F. Veja uma animação do algoritmo de Ford-Fulkerson no site Algorithms, 4th edition de Sedgewick e Wayne.
0-1 0-2 1-2 1-3 2-3 12 15 20 19 11
O consumo de tempo do algoritmo de Ford-Fulkersonal é proporcional ao número de iterações. Tudo se reduz, portanto, à seguinte questão: Quantos pseudocaminhos aumentadores são necessários para produzir um fluxo máximo a partir do fluxo nulo?
Número de pseudocaminhos aumentadores: Se todos os arcos do grafo têm capacidade inteira e menor que uma constante M então o número de pseudocaminhos aumentadores necessário para atingir um fluxo máximo é menor que VM, sendo V o número de vértices do grafo.
Prova: Como as capacidades dos arcos são números inteiros, o fluxo em cada arco é um número inteiro. Portanto, ao longo da execução do algoritmo, a capacidade residual de cada arco em qualquer pseudocaminho aumentador é um número inteiro positivo. Logo, cada pseudocaminho aumentador tem capacidade residual pelo menos 1 e assim aumenta em pelo menos 1 a intensidade do fluxo.
Resta apenas mostrar que não existe fluxo de intensidade maior que V M. Como não temos arcos paralelos, o número de arcos que saem do vértice inicial é menor que V. Portanto, qualquer fluxo tem intensidade menor que V M. (Esse raciocínio é um caso particular da delimitação superior por capacidade de cortes que veremos adiante.)
Essa estimativa do número de pseudocaminhos aumentadores não é excessivamente pessimista: existem grafos capacitados (veja o exemplo abaixo) em que o número de pseudocaminhos aumentadores chega muito perto de V M.
Como o número de pseudocaminhos aumentadores depende das capacidades dos arcos, o algoritmo não pode ser considerado satisfatório: a mera multiplicação de todas as capacidades por 100, por exemplo, pode multiplicar o consumo de tempo por 100. (Em linguagem técnica, diz-se que o algoritmo é apenas fracamente polinomial.) Para obter um desempenho que não dependa das capacidades será preciso escolher os pseudocaminhos aumentadores de maneira mais cuidadosa. É o que faremos nos próximos capítulos.
Exemplo G. Considere o seguinte grafo capacitado com vértice inicial 0 e vértice final 3:
0-1 0-2 1-2 1-3 2-3 M M 1 M M
Começando com fluxo nulo, tome a seguinte sequência periódica de pseudocaminhos aumentadores:
0-1-2-3 0-2=1-3 0-1-2-3 0-2=1-3 0-1-2-3 0-2=1-3 ...
Eis a correspondente sequência de fluxos:
0-1 0-2 1-2 1-3 2-3 0 0 0 0 0 1 0 1 0 1 1 1 0 1 1 2 1 1 1 2 2 2 0 2 2 3 2 1 2 3 3 3 0 3 3 . . . . . . . . . M M 0 M M
O fluxo tem intensidade 2M e o número de iterações é 2M. Como V = 4, o número de iterações é (V-2)M. Esse exercício mostra que o número de pseudocaminhos aumentadores no algoritmo de Ford-Fulkerson pode chegar muito perto de VM.
(É bem verdade que poderíamos atingir o fluxo máximo em apenas duas iterações se os pseudocaminhos aumentadores fossem escolhidos de maneira diferente. Mas a versão do algoritmo dada acima não ensina como escolher bons pseudocaminhos aumentadores.)
0-1 0-2 0-3 1-2 1-3 1-4 2-4 2-5 3-4 3-5 4-5 2 3 2 1 1 1 1 2 2 3 2
com ciclo(ou seja, um fluxo cuja decomposição em caminhos e ciclos tenha um ciclo). Cada um dos pseudocaminhos aumentadores deve ser simples (ou seja, não pode ter vértices repetidos).
0-1 0-2 0-3 1-3 1-4 2-1 2-5 3-4 3-5 4-2 4-5 2 3 2 1 1 1 2 2 3 1 2
ladosdo grafo consiste nos vértices 0 1 2 3 4 e outro consiste nos vértices 5 6 7 8 9 .
0-5 0-6 1-5 1-6 2-5 2-6 3-5 3-7 3-8 3-9 4-6 4-7 4-8 4-9