Algoritmo de fluxo máximo e caminhos aumentadores curtos

Este capítulo descreve a camada interna da implementação do algoritmo de Ford-Fulkerson. Essa camada interna consiste na função AugmPath(), que tem a missão de calcular um caminho aumentador num grafo expandido.

A versão da função AugmPath() discutida neste capítulo produz um caminho aumentador de comprimento mínimo. Edmonds e Karp mostraram (1972) que, com essa versão de AugmPath(), o consumo de tempo de GRAPHmaxFlow() não depende das capacidades dos arcos, ao contrário do que acontece com a versão genérica do algoritmo.

Alguns arcos de G são originais enquanto outros são artificiais, mas a função ignora essa distinção (em particular, ignora os campos type e twin dos nós) e toma conhecimento apenas da capacidade residual cap - flow de cada arco. Essa capacidade residual é sempre positiva, embora o fluxo nos arcos artificiais seja negativo ou nulo. A função ShrtAugmPath() limita-se a calcular um caminho de s a t que tenha capacidade residual estritamente positiva e seja o mais curto possível sob essa restrição. O caminho é armazenado no par de vetores pa[] e parc[]. (Os nomes dos vetores são abreviaturas de parent e parent arc respectivamente.)

A função ShrtAugmPath() é uma mera adaptação da função GRAPHbfs() de busca em largura. O código usa uma fila de vértices manipulada pelas funções QUEUEinit(), QUEUEempty(), QUEUEput() e QUEUEget(), já discutidas.

/* Esta é a versão ShrtAugmPath() 
da função AugmPath(). */

#define AugmPath ShrtAugmPath

/* Esta função recebe um grafo capacitado G
   e um fluxo registrado nos campos flow 
   dos nós das listas de adjacência.
   Calcula um caminho de comprimento mínimo
   de s a t
   dentre os que têm capacidade residual estritamente positiva
   e armazena o caminho nos vetores 
   pa[] e parc[].
   Devolve a capacidade residual do caminho;
   se nenhum caminho de s a t
   tem capacidade residual estritamente positiva,
   devolve 0.
   A função supõe que todos os arcos têm capacidade menor
   que uma constante M. */

int ShrtAugmPath( Graph G, vertex s, vertex t,
                  vertex pa[], link parc[]) 
{ 
   bool visited[1000]; 
   for (vertex v = 0; v < G->V; ++v) visited[v] = false; 
   QUEUEinit( G->V); 
   visited[s] = true;
   QUEUEput( s); 

   while (!QUEUEempty( )) {
      vertex v = QUEUEget( );
      if (v == t) break;
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         // a pode ser original ou artificial
         int residual = a->c - a->flow;
         if (residual > 0 && !visited[a->w]) {
            visited[a->w] = true;
            pa[a->w] = v; parc[a->w] = a; 
            QUEUEput( a->w); 
         }
      }
   }

   if (!visited[t]) return 0; 
   int delta = M;
   for (vertex w = t; w != s; w = pa[w]) { 
      link a = parc[w]; 
      delta = min( delta, a->c - a->flow);
   }
   QUEUEfree( );
   return delta;
}

As últimas linhas do código calculam a capacidade residual, delta, do caminho armazenado em pa[] e parc[].

Exemplo A. Considere o seguinte grafo capacitado com vértice inicial 0 e vértice final 5. (Os arcos artificiais estão destacados em vermelho.) As capacidades estão indicadas na segunda linha. Um fluxo de intensidade 1 está indicado na terceira linha.

A função ShrtAugmPath() ignora a distinção entre arcos vermelhos e pretos e produz o caminho aumentador

que tem capacidade residual 1. (Nesse exemplo, todos os arcos do caminho aumentador são originais.)

Exemplo B. Considere o grafo capacitado abaixo. A tabela mostra apenas os arcos originais e suas capacidades. Os vértices inicial e final são 0 e 13 respectivamente.

A função GRAPHmaxFlow() combinada com ShrtAugmPath() produz a seguinte sequência de caminhos aumentadores a partir do fluxo nulo. Os arcos artificiais estão indicados em vermelho. (Mas ShrtAugmPath() ignora a distinção entre arcos artificiais e originais.) Cada caminho aumentador tem comprimento mínimo. O comprimento e a capacidade residual de cada caminho estão registrados na segunda e terceira colunas respectivamente.

Esses caminhos aumentadores produzem a seguinte sequência de fluxos (leia na vertical, com - representando 0):

A tabela mostra apenas os arcos originais. O fluxo final tem intensidade 30. Veja as duas margens de um corte de capacidade 30:

Exercícios 1

Verifique que o exemplo B está correto. Em particular, confira o corte mínimo.
Que acontece se GRAPHmaxFlow(), e portanto também ShrtAugmPath(), forem invocados com s igual a t? (Convém lembrar, entretanto, que o enunciado do problema do fluxo máximo exige que s seja diferente de t.)
Vetor auxiliar supérfluo. O vetor pa[] no código de ShrtAugmPath() é supérfluo pois pa[x] é sempre igual a parc[x]->twin->w. Reescreva ShrtAugmPath()() sem o vetor pa[].
Mostre o rastro da aplicação da função GRAPHmaxFlow() combinada com ShrtAugmPath() ao grafo capacitado descrito a seguir. Os vértices inicial e final são 0 e 7 respectivamente.
```
0-1 1-2 2-4 0-3 3-4 3-5 5-6 6-7 4-7  
  3   3   3   2   1   2   2   2   3 
```
Mostre o rastro da aplicação da função GRAPHmaxFlow() combinada com ShrtAugmPath() ao grafo capacitado descrito a seguir. Os vértices inicial e final são 0 e 7 respectivamente.
```
0-1 1-2 2-4 0-3 3-4 3-5 5-6 6-7 4-7  
  4   4   4   2   1   3   3   3   3 
```
Corte mínimo. Escreva uma função booleana que decida se um dado fluxo é máximo. Ao receber um grafo capacitado com vértice inicial e final e um certo fluxo, a função deve devolver true se o fluxo é máximo e false em caso contrário. Se devolver true, a função deve também gravar (no endereço indicado pelo usuário) o vetor característico da margem superior de um corte de capacidade mínima. (É claro que a capacidade desse corte deve ser igual à intensidade do fluxo.) Esse corte servirá de certificado da maximalidade do fluxo.

Desempenho do algoritmo do fluxo máximo

O consumo de tempo da função GRAPHmaxFlow() é proporcional ao número de caminhos aumentadores necessário para atingir o fluxo máximo. Quantos caminhos a função ShrtAugmPath() calcula, no pior caso?

A prova dessa propriedade depende do conceito de arco crítico. Um arco de um caminho aumentador é crítico se tiver capacidade residual mínima no caminho. Ou seja, um arco é crítico se sua capacidade residual é igual à capacidade residual, delta, do caminho. Depois da operação de envio de delta unidades de fluxo ao longo do caminho aumentador, a capacidade dos arcos críticos é reduzida a zero e portanto o arco não poderá ser usado pelo caminho aumentador seguinte. (Mas poderá vir a ser usado por caminhos aumentadores subsequentes se sua capacidade residual aumentar nesse meio tempo.)

Essas duas observações não são óbvias; sua prova exige algum esforço e será omitida.

Como todo caminho aumentador tem comprimento menor que V, cada arco do grafo pode ser crítico em não mais que V/2 caminhos aumentadores. Portanto, o número total de caminhos aumentadores é menor que VA/2, como queríamos provar. (Em geral, o número de caminhos aumentadores é muito menor que VA/2.)

Exercícios 2

Seja G um grafo expandido com um certo fluxo. Suponha que P é um caminho aumentador no grafo. Depois que uma certa quantidade de fluxo for enviada ao longo de P, é possível que algum arco artificial de P fique com capacidade residual nula?
Seja G um grafo expandido com um certo fluxo. Suponha que um arco arficial a de G tem capacidade residual nula. Suponha que enviamos uma certa quantidade de fluxo ao longo de algum caminho aumentador. Depois dessa operação, é possível que a capacidade residual do arco a fique estritamente positiva?
Prove a propriedade que limita o número de caminhos aumentadores.

Fluxo máximo via caminhos aumentadores mínimos

Cálculo de um caminho aumentador mínimo

Exercícios 1

Desempenho do algoritmo do fluxo máximo

Exercícios 2