Algoritmos para Grafos, via Sedgewick | Índice remissivo
Esta página mostra que o algoritmo de Ford e Fulkerson de fato resolve o problema do fluxo máximo. Assim, prova o célebre Teorema do Fluxo Máximo e Corte Mínimo.
(A página é um resumo de parte da seção 22.2 (Augmenting-Path Maxflow Algorithms) do livro de Sedgewick.)
Precisamos de uma definição de corte ligeiramente mais restrita que aquela usada na definição de grafo conexo. Dada um digrafo com vértice inicial s e vértice final t, um corte (= st-cut) é qualquer partição (S,T) do conjunto de vértices tal que
s está em S e t está em T.
Um arco direto de um corte (S,T) é qualquer arco que vai de S para T. Um arco inverso do corte é qualquer arco que vai de T para S.
Numa rede capacitada, a capacidade de um corte (S,T) é a soma das capacidades dos arcos diretos do corte.
Suponha dada uma rede capacitada e um fluxo que respeita as capacidades. O fluxo através de um corte (S,T) é a diferença entre a soma dos fluxos nos arcos diretos do corte e a soma dos fluxos nos arcos inversos do corte, ou seja, o saldo de fluxo em S.
A seguinte propriedade decorre imediatamente da propriedade dos saldos:
Delimitação Superior dos Fluxos (Property 22.4, p. 374, Sedgewick): Para qualquer fluxo que respeita as capacidades de uma rede capacitada, o fluxo através de qualquer corte é menor ou igual à capacidade do corte.
Uma consequência importante dessa propriedade: Se um fluxo f respeita as capacidades e tem intensidade igual à capacidade de um corte (S,T) então o fluxo tem intensidade máxima (e o corte tem capacidade mínima). Um tal corte (S,T) é, portanto, um certificado da maximalidade do fluxo.
Considere a rede capacitada abaixo, com vértice inicial 0 e vértice final 5. A coluna f dá um fluxo que respeita as capacidades.
arco cap f s = 0
0-1 2 2 t = 5
0-2 3 2
1-3 3 1
1-4 1 1
2-3 1 1
2-4 1 1
3-5 2 2
4-5 3 2
A tabela abaixo lista todos os cortes. Em cada linha temos um corte (com S na primeira coluna e T na segunda), os arcos diretos do corte (terceira coluna), os arcos inversos do corte (quarta coluna) e a capacidade do corte (quinta coluna).
0 1 2 3 4 5 0-1 0-2 5
0 1 2 3 4 5 0-2 1-3 1-4 7
0 2 1 3 4 5 0-1 2-3 2-4 4
0 3 1 2 4 5 0-1 0-2 3-5 1-3 2-3 7
0 4 1 2 3 5 0-1 0-2 4-5 1-4 2-4 8
0 1 2 3 4 5 1-3 1-4 2-3 2-4 6
0 1 3 2 4 5 0-2 1-4 3-5 2-3 6
0 1 4 2 3 5 0-2 1-3 4-5 2-4 9
0 2 3 1 4 5 0-1 2-4 3-5 1-3 5
0 2 4 1 3 5 0-1 2-3 4-5 1-4 6
0 3 4 1 2 5 0-1 0-2 1-3 1-4 2-3 2-4 5
0 1 2 3 4 5 1-4 2-4 3-5 4
0 1 2 4 3 5 1-3 4-5 6
0 2 3 4 1 5 0-1 3-5 4-5 1-3 1-4 7
0 1 2 3 4 5 3-5 4-5 5
Verifique que o fluxo através de cada um dos quinze cortes tem intensidade 4. (Este exemplo é cópia da figura 22.16, p.375, de Sedgewick.)
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
Quando discutimos o algoritmo dos caminhos de aumento, omitimos a prova de sua correção. É verdade que aquele algoritmo resolve o Problema do Fluxo Máximo?
Para mostrar que isso é verdade, basta provar o seguinte fato: se não existe um caminho de aumento em relação a um dado fluxo então o fluxo tem intensidade máxima. Eis a prova desse fato (veja propriedade 22.5, p.374, Sedgewick):
Suspenda, temporariamente, a cláusula da definição de caminho de aumento que exige que o caminho termine em t. Agora, seja S o conjunto de todos os vértices que são término de um caminho de aumento. É claro que s está em S. Seja T o conjunto de todos os demais vértices de G. O vértice t está em T pois não existe caminho de aumento que termine em t. Portanto, (S,T) é um corte. Todos os arcos diretos desse corte estão cheios e todos os arcos inversos estão vazios. Portanto, o fluxo através desse corte é igual à capacidade do corte.Mas o fluxo através de (S,T) é igual ao saldo em S e portanto igual à intensidade do fluxo (veja a Propriedade dos Saldos). Por outro lado, não existe fluxo de intensidade maior que a capacidade de algum corte (veja a Delimitação Superior dos Fluxos). Logo, nosso fluxo tem intensidade máxima.
Essa análise do algoritmo dos caminhos de aumento prova que a Delimitação Superior dos Fluxos vale com igualdade quando o fluxo é máximo e o corte é mínimo:
Teorema do Fluxo Máximo e Corte Mínimo (Maxflow-mincut Theorem, Property 22.5, p.374, Sedgewick): Em qualquer rede capacitada, a intensidade de um fluxo máximo é igual à capacidade de um corte mínimo.
Considere a rede capacitada abaixo, com vértice inicial 0 e vértice final 5. (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
Eis um fluxo máximo:
arco f
0-1 2
0-2 2
1-3 2
1-4 1
2-3 1
2-4 1
3-5 2
4-5 2
Eis um corte mínimo:
S T
0 2 1 3 4 5
A intensidade do fluxo máximo é 4 e a capacidade do corte mínimo é 4.
A figura define um fluxo f numa rede capacitada com capacidade c. Qual o vértice inicial e o final? Existe caminho de aumento para f? Exiba um fluxo máximo e um corte mínimo. Diga qual a capacidade do corte.
arco c f
0-1 1 0
0-4 2 2
1-5 4 2
2-0 2 1
2-3 2 0
2-4 1 0
4-3 2 2
5-0 2 1
5-2 1 1