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. (O teorema foi publicado em 1956 por Ford e Fulkerson e também, no mesmo ano, por Elias, Feinstein e Shannon.)
[A página é um resumo de parte da seção 22.2 (Augmenting-Path Maxflow Algorithms) do livro de Sedgewick.]
Dada um digrafo com vértice inicial s e vértice final t, um corte (= cut) é a união dos leques de saída e entrada de algum conjunto S de vértices que separa s de t, ou seja,
contém s mas não contém t.
Diremos que o conjunto S é a margem s ou lado s do corte. Da mesma forma, diremos que o complemento de S é a margem t ou lado t do corte.
Às vezes é conveniente representar um corte pela expressão (S,T) , sendo S a lado s do corte e T é a lado t do corte. (É claro que (S,T) é uma partição do conjunto de vértices do digrafo.) Um arco de um tal corte (S,T) é direto se vai de S para T e é inverso se vai de T para S.
Numa rede, a capacidade de um corte é a soma das capacidades dos arcos diretos do corte. A expressão "corte mínimo" é uma abreviatura de "corte de capacidade mínima" ou até de "corte de capacidade mínima dentre os que separam o vértice inicial do vértice final".
Exemplo A. Considere a rede abaixo, com vértice inicial 0 e vértice final 5. [Este exemplo é cópia da figura 22.16 de Sedgewick.)
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5
2 3 3 1 1 1 2 3
A tabela abaixo lista todos os cortes que separam 0 de 5. Em cada linha temos um corte. A primeira coluna dá o lado 0 do corte, a segunda dá o lado 5 do corte, a terceira dá os arcos diretos do corte, a quarta dá os arcos inversos, e a última dá a capacidade do corte. Os cortes mínimos têm capacidade 4.
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
(A lista está completa? Falta algo?)
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
Suponha dada uma rede (G, s, t, c). A capacidade dos cortes que separam s de t limita a intensidade dos fluxos:
Delimitação Superior dos Fluxos [Property 22.4 Sedgewick]: Em qualquer rede (G, s, t, c), para todo fluxo que respeita as capacidades e para todo corte que separa s de t, a intensidade do fluxo é menor que ou igual à capacidade do corte.
Essa propriedade pode ser informalmente resumida pela seguinte expressão: intensidade (fluxo) ≤ capacidade (corte) para todo fluxo e todo corte. Ela decorre imediatamente da propriedade dos saldos.
Uma consequência importante dessa propriedade: Se um fluxo f respeita as capacidades e tem intensidade igual à capacidade de algum corte (S,T) então f é um fluxo de intensidade máxima. Um tal corte é, portanto, um certificado da maximalidade do fluxo. (E, a propósito, f é um certificado da minimalidade do corte (S,T).)
Exemplo B. Considere a rede abaixo, com vértice inicial 0 e vértice final 5. (Trata-se da mesma rede do exemplo A.) A segunda linha dá as capacidades dos arcos e a terceira linha dá um fluxo que respeita as capacidades.
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5
2 3 3 1 1 1 2 3
2 2 1 1 1 1 2 2
Dê um corte que corte que certifique a maximalidade do fluxo.
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
Quando discutimos o algoritmo dos pseudocaminhos 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 pseudocaminho de aumento em relação a um dado fluxo f então f tem intensidade máxima. Eis a prova desse fato [veja propriedade 22.5 Sedgewick]:
Suspenda, temporariamente, a cláusula da definição de pseudocaminho de aumento que exige que o pseudocaminho termine em t. Seja S o conjunto de todos os vértices que são término de um pseudocaminho de aumento. É claro que s está em S. Seja T o conjunto de todos os demais vértices da rede. O vértice t está em T pois, por hipótese, não existe pseudocaminho de aumento que termine em t. Portanto, o corte (S,T) separa s de t. Todos os arcos diretos desse corte estão cheios e todos os arcos inversos estão vazios (por que?). Portanto, o saldo de f em S é igual à capacidade do corte.
Mas o saldo de f em S é igual à intensidade do fluxo, conforme a Propriedade dos Saldos. Como não existe fluxo de intensidade maior que a capacidade do corte (S,T), conforme a Delimitação Superior dos Fluxos, nosso fluxo f tem intensidade máxima!
Essa análise do algoritmo dos pseudocaminhos de aumento prova o seguinte teorema (compare com a delimitação superior dos fluxos dada acima):
Teorema do Fluxo Máximo e Corte Mínimo [Maxflow-mincut Theorem, Property 22.5 Sedgewick]: Em qualquer rede (G, s, t, c), a intensidade de um fluxo máximo que respeita as capacidades é igual à capacidade de um corte mínimo que separa s de t.
O teorema pode ser informalmente resumido pela seguinte expressão: max intensidade (fluxo) = min capacidade (corte). Diz-se que esse teorema estabelece uma "identidade minimax".
Exemplo C. Considere a rede abaixo, com vértice inicial 0 e vértice final 5. [Este exemplo é cópia da figura 22.14 de Sedgewick.]
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5
2 3 3 1 1 1 2 3
Eis um fluxo que respeita as capacidades:
0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5
2 2 2 1 1 1 2 2
Eis um corte que separa 0 de 5:
0 2 1 3 4 5
A intensidade do fluxo é 4 e a capacidade do corte é 4. Portanto, o fluxo é máximo e o corte é mínimo. (Exercício: encontre outro corte mínimo.)
0-1 0-4 1-5 2-0 2-3 2-4 4-3 5-0 5-2
1 2 4 2 2 1 2 2 1
0 2 2 1 0 0 2 1 1
