Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página descreve o algoritmo dos caminhos de aumento para o problema do fluxo máximo. O algoritmo foi publicado por Ford e Fulkerson em 1962.
[Esta página é um resumo de parte da seção 22.2 (Augmenting-Path Maxflow Algorithms) do capítulo 22 (Network Flow) do livro de Sedgewick.]
Um pseudocaminho num digrafo é uma sequência de vértices dotada da seguinte propriedade: para cada par (u,v) de vértices consecutivos,
No primeiro caso, dizemos que u-v é um arco direto (= forward arc) do pseudocaminho. No segundo caso, dizemos que v-u é um arco inverso (= backward arc) do pseudocaminho.
Exemplo: Considere o digrafo definido pelo conjunto de arcos abaixo.
0-1 1-7 2-1 2-3 3-4 4-2 2-6
Nesse digrafo, a sequência 0-1-2-3-4-5-6 é um pseudocaminho. O arco 2-1 é inverso. Todos os demais arcos são diretos.
Um pseudocaminho é um caminho se não tem arcos inversos. Vamos apelar, frequentemente, ao princípio da preguiça universal e dizer "caminho" no lugar de "pseudocaminho", embora isso possa causar confusão…
Suponha dada uma rede capacitada e um fluxo que respeita as capacidades dos arcos. Dizemos que um arco u-v está cheio se o fluxo no arco é igual à capacidade do arco. Dizemos que um arco u-v está vazio se o fluxo no arco é nulo.
Nesse contexto, um caminho de aumento (= augmenting path) é um pseudocaminho que vai do vértice inicial ao final da rede e tem as seguintes propriedades:
A operação de enviar d unidades de fluxo ao longo de um caminho de aumento consiste no seguinte:
É fácil verificar que o resultado dessa operação é um fluxo desde que d não seja muito grande.
Suponha dada uma rede capacitada e um fluxo que respeita as capacidades. Suponha dado um caminho de aumento na rede. A capacidade residual de um arco direto, digamos a, do caminho é a diferença
c(a) - f(a)
e a capacidade residual de um arco inverso, digamos b, do caminho é
f(b),
sendo f(e) o fluxo e c(e) a capacidade de um arco e.
A capacidade residual do caminho de aumento é a menor das capacidades residuais dos arcos do caminho. É claro que a capacidade residual de um caminho de aumento é um número estritamente positivo. (Como veremos adiante, esse número é necessariamente inteiro.)
Suponha que um caminho de aumento C tem capacidade residual d. Se enviarmos d unidades de fluxo ao longo de C, produziremos um novo fluxo que respeita a capacidade de cada arco da rede. A intensidade do novo fluxo será d unidades maior que a intensidade do fluxo original.
Considere a rede capacitada abaixo. O fluxo indicado na coluna f respeita as capacidades e tem intensidade 2.
arco c f s = 0
0-1 2 2 t = 3
0-2 2 0
1-2 2 2
1-3 2 0
2-3 2 2
A sequência 0-2-1-3 é um caminho de aumento. Esse caminho tem capacidade residual 2. Se enviarmos 2 unidades de fluxo ao longo do caminho, teremos um novo fluxo f':
arco c f'
0-1 2 2
0-2 2 2
1-2 2 0
1-3 2 2
2-3 2 2
O novo fluxo f' respeita as capacidades e tem intensidade 4.
O algoritmo de Ford e Fulkerson, também conhecido como algoritmo dos caminhos de aumento, resolve o problema do fluxo máximo. Cada iteração começa com um fluxo f que respeita a capacidade dos arcos da rede. A primeira iteração começa com o fluxo nulo. Cada iteração consiste no seguinte:
- se existe caminho de aumento para f
- então encontre um caminho de aumento C
- então calcule a capacidade residual d de C
- então envie d unidades de fluxo ao longo de C
- então seja f' o fluxo resultante dessa operação
- então comece nova iteração com f' no lugar de f
- senão devolva f e pare
Por incrível que pareça, esse algoritmo produz um fluxo de intensidade máxima. A prova desse fato, será discutida na próxima página, depois que tivermos introduzido o conceito de capacidade de um corte.
Eis uma propriedade interessante do algoritmo: Como as capacidades dos arcos são números inteiros, o valor do fluxo em cada arco será inteiro ao longo da execução do algoritmo.
Considere a rede capacitada abaixo. (Este exemplo é cópia da figura 22.14, p.372, de Sedgewick.)
arco cap s = 0
0-1 2 t = 5
0-2 3
1-3 3
1-4 1
2-3 1
2-4 1
3-5 2
4-5 3
Comece com fluxo nulo. Agora aplique a sequência de caminhos de aumento
0-1-3-5
0-2-4-5
0-2-3-1-4-5
(os arcos inversos estão indicados em negrito). O primeiro caminho de aumento tem capacidade residual 2. Depois que enviarmos 2 unidades de fluxo ao longo desse caminho, teremos um fluxo f'. O segundo caminho de aumento é calculado em relação a f' e produz um terceiro fluxo, digamos f". O terceiro caminho de aumento é calculado em relação a f" e tem capacidade residual 1.
A sequência de fluxos produzida pelos caminhos de aumento está indicada abaixo. Todos respeitam as capacidades dos arcos. O último fluxo tem intensidade 4.
arco f f' f" f"'
0-1 0 2 2 2
0-2 0 0 1 2
1-3 0 2 3 2
1-4 0 0 0 1
2-3 0 0 0 1
2-4 0 0 1 1
3-5 0 2 2 2
4-5 0 0 1 2
| | |
| | 0-2-3-1-4-5
| 0-2-4-5
0-1-3-5
Eis outra sequência de caminhos de aumento que leva do fluxo nulo a um fluxo de intensidade 4:
0-2-4-5
0-2-3-5
0-1-4-5
0-1-3-5
Mais uma sequência de caminhos de aumento que leva do fluxo nulo a um fluxo de intensidade 4:
0-1-4-5
0-2-4-1-3-5
0-2-3-5
0-1-4-5
O consumo de tempo do algoritmo é diretamente proporcional ao número de iterações. Tudo se reduz, portanto, à seguinte questão: Quantos caminhos de aumento são necessários para produzir um fluxo máximo a partir do fluxo nulo?
Número de Caminhos de Aumento (Property 22.6, p.382, Sedgewick): Se todos os arcos da rede têm capacidade menor que M então o número de caminhos de aumento necessário para atingir o fluxo máximo é menor que V·M, sendo V o número de vértices da rede.
Eis a prova desse fato. 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 caminho de aumento é um número inteiro positivo. Logo, cada caminho de aumento tem capacidade residual pelo menos 1 e assim aumenta em pelo menos 1 a intensidade do fluxo. Resta apenas mostrar que a intensidade do fluxo é menor que VM. 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 caminhos de aumento não é excessivamente pessimista: existem exemplos — veja próxima seção — em que o número de caminhos de aumento chega muito perto de VM.
Como o número de caminhos de aumento 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 mais técnica, diz-se que o algoritmo é apenas fracamente polinomial.]
Para obter um desempenho que não dependa das capacidades será preciso escolher os caminhos de aumento de maneira mais cuidadosa. É o que faremos nas próximas páginas.
Considere a rede capacitada abaixo. (Este exemplo é cópia da figura 22.20, p.383, de Sedgewick.)
arco cap s = 0
0-1 M t = 3
0-2 M
1-2 1
1-3 M
2-3 M
Começando com fluxo nulo, considere a sequência de caminhos de aumento
0-1-2-3, 0-2-1-3, 0-1-2-3, 0-2-1-3, ...
Eis a correspondente sequência de fluxos:
arco f f f f f ...
0-1 0 1 1 2 2
0-2 0 0 1 1 2
1-2 0 1 0 1 0
1-3 0 0 1 1 2
2-3 0 1 1 2 2
| | | |
| | | |
| | | |
| | | 0-2-1-3
| | 0-1-2-3
| 0-2-1-3
0-1-2-3
O número de iterações é tanto maior quanto maior for M. Mais precisamente, o algoritmo controi 2M caminhos de aumento para atingir o fluxo máximo (que tem intensidade 2M). Como V=4, temos (V-2)M caminhos de aumento.
(É bem verdade que poderíamos atingir o fluxo máximo em apenas duas iterações se os caminhos de aumento fossem escolhidos de maneira diferente.)
arco cap s = 0
0-1 2 t = 5
0-2 3
0-3 2
1-2 1
1-3 1
1-4 1
2-4 1
2-5 2
3-4 2
3-5 3
4-5 2
arco cap s = 0 t = 5
0-1 2
0-2 3
0-3 2
1-3 1
1-4 1
2-1 1
2-5 2
3-4 2
3-5 3
4-2 1
4-5 2