O problema do fluxo máximo num grafo

O problema do fluxo máximo é uma poderosa ferramenta de modelagem, capaz de representar uma grande variedade de outros problemas. As aplicações mais óbvias incluem o fluxo de um líquido através de uma rede de tubos, o fluxo de mercadorias do produtor ao consumidor, o casamento de desempregados com empregos, etc. O problema do emparelhamento bipartido máximo é um caso particular.

Este capítulo é uma introdução ao problema do fluxo máximo. Ela estabelece a terminologia técnica e em seguida enuncia o problema. Um algoritmo para o problema será discutido em capítulos subsequentes.

Fluxo

Suponha dada uma tabela f que associa um número positivo com cada arco de um grafo. O número que f associa com um arco v-w será denotado por f_vw e chamado fluxo no arco v-w.

Para qualquer vértice v do grafo, o fluxo que entra em v (= inflow) é a soma dos fluxos nos arcos que entram em v. O fluxo que sai de v (= outflow) é a soma dos fluxos nos arcos que saem de v. O saldo de fluxo (= net flow) em v é a diferença

entre o fluxo que sai de v e o fluxo que entra em v. (Não confunda essa diferença com inflow(v) − outflow(v).) O saldo de fluxo é estritamente positivo se o fluxo que sai é maior que o fluxo que entra.

O enunciado do problema que estudaremos a seguir especifica dois vértices do grafo: um vértice inicial e um vértice final. Esses dois 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 (ainda que, muitas vezes, s seja uma fonte e t um sorvedouro).

Agora podemos definir o conceito de fluxo. (É estranho definir a expressão fluxo no arco antes de definir fluxo, mas essa foi a melhor maneira que encontrei de apresentar os conceitos.) Um fluxo (= flow) num grafo com vértice inicial s e vértice final t é uma tabela f que atribui números positivos (não necessariamente inteiros) aos arcos do grafo de tal modo que

(Para dar ênfase ao papel dos vértices inicial e final, podemos usar a expressão fluxo de s a t.) É fácil mostrar a seguinte propriedade do fluxo: o saldo de f em t é igual ao saldo de f em s com sinal trocado.

A intensidade (= flow value) de um fluxo f é o saldo de f no vértice inicial s. Em muitos exemplos, o fluxo que entra em s é nulo e o fluxo que sai de t é nulo. Quando isso acontece, a intensidade do fluxo é igual ao fluxo que sai de s e portanto também igual ao fluxo que entra em t. (Pode parecer atraente exigir, na definição do conceito de fluxo, que seja nulo o fluxo que entra no vértice inicial. Mas é mais fácil trabalhar sem essa exigência.)

Como representar um fluxo? Se o grafo é representado por listas de adjacência, poderíamos acrescentar um campo aos nós que representam os arcos. Se o grafo é representado por uma matriz de adjacências, podemos usar uma matriz f[][] definida da maneira óbvia: se v-w é um arco, então f[v][w] é o fluxo no arco; senão, f[v][w] é 0.

Exemplo A. A tabela a seguir define um fluxo num grafo-ciclo. O vértice inicial é 0 e o vértice final é 2. O fluxo tem intensidade 40.

Exemplo B. A tabela a seguir define um fluxo no grafo da figura ao lado. O vértice inicial é 0 e o vértice final é 5. O fluxo tem intensidade 50.

Exercícios 1

Seja f um fluxo num grafo com vértice inicial s e vértice final t. Prove que o saldo de f em t é igual ao saldo de f em s com sinal trocado.
A tabela abaixo define um fluxo? Qual o vértice inicial e o final?
```
0-1 0-2 1-2 1-3 2-3 
 15  11   5  10  16 
```
Prove a propriedade dos saldos enunciada acima.
A tabela abaixo define um fluxo no grafo? Se sua resposta for afirmativa, qual o vértice inicial e o final? Qual a intensidade do fluxo?
```
0-1 0-4 1-5 2-0 2-3 2-4 4-3 5-0 5-2 
 10  20  50  10  10  10  30  20  30  
```
A tabela abaixo define um fluxo no grafo? Em caso afirmativo, qual o vértice inicial e o final do grafo? Qual a intensidade do fluxo?
```
0-1 0-4 1-5 2-0 2-3 2-4 4-3 5-0 5-2 
  0  30  30  10  10   0  30  10  20   
```
Verifica fluxo. Escreva uma função GRAPHcheckFlow() que verifique se um suposto fluxo é de fato um fluxo. A função deve receber um grafo G, um vértice inicial s, um vértice final t, e um suposto fluxo representado por uma matriz f[][]. Se f[][] for de fato um fluxo, a função deve devolver sua intensidade. A função também deve verificar se o saldo no vértice final é o negativo do saldo no vértice inicial! [Sedgewick faz uma observação engraçada: Despite our confidence as mathematicians in Property 22.1, our paranoia as programmers dictates that we also check that the flow out of the source is equal to the flow into the sink.]
★ Fluxo em arcos antiparalelos. Seja f um fluxo num grafo com vértice inicial e vértice final. Mostre que existe um fluxo g ≤ f (ou seja, g_vw ≤ f_vw e para cada arco v-w) tal que
1. a intensidade de g é igual à intensidade de f e
2. para cada par v-w, w-v de arcos antiparalelos, um de g_vw e g_wv é nulo.
★ Fluxo em grafo não-dirigido. Seja f um fluxo num grafo não-dirigido com vértice inicial e vértice final. Mostre que podemos supor, sem perda de generalidade, que um de f_vw e f_wv é nulo para cada aresta v-w do grafo.

Fluxo versus coleção de caminhos

Todo fluxo por ser visto como uma macarronada, ou seja, uma coleção de caminhos, todos com origem no vértice inicial e término no vértice final do grafo. Embora o conceito seja intuitivo, sua definição exata é um tanto longa e enfadonha, como veremos a seguir.

Uma coleção P₀, P₁, … , P_m de caminhos, juntamente com uma correspondente coleção ε₀, ε₁, … , ε_m de números inteiros positivos, representa um fluxo f se

Diremos que ε_i é a quantidade de fluxo que o caminho P_i conduz. (Note que, em geral, os caminhos têm vértices e arcos em comum.)

Exemplo C. Considere o fluxo indicado abaixo. A primeira linha da tabela dá os arcos do grafo. A segunda dá o fluxo em cada arco. O vértice inicial é 0 e o final é 1. A intensidade do fluxo é 6.

A seguir, uma coleção de três caminhos que representa o fluxo. Cada caminho conduz a quantidade de fluxo indicada na segunda coluna da tabela

Exercícios 2

Fluxo binário. Seja G um grafo com vértice inicial s e vértice final t. Seja f um fluxo tal que f_vw vale 0 ou 1 em cada arco v-w. Mostre que f é essencialmente igual a uma coleção de caminhos simples de s a t sem arcos em comum (ou seja, cada arco do grafo pertence a no máximo um dos caminhos da coleção).
★ Escreva uma função que receba um fluxo f[][] num grafo que tem vértice inicial e vértice final e imprima uma macarronada (ou seja, uma coleção de caminhos) que represente o fluxo. Sua função deve imprimir também a quantidade de fluxo que cada caminho conduz. (Sugestão: descreva o algoritmo em português antes de começar a programar.)
Decomposição em caminhos e ciclos. Seja f um fluxo de s a t num grafo G. Considere uma coleção de caminhos que representa f. Mostre que o fluxo f em alguns arcos de G pode ser maior que a soma das quantidades de fluxo conduzidas pelos caminhos. Mostre que esse sobra pode ser representada por uma coleção de ciclos.
Sejam s e t os vértices inicial e final de um grafo. Imagine uma coleção de caminhos simples de s a t e um inteiro positivo ε(C) associado com cada caminho C. Escreva um algoritmo que receba essas informações e calcule um fluxo de s a t que seja a soma dos caminhos da coleção. A intensidade do fluxo deve ser igual a ∑_C ε(C).

O problema do fluxo máximo

Uma grafo capacitado é um grafo com números positivos associados aos arcos. O número associado a um arco é conhecido como capacidade do arco. A capacidade de um arco v-w será denotada por c_vw . Suporemos que todas as capacidades são inteiras.

(Um grafo capacitado é, portanto, o caso especial de grafo com custos nos arcos em que os custos são todos positivos e a palavra capacidade é usada no lugar de custo.) Um grafo capacitado com vértice inicial e vértice final é às vezes chamado rede (= network).

Suponha que f é um fluxo num grafo capacitado com vértice inicial e vértice final. Dizemos que f respeita as capacidades se f_vw ≤ c_vw para cada arco v-w, sendo f_vw o fluxo no arco v-w e c_vw a capacidade do arco.

Feita essa definição, podemos enunciar o problema central deste capítulo (e dos capítulos seguintes):

Usaremos frequentemente a expressão fluxo máximo como abreviatura de fluxo de intensidade máxima ou até de fluxo de intensidade máxima dentre os que respeitam as capacidades dos arcos.

Exemplo D. A tabela abaixo especifica um grafo capacitado (a segunda linha da tabela dá as capacidades dos arcos). Suponha que o vértice inicial é 0 e o vértice final é 5.

Exercícios 3

Explique, em sua próprias palavras, o que é o problema do fluxo máximo.
Quais são os dados do problema do fluxo máximo?
Mostre como reduzir uma instância arbitrária do problema do fluxo máximo ao caso especial em que s é a única fonte do grafo e t é o único sorvedouro.
Considere o grafo capacitado com as capacidades definidas pela tabela abaixo. Adote 0 como vértice inicial e 3 como vértice final. Encontre um fluxo máximo.
```
0-1 0-2 1-2 1-3 2-3 
 12  15  20  19  11 
```
[Sedgewick 22.1] Encontre dois fluxos máximos no grafo capacitado abaixo (veja figura ao lado) supondo que o vértice inicial é 0 e vértice final é 5.
```
0-1 0-2 0-3 1-2 1-3 1-4 2-4 2-5 3-4 3-5 4-5 
 20  30  20  10  10  10  10  20  20  30  20   
```
[Sedgewick 22.15] Encontre todos os fluxos máximos no grafo capacitado abaixo supondo que o vértice inicial é 0 e o vértice final é 5.
```
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  
```
Verificação do respeito à capacidade. Escreva uma função que receba um grafo capacitado com capacidades c[][], vértice inicial s, vértice final t, e um fluxo f[][] e verifique se f[][] respeita as capacidades. Também calcule a intensidade do fluxo.
[Sedgewick 22.2] Cota superior da intensidade. Suponha que um grafo capacitado tem V vértices e A arcos. Suponha ainda que as capacidades são números inteiros menores que uma constante M. Dê uma cota superior simples e grosseira para a intensidade de um fluxo que respeita as capacidades. (A cota não depende de quais sejam os vértices inicial e final.)
Certo ou errado? Se f é um fluxo máximo então não existe ciclo no qual todo arco conduz fluxo estritamente positivo.
Certo ou errado? Existe um fluxo máximo f tal que, para todo ciclo, f é nulo em algum arco do ciclo.
Certo ou errado? Se as capacidades forem distintas duas a duas, o fluxo máximo é único.
★ [Sedgewick 22.3] Fluxo em quase-árvore radicada. Seja G um grafo capacitado com vértice inicial s e vértice final t. Suponha que o grafo G − t é uma árvore radicada com raiz s. Descreva um algoritmo para calcular um fluxo máximo que respeite as capacidades.
Fluxo em dags. Mostre que a restrição do problema do fluxo máximo a dags não torna o problema mais fácil.
Emparelhamento bipartido. Mostre que problema do emparelhamento máximo num grafo não-dirigido bipartido é, essencialmente, um caso especial do problema do fluxo máximo.