Algoritmos para Grafos  |  Índice

Fluxo máximo e corte mínimo

Este capítulo mostra que o algoritmo de Ford-Fulkerson resolve o problema do fluxo máximo.  Isso prova o célebre Teorema do Fluxo Máximo e Corte Mínimo  (publicado em 1956 por Ford e Fulkerson e também por Elias, Feinstein e Shannon).

Saldo de fluxo num conjunto de vértices

Considere o conceito de fluxo em um grafo com vértice inicial e vértice final.  A definição de saldo de fluxo em um vértice pode ser estendida a qualquer conjunto de vértices.  O fluxo que sai de um conjunto S é a soma dos fluxos nos arcos que saem de S e o fluxo que entra em S é a soma dos fluxos nos arcos que entram em S.  O saldo de fluxo em S é a diferença

entre o fluxo que sai de S e o fluxo que entra em S.   É fácil verificar a seguinte propriedade dos saldos: para qualquer fluxo f num grafo com vértice inicial s e vértice final t e para qualquer conjunto S que contém s mas não contém t,

Cortes e sua capacidade

Dado um grafo com vértice inicial s e vértice final t, dizemos que um conjunto de vértices separa s de t se contém s mas não contém t.   Um  corte (= cut)  no grafo é qualquer conjunto de arcos que tenha a forma C' ∪ C'', sendo C' o leque de saída e C'' o leque de entrada de algum conjunto S de vértices que separa s de t.  Diremos que o conjunto S é a margem superior do corte e o complemento S de S é a margem inferior do corte.

Um arco de um corte é direto se pertence ao leque de saída da margem superior do corte (ou seja, se vai da margem superior para a margem inferior) e é reverso se pertence ao leque de entrada da margem superior do corte (ou seja, se vai da margem inferior para a margem superior).

Num grafo capacitado, a capacidade  de um corte é a soma das capacidades dos arcos diretos do corte.  (Se todos os arcos tiverem capacidade 1, a capacidade de um corte é o número de arcos diretos do corte.)  Os arcos reversos não contribuem para a capacidade do corte.

A expressão corte mínimo é uma abreviatura de corte de capacidade mínima.

Exemplo A.  Considere o grafo capacitado abaixo, com vértice inicial 0 e vértice 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  

A tabela abaixo lista todos os cortes do grafo. Em cada linha temos um corte. A primeira coluna dá a margem superior do corte, a segunda dá a margem inferior do corte, a terceira dá os arcos diretos do corte, a quarta dá os arcos reversos, e a última dá a capacidade do corte.  Os cortes mínimos têm capacidade 40.

0    1 2 3 4 5   0-1 0-2                            50  
0 1    2 3 4 5   0-2 1-3 1-4                        70
0 2    1 3 4 5   0-1 2-3 2-4                        40
0 3    1 2 4 5   0-1 0-2 3-5      1-3 2-3           70
0 4    1 2 3 5   0-1 0-2 4-5      1-4 2-4           80
0 1 2    3 4 5   1-3 1-4 2-3 2-4                    60
0 1 3    2 4 5   0-2 1-4 3-5      2-3               60
0 1 4    2 3 5   0-2 1-3 4-5      2-4               90
0 2 3    1 4 5   0-1 2-4 3-5      1-3               50
0 2 4    1 3 5   0-1 2-3 4-5      1-4               60
0 3 4    1 2 5   0-1 0-2          1-3 1-4 2-3 2-4   50
0 1 2 3    4 5   1-4 2-4 3-5                        40
0 1 2 4    3 5   1-3 4-5                            60
0 2 3 4    1 5   0-1 3-5 4-5      1-3 1-4           70
0 1 2 3 4    5   3-5 4-5                            50

(A lista de cortes está completa? Falta algum?)

Cortes limitam fluxo

A capacidade de qualquer corte limita a intensidade de qualquer fluxo que respeita as capacidades.

Essa propriedade pode ser resumida pela expressão  intensidade (fluxo) ≤ capacidade (corte) .  A prova da propriedade é simples. Suponha que f é um fluxo que respeita as capacidades e C é um corte. Seja S a margem superior do corte.  Pela propriedade dos saldos, a intensidade de f é igual ao saldo de f em S.  Esse saldo é outflow(S) − inflow(S) e portanto não passa de outflow(S).  Como f respeita as capacidades, outflow(S) não passa da capacidade do corte C.

Eis uma consequência importante da delimitação:  Se um fluxo f respeita as capacidades e tem intensidade igual à capacidade de algum corte então f é um fluxo de intensidade máxima. Um tal corte é, portanto, um certificado da maximalidade do fluxo. 

Exemplo B.  Considere o grafo capacitado abaixo (o mesmo do exemplo A), com vértice inicial 0 e vértice final 5. A segunda linha da tabela 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 
 20  30  30  10  10  10  20  30  
 20  20  10  10  10  10  20  20 

Mostre um corte que certifique a maximalidade do fluxo.

Análise do algoritmo de Ford-Fulkerson

Quando discutimos o algoritmo de Ford-Fulkerson no capítulo de mesmo nome, omitimos a prova de sua correção.  Para mostrar que o algoritmo de fato resolve o problema do fluxo máximo, basta provar o seguinte fato:  se um dado fluxo f não tem pseudocaminho aumentador então f é um fluxo de intensidade máxima.

A prova desse fato é surpreendentemente simples.  Suspenda, por um momento, a cláusula da definição de pseudocaminho aumentador que exige que o pseudocaminho termine em t. Agora considere o conjunto  S  de todos os vértices que são término de um pseudocaminho aumentador.  É claro que s está em S. Mas t está fora de S pois, por hipótese, não existe pseudocaminho aumentador que termine em t.  Seja C o corte cuja margem superior é S.  Todos os arcos diretos de C estão cheios e todos os arcos reversos estão vazios (por que?).  Portanto, o saldo de f em S é igual à capacidade de C.  Logo, a intensidade de f é igual à capacidade de C e portanto f é um fluxo máximo.

Essa análise da última iteração do algoritmo de Ford-Fulkerson prova o seguinte teorema:

O teorema pode ser informalmente resumido pela expressão  max intensidade (fluxo) = min capacidade (corte).  Diz-se que o teorema estabelece uma identidade minimax.  (Se as capacidades forem todas iguais a 1, o teorema diz que uma coleção máxima de caminhos sem arcos em comum tem o mesmo tamanho que um corte mínimo, sendo o tamanho do corte medido pelo número de arcos diretos.)

O algoritmo de Ford-Fulkerson mostra também um importante adendo ao teorema:  se as capacidades dos arcos forem números inteiros então existe um fluxo máximo tal que o fluxo em cada arco é um número inteiro.

Exemplo C.  Considere o grafo capacitado abaixo, com vértice inicial 0 e vértice 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  

Eis um fluxo que respeita as capacidades:

0-1 0-2 1-3 1-4 2-3 2-4 3-5 4-5 
 20  20  20  10  10  10  20  20

Agora tome o corte cuja margem superior é o conjunto de vértices  0 2  e cuja margem inferior é  1 3 4 5.  A capacidade desse corte é 40.  Como a intensidade do fluxo também é 40, concluímos que o fluxo é máximo e o corte é mínimo.  (Exercício: encontre outro corte mínimo.)

Exemplo D.  Veja exemplo animado de fluxo máximo e corte mínimo no site Algorithms, 4th edition de Sedgewick e Wayne.

O problema do corte mínimo.  Considere o seguinte problema: Dados vértices s e t de um grafo capacitado, encontrar um corte de capacidade mínima dentre os que separam s de t.  O algoritmo de Ford-Fulkerson discutido acima resolve esse problema. De fato, na última iteração do algoritmo, o leque de saída do conjunto S definido na prova da correção do algoritmo é um corte de capacidade mínima.