Algoritmos para Grafos, via Sedgewick | Índice remissivo
[Esta página é um resumo da parte inicial do capítulo 22 (Network Flow) do livro de Sedgewick. O resumo corresponde à introdução do capítulo e à seção 22.1 (Flow Networks).]
(Veja também minha página Fluxo em Redes.)
Suponha dado um digrafo G e uma função f que atribui um número não negativo a cada arco de G. Diremos que o valor de f num arco é o fluxo no arco. Para qualquer vértice v de G, o influxo em v (= inflow into v) é a soma dos fluxos nos arcos que entram em v. O efluxo de v (= outflow from v) é a soma dos fluxos nos arcos que saem de v. O saldo em v é a diferença
ef(v) - inf(v)
entre o efluxo de v e o influxo em v. (Não confunda essa diferença com inf(v) - ef(v).) Portanto, o saldo em v é o que sai de v menos o que entrou em v.
O enunciado do problema que estudaremos a seguir especifica dois vértices do digrafo: um vértice inicial e um vértice final. Esses vértices serão denotados por s e t respectivamente. [Os vértices escolhidos para fazer o papel de s e t não precisam ter quaisquer propriedades especiais. Na prática, entretanto, não há mal em supor que s é uma fonte e t é um sorvedouro. Poderíamos até mesmo supor que s é a única fonte e t o único sorvedouro do digrafo.]
Num digrafo G com vértice inicial s e vértice final t, um fluxo (= flow) é uma função f que atribui números não negativos aos arcos de G de tal modo que
o saldo de f em todo vértice distinto de s e t é nulo
e o saldo em s não é negativo. É fácil mostrar a seguinte
Propriedade do Fluxo (Property 22.1, p.362, Sedgewick): Para qualquer fluxo num digrafo com vértice inicial s e vértice final t, o saldo em t é igual ao saldo em s com sinal trocado.
A intensidade de um fluxo f é o saldo de f em s. De acordo com a propriedade acima, a intensidade de f é igual ao negativo do saldo em t. Em geral (mas nem sempre) o influxo em s é nulo e o efluxo de t é nulo. Quando isso acontece, a intensidade do fluxo é igual ao efluxo de s e portanto também igual ao influxo em t.
Exemplo trivial: A função que associa 0 a cada arco é um fluxo. A intensidade desse fluxo nulo é 0.
arco f
0-1 1
0-4 2
1-5 5
2-0 1
2-3 1
2-4 1
4-3 3
5-0 2
5-2 3
arco f
0-1 0
0-4 3
1-5 3
2-0 1
2-3 1
2-4 0
4-3 3
5-0 1
5-2 2
A definição de saldo de um fluxo pode ser estendida aos conjuntos de vértices que "separam" o vértice inicial do final. Dado um conjunto S que contém s mas não contém t, o efluxo de S é a soma dos fluxos nos arcos que saem de S e o influxo em S é a soma dos fluxos nos arcos que entram em S. O saldo em S é a diferença
ef(S) - inf(S),
entre o efluxo de S e o influxo em S.
Propriedade dos Saldos (Property 22.3, p.374, Sedgewick): Para qualquer fluxo num digrafo 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, o saldo em S é igual ao saldo em s.
Em outras palavras, para qualquer conjunto S que contém s mas não contém t, o saldo em S é igual à intensidade do fluxo.
No digrafo abaixo (copiado da figura 22.5, p.359, de Sedgewick), o vértice inicial é 0 e o vértice final é 5. A tabela especifica um fluxo de intensidade 4:
arco f
0-1 2
0-2 2
1-3 1
1-4 1
2-3 1
2-4 1
3-5 2
4-5 2
arco f
0-1 2
0-2 0
1-2 2
1-3 0
2-3 2
A soma dos fluxos que saem do vértice 0 é 2, mas alguma coisa deve estar errada, pois a soma dos fluxos que saem do conjunto de vértices {0,2} é diferente de 2. O que está errado?
Todo fluxo por ser representado por uma coleção de caminhos. Cada caminho começa em s, termina em t, e "conduz" uma certa "quantidade de fluxo". A soma das quantidades de fluxo conduzidas pelos caminhos é igual à intensidade do fluxo. (Os caminhos da coleção têm, tipicamente, muitos vértices e arcos em comum.)
Uma rede capacitada é um digrafo com vértice inicial e vértice final a cada um de cujos arcos está associado um número que chamaremos capacidade do arco.
As capacidades dos arcos são números inteiros não negativos. [Essa hipótese é importante para que nossos algoritmos convirjam.] Mais que isso, suporemos que as capacidades de todos os arcos pertencem ao intervalo fechado
[0, M-1],
sendo M uma constante inteira positiva.
Em suma, uma rede capacitada é um digrafo na qual foram especificados
Numa rede capacitada com capacidades c, dizemos que um fluxo f respeita a capacidade se
f(a) ≤ c(a)
para cada arco a. Eis o problema central deste capítulo:
Problema do Fluxo Máximo (= Maximum Flow Problem): Dada uma rede capacitada, encontrar um fluxo de intensidade máxima dentre os que respeitam as capacidades dos arcos.
A tabela abaixo especifica uma rede capacitada com vértice inicial 0 e vértice final 5. A última coluna da tabela especifica um fluxo de intensidade 3 que respeita as capacidades.
s = 0 arco cap f
t = 5 0-1 2 2
0-2 3 1
1-3 3 2
1-4 1 0
2-3 1 0
2-4 1 1
3-5 2 2
4-5 3 1
A próxima tabela especifica outro fluxo que respeita as capacidades e tem intensidade 4:
arco cap f
0-1 2 2
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
Esse fluxo é máximo? (Exemplo copiado da figura 22.6, p.360, 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