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