Algoritmos para Grafos, via Sedgewick | Índice remissivo
Para representar redes capacitadas, poderíamos usar a estrutura de dados já empregada para digrafos com custos nos arcos, depois de substituir "custo" por "capacidade". Mas é conveniente definir uma nova estrutura, sob medida para tratar do problema do fluxo máximo. Em particular, é conveniente que a estrutura represente uma rede de fluxo, conforme a seguinte definição.
Uma rede de fluxo (= flow network) é uma
[Esta página é um resumo de parte da seção 22.1 (Flow Networks) do capítulo 22 (Network Flow) do livro de Sedgewick.]
Nossas redes de fluxo serão representadas por listas de adjacência. Como de hábito, cada arco v-w será representado por um nó na lista adj[v]. Além do campo w, esse nó terá
O nó terá ainda um campo dup, cujo uso será descrito mais adiante.
/* Copiado do programa 22.1, p.366, de Sedgewick. */
typedef struct node *link; struct node { Vertex w; int cap; int flow; link dup; link next; }; link NEW (Vertex w, int cap, int flow, link next) { link x = malloc(sizeof *x); x->w = w; x->cap = cap; x->flow = flow; x->next = next; return x; } struct flownet { int V, A; link *adj; Vertex s, t; }; typedef struct flownet *Flownet;
Eis algumas funções óbvias para construção de uma rede de fluxo:
Flownet FLOWinit (int V) { Vertex v; Flownet G = malloc(sizeof *G); G->adj = malloc(V * sizeof(link)); G->V = V; G->A = 0; for (v = 0; v < V; v++) G->adj[v] = NULL; return G; }/* Insere um arco v-w, de capacidade cap e fluxo nulo na rede G. */
void FLOWinsertA (Flownet G, Vertex v, Vertex w, int cap) { if (v == w || cap < 0) return; G->adj[v] = NEW(w, cap, 0, G->adj[v]); G->adj[v]->dup = G->adj[w]; G->A++; }
6 0 5
0-1 2
0-2 3
1-3 3
1-4 1
2-3 1
2-4 1
3-5 2
4-5 3
Preencha os campos flow dos arcos com zeros.
É difícil procurar (pseudo)caminhos de aumento numa rede de fluxo porque esses caminhos podem ter arcos inversos. Para contornar essa dificuldade, vamos introduzir o conceito de rede de fluxo expandida. Nessa rede, será possível trabalhar exclusivamente com caminhos (dirigidos).
Suponha dada uma rede de fluxo. Para cada arco v-w, acrescente à rede um arco w-v. Diremos que os novos arcos são artificiais e os antigos são originais (cada arco artificial é antiparalelo ao correspondente arco original). A capacidade de cada arco artificial w-v será, por definição, o negativo da capacidade do correspondente arco original v-w. O fluxo em cada arco artificial será o negativo do fluxo no correspondente arco original.
(É preciso admitir que a aplicação dos termos "capacidade" e "fluxo" aos arcos artificiais é abusiva, uma vez que esses números são tipicamente negativos.)
A rede que acabamos de construir será chamada rede de fluxo expandida, ou simplesmente rede expandida. Ela representa, com certas vantagens, a rede de fluxo original. [O conceito de rede expandida substitui, com vantagem, o conceito de "rede residual" de Sedgewick.]
(Se a rede original tiver arcos antiparalelos, a rede expandida terá arcos paralelos, o que entra em choque com nossa proibição de tais arcos. Felizmente, a estrutura de dados que definimos acima é capaz de representar arcos paralelos. Podemos, portanto, desrespeitar a proibição ao tratar de redes expandidas.)
A estrutura de dados que definimos acima para representar redes de fluxo também é capaz de representar redes expandidas: basta acrescentar os arcos artificiais à rede de fluxo original. O campo dup nos nós das listas de adjacência será usado para apontar de um arco original para o correspondente arco artificial e vice-versa. Para cada o arco artificial teremos
cap ≤ flow ≤ 0
e para cada o arco original teremos 0 ≤ flow ≤ cap.
Eis uma função que transforma uma rede de fluxo na correspondente rede de fluxo expandida:
/* Transforma uma rede de fluxo G na correspondente rede de fluxo expandida. */
void Expand (Flownet G) { Vertex s = G->s, t = G->t, v, w; link po, pa; int cap, flow; for (v = 0; v < G->V; v++) for (po = G->adj[v]; po != NULL; po = po->next) po->dup = NULL; for (v = 0; v < G->V; v++) for (po = G->adj[v]; po != NULL; po = po->next) if (po->dup == NULL) { w = po->w; cap = po->cap; flow = po->flow; G->adj[w] = pa = NEW(v, -cap, -flow, G->adj[w]); po->dup = pa; pa->dup = po; } }
Veja como é fácil calcular o saldo do fluxo num vértice v de uma rede de fluxo expandida:
/* A função flowV calcula o saldo de fluxo no vértice v de uma rede de fluxo expandida G. (Copiado do programa 22.2, p.367, de Sedgewick.) */
int flowV (Flownet G, Vertex v) { link p; int x = 0; for (p = G->adj[v]; p != NULL; p = p->next) x += p->flow; return x; }
A intensidade do fluxo nada mais é que o valor da expressão flowV(G, G->s).
Considere a rede de fluxo (não expandida) abaixo (esse exemplo é cópia de parte da figura 22.17, p.377, de Sedgewick).
arco cap flow s = 0
0-1 2 2 t = 5
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
A tabela seguinte mostra a correspondente rede de fluxo expandida. Os arcos artificiais estão pintados de vermelho.
arco cap flow
0-1 2 2
1-0 -2 -2
0-2 3 2
2-0 -3 -2
1-3 3 1
3-1 -3 -1
1-4 1 1
4-1 -1 -1
2-3 1 1
3-2 -1 -1
2-4 1 1
4-2 -1 -1
3-5 2 2
5-3 -2 -2
4-5 3 2
5-4 -3 -2
Um caminho (sem arcos inversos) de s a t na rede de fluxo expandida corresponde a um (pseudo)caminho de aumento na rede de fluxo original se os seus arcos originais têm fluxo menor que a capacidade e os seus arcos artificiais têm fluxo estritamente negativo, ou seja, se
para todo arco do caminho. Diremos, simplesmente, que um caminho com essas propriedades é um caminho de aumento na rede de fluxo expandida.
Cada arco da rede de fluxo expandida tem uma capacidade residual, definida da seguinte maneira. A capacidade residual de um arco original da rede expandida (ou seja, um arco com cap ≥ 0) é a diferença
cap - flow
e a capacidade residual de um arco artificial (ou seja, um arco com cap < 0) é
-flow .
(Note que essas capacidades residuais são números não negativos.) O código de nossas implementações calculará as capacidades residuais dos arcos da rede de fluxo expandida sempre da mesma maneira: Se v é um vértice e L é o endereço de um nó na lista adj[v] então o valor da expressão
L->cap >= 0 ? L->cap - L->flow : -L->flow
é a capacidade residual do arco (original ou artificial) que tem ponta inicial v e ponta final L->w.
A capacidade residual de um caminho (dirigido) na rede de fluxo expandida é a menor das capacidades residuais de seus arcos. (Observe como essa definição corresponde, precisamente, à definição de capacidade residual de um caminho de aumento na rede de fluxo original.) Um caminho de s a t na rede de fluxo expandida é um caminho de aumento se e somente se sua capacidade residual é estritamente positiva.
Considere a rede de fluxo (não expandida) abaixo. (Esse exemplo é cópia de parte da figura 22.17, p.377, de Sedgewick.)
arco cap flow s = 0
0-1 2 2 t = 5
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 tabela seguinte mostra os arcos da correspondente rede de fluxo expandida com suas capacidades residuais. Os arcos artificiais estão pintados de vermelho.
arco capres
0-1 0
1-0 2
0-2 2
2-0 1
1-3 1
3-1 2
1-4 1
4-1 0
2-3 1
3-2 0
2-4 0
4-2 1
3-5 0
5-3 2
4-5 2
5-4 1