O problema do fluxo máximo entre dois nós de uma rede é fundamental em otimização combinatória. O correspondente teorema Max-flow Min-cut é uma poderosa ferramenta com muitas aplicações.
(Consulte o índice remissivo e os apêndices para conferir as definições de termos técnicos.)
Um fluxo em um grafo dirigido $D$ é qualquer função de $E(D)$ em $\Rplus$. Em outras palavras, um fluxo é uma função que atribui um número real não-negativo a cada arco de $D$. [Poderíamos nos restringir aos números racionais, uma vez que computadores digitais não conhecem números irracionais.]
Se $x$ é um fluxo e $R$ é um conjunto de nós do grafo, denotamos por $x(\cutin(R))$ a soma dos valores de $x$ nos arcos de $\cutin(R)$, ou seja, nos arcos que entram em $R$. Convém simplificar essa expressão e escrever apenas $\xin(R)$. Portanto, \[\textstyle \xin(R) := \sum \left( x_{uv} : uv \in \cutin(R) \right)\text{.} \]
Analogamente, denotamos por $\xout(R)$ a soma dos valores de $x$ nos arcos que saem de $R$: \[\textstyle \xout(R) := \sum \left( x_{vw} : vw \in \cutout(R) \right)\text{.} \]
[Para justificar
os superscritos $+$
e $-$
,
você pode imaginar que os nós são contas bancárias
e os arcos representam movimentação de dinheiro:
tudo que entra numa conta é somado ao saldo
e tudo que sai é subtraído.]
É claro que $\xout(R) = \xin(\compl{R})$,
sendo $\compl{R} := \text{}$ $V(D)\setm R$.
O excesso,
ou acúmulo,
ou saldo
(= net flow)
de $x$ em $R$
é a quantidade
de fluxo
que fica retida
em $R$.
Esse excesso é denotado por $\xinout(R)$:
\[
\xinout(R) := \xin(R) \ - \ \xout(R)\:\text{.}
\]
Se $R=\conj{v}$, escrevemos simplesmente $\xinout(v)$, $\xin(v)$ e $\xout(v)$.
Lema 2.1 (soma de excessos) Para qualquer fluxo $x$ em um grafo dirigido $D$ e qualquer subconjunto $R$ de $V(D)$, a soma dos excessos nos nós de $R$ é igual ao excesso em $R$: \[\textstyle \sum_{v\in R}\, \xinout(v) = \xinout(R)\,\text{.} \]
Prova: Para mostrar que $\sum_{v\in R} \xin(v) - \sum_{v\in R} \xout(v) = \text{}$ $\xin(R)-\xout(R)$, basta verificar que cada arco do grafo dá a mesma contribuição para o lado esquerdo e o lado direito dessa igualdade.
Um arco $ij$ que tem ambas as pontas em $R$ contribui $x_{ij}$ para a primeira somatória e $x_{ij}$ para a segunda somatória, e portanto a contribuição total para o lado esquerdo é nula. A contribuição de $ij$ para o lado direito também é nula. Um raciocínio análogo mostra que é nula a contribuição dos arcos que têm ambas as pontas em $\compl{R}$.
Um arco que entra em $R$ contribui apenas para a primeira somatória do lado esquerdo e para o primeiro termo do lado direito. Analogamente, um arco que sai de $R$ contribui apenas para a segunda somatória do lado esquerdo e o segundo termo do lado direito. Resumindo: cada arco com uma ponta em $R$ e outra em $\compl{R}$ dá a mesma contribuição para os dois lados da igualdade. ■
Uma circulação
(= circulation)
em uma grafo dirigido é qualquer fluxo que tenha excesso nulo em cada nó.
Mais precisamente, uma circulação é qualquer fluxo $x$ tal que
\[
\xinout(v) = 0
\]
para cada nó $v$.
(Essa igualdade é conhecida como conservação de fluxo
em $v$.)
Segue do lema 2.1 que a quantidade
de circulação que atravessa um corte
da esquerda para a direita
é igual à quantidade
que atravessa o corte da direita para a esquerda
:
Corolário 2.2 Para qualquer circulação $x$ e qualquer conjunto $R$ de nós, vale a igualdade $\xout(R) = \xin(R)$. ■
Qualquer família de ciclos dirigidos define uma circulação. (Poderíamos nos restringir a ciclos simples, mas isso não afetaria os conceitos.) Se $C_1,\ldots,C_j$ é uma família de ciclos dirigidos e $x_e$ é o número desses ciclos que contêm o arco $e$ então $x$ é uma circulação. Reciprocamente, toda circulação pode ser representada por uma família de ciclos dirigidos, como mostramos a seguir.
Lema 2.3 (decomposição em ciclos) Para toda circulação $x$ em um grafo dirigido, existem ciclos dirigidos simples $C_1,\ldots,C_j$, com $j \leq m$, e números positivos $\alpha_1, \ldots, \alpha_j$ tais que $\sum_{C_i \ni e} \alpha_i = x_e$ para cada arco $e$.
Esboço da prova: Seja $E'$ o suporte de $x$, isto é, o conjunto dos arcos $e$ tais que $x_e\neq 0$. Se $E'$ é vazio, a conclusão do lema vale com $j=0$. Senão, seja $D'$ o subgrafo de $D$ induzido por $E'$. Como $\xin(v) = \xout(v) \neq 0$ para cada nó $v$, o grafo $D'$ tem um ciclo dirigido simples, digamos $C$. Seja $\alpha := \min_{e\in E(C)} x_e$ e subtraia $\alpha$ de $x_e$ para cada arco $e$ de $C$. Essa operação produz uma nova circulação. Repita o processo com a nova circulação. ■
Exemplo 2.1: A tabela mostra uma circulação $x$ no grafo da figura.
Esta circulação pode ser decomposta nos ciclos dirigidos $(1,2,4,5,1)$ e $(1,4,5,1)$. O primeiro ciclo conduz $2$ unidades de fluxo e o segundo conduz $1$ unidade.
Dados dois nós $r$ e $s$ de um grafo dirigido, um fluxo de $r$ a $s$ é qualquer fluxo que tenha excesso nulo em todos os nós exceto $r$ e $s$ e excesso não-negativo em $s$. Mais precisamente, $x$ é um fluxo de $r$ a $s$ se $\xinout(s)\geq 0$ e \[ \xinout(v) = 0 \]
para todo nó $v$ distinto de $r$ e de $s$.
O excesso de $x$ em $s$ é a intensidade,
ou valor,
de $x$.
É conveniente ter uma notação especial para a intensidade do fluxo $x$:
\[
\intens(x) := \xinout(s)\text{.}
\]
(É preciso ficar atento para não confundir
$\intens$
com inteiro
!)
Dizemos que um conjunto $R$ de nós separa $r$ de $s$ se $r\in R$ e $s\notin R$. Em virtude do lema 2.1, a intensidade de um fluxo de $r$ a $s$ pode ser medida em qualquer dos conjuntos que separam $r$ de $s$:
Lema 2.4 Para qualquer fluxo $x$ de $r$ a $s$ e qualquer conjunto $R$ que separa $r$ de $s$, tem-se $\intens(x) = - \xinout(R)$, ou seja, a intensidade de $x$ é igual à diferença $\xout(R) - \xin(R)$. ■
Em particular, a intensidade do fluxo $x$ é igual ao excesso de $x$ em $r$ com sinal trocado, ou seja, $\intens(x) = - \xinout(r)$.
Qualquer família de caminhos dirigidos de $r$ a $s$ define um fluxo. (Poderíamos nos restringir a caminhos simples, mas isso não afetaria os conceitos.) Se $P_1,\ldots,P_k$ é uma família de caminhos dirigidos de $r$ a $s$ e $x_e$ é o número desses caminhos que contêm o arco $e$ então $x$ é um fluxo de $r$ a $s$ de intensidade $k$. Reciprocamente, todo fluxo de $r$ a $s$ pode ser representado por uma família de caminhos (e ciclos) dirigidos:
Lema 2.5 (decomposição em caminhos e ciclos) Para todo fluxo $x$ de $r$ a $s$ em um grafo dirigido, existem ciclos dirigidos simples $C_1,\ldots,C_j$ e caminhos dirigidos simples $P_1,\ldots, P_k$ de $r$ a $s$, com $j+k \leq m$, e existem números positivos $\alpha_1,\ldots,\alpha_j,$ $\beta_1,\ldots,\beta_k$, tais que $\beta_1+\cdots+\beta_k = \text{}$ $\intens(x)$ e \[\textstyle \sum_{C_i \ni e} \alpha_i + \sum_{P_i \ni e} \beta_i = x_e \] para cada arco $e$.
Esboço da prova: Seja $E'$ o suporte de $x$. Seja $D'$ o grafo $(V,E')$. Graças ao lema 2.1, se $\intens(x) > 0$ então existe um caminho dirigido de $r$ a $s$ em $D'$. Seja $P$ esse caminho e $\beta := \min_{e\in E(P)} x_e$. Subtraia $\beta$ de $x_e$ para cada $e$ em $P$. Isso produz um novo fluxo de $r$ a $s$. A intensidade do novo fluxo é $\intens(x)-\beta$. Repita o processo até obter um fluxo de intensidade $0$. Esse fluxo será uma circulação, e portanto o lema 2.3 poderá ser aplicado. ■
Exemplo 2.2: A tabela mostra um fluxo $x$ de $0$ a $5$ no grafo da figura.
Este fluxo pode ser decomposto em três caminhos dirigidos e um ciclo dirigido: $(0,3,5)$, $(0,4,5)$, $(0,2,4,5)$ e $(1,4,5,1)$. Os caminhos conduzem $3$, $2$ e $1$ unidades de fluxo respectivamente. O ciclo conduz $4$ unidades de fluxo.
Seja $D$ um grafo dirigido e $u$ uma função que leva $E(D)$
em $\Rplus$.
[A letra $u$ é a inicial de
upper bound.
Não haveria prejuízo
se disséssemos que $u$ leva $E(D)$
em $\Qplus$.]
Dizemos que $u$ é uma função-
Dizemos que um fluxo $x$ numa rede capacitada $(D,u)$ respeita as capacidades dos arcos se $x \leq u$, ou seja, se $x_{e} \leq u_{e}$ para cada arco $e$.
Problema 2.A (fluxo máximo) Dados nós $r$ e $s$ de uma rede capacitada $(D,u)$, encontrar um fluxo de $r$ a $s$ que respeite $u$ e tenha intensidade máxima.
Dizemos que $r$ é o nó inicial da rede e $s$ é o nó final. Podemos incorporar esses nós à definição da rede e dizer que $(D,u,r,s)$ é uma rede de fluxo.
Para simplificar a discussão do problema,
adotamos algumas abreviaturas.
Dizemos que um fluxo é viável
se vai de $r$ a $s$
e respeita $u$.
Dizemos também fluxo viável máximo
no lugar de fluxo viável de intensidade máxima
.
Podemos até mesmo dizer fluxo máximo
,
subentendendo o viável
.
Toda instância do problema tem solução. Com efeito, toda instância tem um fluxo viável (o fluxo nulo, por exemplo) e toda instância tem um fluxo máximo (uma vez que a intensidade de qualquer fluxo não passa da soma das capacidades de todos os arcos).
Seja $(D,u)$ uma rede capacitada. Para qualquer conjunto $R$ de nós de $D$, a capacidade do corte $\cutout(R)$ é a soma das capacidades dos arcos que saem de $R$. Essa soma é denotada por $u(\cutout(R))$. Para simplificar, podemos até escrever $\uout(R)$. Portanto, \[\textstyle \uout(R) := \sum_{e\in \cutout(R)} u_e\,\text{.} \] É conveniente ter uma notação especial para a capacidade de um corte. Assim, se $C:=\cutout(R)$ então \[ \capac(C) := \uout(R)\,\text{.} \]
Os cortes mais relevantes numa rede de fluxo $(D,u,r,s)$ são os que separam $r$ de $s$. Dizemos que um corte $\cutout(R)$ separa $r$ de $s$ se $r\in R$ e $s\notin R$. Usamos também a expressão $(r,s)$-corte para designar um corte que separa $r$ de $s$.
Exemplo 2.3: Seja $D$ o grafo dirigido com nós $r \ v \ w \ s$ descrito abaixo por sua matriz de adjacências. À direita, uma função-capacidade $u$.
Os conjuntos $R_1=\conj{r,v}$, $R_2=\conj{r,w}$ e $R_3=\conj{r,v,w}$ separam $r$ de $s$ e os correspondentes cortes têm capacidades $22$, $14$ e $16$ respectivamente.
Segue imediatamente do lema 2.4 que a capacidade de qualquer corte que separa $r$ de $s$ limita a intensidade de todo fluxo viável:
Lema 2.6 (fluxo versus corte) Para qualquer fluxo $x$ de $r$ a $s$ que respeita as capacidades e qualquer corte $C$ que separa $r$ de $s$, vale a desigualdade $\intens(x) \leq \capac(C)$. ■
O lema leva ao seguinte critério de maximalidade para fluxos: dado um fluxo viável $x$, se $\intens(x) = \capac(C)$ para algum corte $C$ que separa $r$ e $s$ então $x$ é máximo, ou seja, $x$ é solução do problema 2.A.
O lema também leva ao seguinte critério de minimalidade para cortes: dado um $(r,s)$-corte $C$, se $\capac(C) = \intens(x)$ para algum fluxo viável $x$ então $C$ é mínimo, ou seja, tem capacidade mínima dentre todos os cortes que separam $r$ de $s$.
Surpreendentemente, a recíproca do critério de maximalidade enunciado depois do lema 2.6 é verdadeira. A prova desse fato foi publicada (1956) por Ford e Fulkerson e por Kotzig:
Teorema 2.7 Em qualquer rede de fluxo $(D,u,r,s)$, para qualquer fluxo viável $x$ de intensidade máxima existe um $(r,s)$-corte $C$ tal que $\intens(x) = \capac(C)$.
A prova do teorema usa a técnica dos caminhos de aumento, que passamos a descrever. Um caminho (não necessariamente dirigido) é compatível com um fluxo viável $x$ se (i) é quase-simples; (ii) seus arcos diretos não estão cheios de fluxo; e (iii) seus arcos inversos não estão vazios de fluxo. Em outras palavras, um caminho quase-simples $P$ é compatível com $x$ se
$x_{e} \lt u_e\ph{0}$
para cada arco direto $e$ de $P$ e
$x_{e} > 0\ph{u_e}$
para cada inverso $e$ de $P$.
Um caminho de aumento (= augmenting path) é qualquer caminho compatível com $x$ que vai $r$ a $s$. A largura (= width) de um caminho de aumento $P$ é o maior número $\epsilon$ tal que $x_e - \epsilon \geq 0$ para cada arco inverso $e$ de $P$ e $x_e + \epsilon \leq u_{e}$ para cada arco direto $e$ de $P$. Dada a largura $\epsilon$ de um caminho de aumento $P$, podemos executar a seguinte operação de envio de $\epsilon$ unidades de fluxo ao longo de $P$:
para cada arco direto $e$ de $P$, some $\epsilon$ a $x_e$;
para cada arco inverso $e$ de $P$, subtraia $\epsilon$ de $x_e$.
Essa operação produz um novo fluxo que é viável e tem intensidade $\intens(x) + \epsilon$. Como $\epsilon$ é positivo, a intensidade do novo fluxo é maior que a de $x$.
Prova do teorema 2.7: Seja $x$ um fluxo máximo. Queremos encontrar um corte que separe $r$ de $s$ e tenha capacidade igual a $\intens(x)$.
Seja $R$ o conjunto de todos os nós que são término de algum caminho que começa em $r$ e é compatível com $x$. Suponha por um instante que $s\in R$ e seja $P$ um caminho compatível com $x$ que começa em $r$ e termina em $s$. É claro que $P$ é um caminho de aumento. Seja $\epsilon$ a largura de $P$. O envio de $\epsilon$ unidades de fluxo ao longo de $P$ produz um novo fluxo viável que tem intensidade maior que a de $x$. Mas isso é contraditório, pois $x$ tem intensidade máxima por hipótese. Concluímos assim que $s \notin R$ e portanto $R$ separa $r$ de $s$.
A definição de $R$ garante que $x_{e} = u_{e}$ para cada $e$ em $\cutout(R)$ e $x_{e} = 0$ para cada $e$ em $\cutin(R)$. Em outras palavras, todos os arcos que saem de $R$ estão cheios de fluxo, e todos os arcos que entram em $R$ estão vazios de fluxo. Portanto, \[ \xout(R) = \uout(R) \quad\mbox{e}\quad \xin(R) = 0\,\text{.} \] O lema 2.4 permite dizer então que $\xout(R) - \xin(R)$ $\text{} = \uout(R)$. Assim, $\intens(x) = \text{}$ $\capac(\cutout(R))$, como queríamos mostrar. ■
Exemplo 2.4: A tabela abaixo descreve uma fluxo viável $x$ na rede $(D,u,r,s)$ do exemplo 2.3.
A sequência de nós $\seq{r,w,v,s}$ define um caminho de aumento. A largura desse caminho é $2$. É fácil calcular o fluxo $x'$ que resulta do envio de $2$ unidades de fluxo ao longo do caminho de aumento. Feito isso, é fácil calcular um $(r,s)$-corte mínimo.
A prova do teorema 2.7, combinada com o lema 2.6, produz a seguinte manifestação da condição de folgas complementares da programação linear:
Corolário 2.8 (folgas complementares) Seja $x$ um fluxo viável e $R$ um conjunto de nós que separa $r$ de $s$. O fluxo $x$ é máximo se e somente se $x_e = u_e$ para cada $e$ em $\cutout(R)$ e $x_e = 0$ para cada $e$ em $\cutin(R)$. ■
Exemplo 2.5: A tabela abaixo descreve uma fluxo viável $x$ na rede $(D,u,r,s)$ do exemplo 2.3.
O conjunto $R=\conj{r,w}$ é a margem negativa de um corte de capacidade $14$. Temos $\intens(x) = \capac(\cutout(R))$. Observe que $\xout(R)=\uout(R)$ e $\xin(R)=0$.
A combinação do teorema 2.7
com o lema 2.6
pode ser resumida no seguinte teorema,
conhecido pelas iniciais MFMC
de Max-Flow Min-Cut
:
Teorema 2.9 (MFMC) Em qualquer rede de fluxo $(D,u,r,s)$, vale a igualdade \[ \max_x \, \intens(x) \ = \ \min_C \, \capac(C)\,\text{,} \] sendo $\max_x$ tomado sobre todos os fluxos viáveis $x$ e $\min_C$ tomado sobre todos os cortes $C$ que separam $r$ de $s$. ■
Um fluxo $x$ é inteiro se $x_e \in \Zplus$ para todo arco $e$. Analogamente, uma função-capacidade $u$ é inteira se $u_e \in \Zplus$ para todo $e$. Surpreendentemente, basta que a função-capacidade seja inteira para que exista um fluxo máximo inteiro:
Teorema 2.10 (MFMC inteiro) Em qualquer rede de fluxo $(D,u,r,s)$, se a função-capacidade $u$ é inteira então algum fluxo viável máximo é inteiro.
Prova: Refaça a prova do teorema 2.7 começando com o fluxo nulo. A largura $\epsilon$ de qualquer caminho de aumento será inteira. Portanto, o envio de $\epsilon$ unidades de fluxo ao longo de um caminho de aumento produzirá um novo fluxo inteiro. ■
para provar que o fluxo $x$ é máximo basta mostrar que não existe caminho de aumento para $x$.
A prova do teorema 2.7 sugere um algoritmo iterativo para calcular um fluxo máximo e um corte mínimo. Esse é o algoritmo de Ford–Fulkerson, ou algoritmo dos caminhos de aumento:
| FordFulkerson $(D, \ u, \ r, \ s)$ |
| 01 . $x\larr 0$ |
| 02 . repita |
| 03 .ooo $R\larr \text{}$ CaminhosCompatíveis $(D,u,r,x)$ |
| 04 .ooo se $s\notin R$ |
| 05 .oooooo então devolva $x$ e $R$ e pare $\rhd$ solução |
| 06 .ooo $P \larr \text{}$ CaminhoDeAumento $(D,u,r,x)$ |
| 07 .ooo $\epsilon_1 \larr \min\,(u_{e}-x_{e} : e\in \Eforward(P))$ |
| 08 .ooo $\epsilon_2 \larr \min\,(x_{e} : e\in \Ereverse(P))$ |
| 09 .ooo $\epsilon \larr \min\,(\epsilon_1,\epsilon_2)$ |
| 10 .ooo $x \larr \text{}$ EnviaFluxo $(D,x,P,\epsilon)$ |
Na linha 05, $\cutout(R)$ é um corte de capacidade igual à intensidade do fluxo $x$. Portanto, o fluxo é máximo (e o corte é mínimo).
Na linha 03, a rotina CaminhosCompatíveis devolve o conjunto dos términos de todos os caminhos compatíveis com $x$ que começam em $r$. Na linha 06, a rotina CaminhoDeAumento produz um caminho de aumento para $x$ (supondo que um tal caminho existe).
Nas linhas 07 e 08, a expressão $\Eforward(P)$ denota o conjunto dos arcos diretos do caminho $P$ e $\Ereverse(P)$ denota o conjunto dos arcos inversos de $P$.
Na linha 10, a rotina EnviaFluxo envia $\epsilon$ unidades de fluxo ao longo do caminho $P$ e devolve o fluxo resultante.
Número de iterações. Se $u_e\in \Qplus$ para todo arco $e$ (ou seja, se as capacidades são números racionais) é possível mostrar que a execução do algoritmo termina depois de um número finito de iterações. O número de iterações pode depender dos valores de $u$; portanto, o algoritmo é apenas pseudopolinomial.
O algoritmo de Ford–Fulkerson não estabelece um critério para escolher um caminho de aumento quando há mais de um. Com isso, o algoritmo pode vir a executar um número muito grande de iterações. Uma ideia natural e intuitiva é usar apenas caminhos de aumento de comprimento mínimo. Edmonds e Karp mostraram (1972) que esse aperfeiçoamento faz com que o algoritmo execute no máximo $nm$ iterações, sendo $n$ o número de nós e $m$ o número de arcos do grafo.
Teorema 2.11 (Edmonds–Karp) Se cada iteração do algoritmo de Ford–Fulkerson usar um caminho de aumento de comprimento mínimo, o algoritmo não fará mais que $n m$ iterações.
Esboço da prova: No início de cada iteração temos um fluxo viável $x$. Digamos que um caminho na rede é bom se for um caminho de aumento de comprimento mínimo. Digamos que um arco é bom se pertence a algum caminho bom. Digamos que o comprimento da rede é o comprimento de um caminho bom.
Se o comprimento da rede não muda de uma iteração para a seguinte, o conjunto dos arcos bons encolhe, ou seja, torna-se um subconjunto próprio do anterior. Segue daí que no máximo $m$ iterações consecutivas podem ocorrer enquanto o comprimento da rede permanecer constante.
Por outro lado, o comprimento da rede nunca diminui de uma iteração para a seguinte. Como o comprimento da rede não pode aumentar mais que $n$ vezes e há no máximo $m$ iterações entre dois aumentos consecutivos do comprimento, o número total de iterações não passa de $nm$. ■
Consumo de tempo. Para procurar caminhos de aumento de comprimento mínimo, basta implementar as rotinas CaminhosCompatíveis e CaminhoDeAumento conjuntamente usando uma adaptação da busca em largura. Essa adaptação exige atenção pois a versão original da busca em largura procura caminhos dirigidos enquanto aqui procuramos por caminhos não necessariamente dirigidos. Podemos usar um grafo dirigido auxiliar $(V(D),E')$ definido assim: $vw \in E'$ se e somente se $vw\in E(D)$ e $x_{vw} \lt u_{vw}$ ou $wv\in E(D)$ e $x_{wv} > 0$. Os caminhos dirigidos nesse grafo auxiliar correspondem aos caminhos compatíveis com $x$ no grafo original.
Cada iteração desse algoritmo auxiliar consome $\Oh(m)$ unidades de tempo. Como o número de iterações não passa de $nm$, o algoritmo todo consome \[ \Oh(n m^2) \] unidades de tempo. Essa delimitação não depende de $u$, e portanto podemos dizer que o algoritmo é fortemente polinomial.
quantidadede fluxo que pode passar por $v$. Como resolver o problema de determinar um fluxo máximo que respeite as capacidades dos nós e as capacidades dos arcos? Transforme esse problema em um problema padrão de fluxo máximo (que só tem capacidades nos arcos). Do ponto de vista da complexidade de pior caso, o problema com capacidades nos nós é mais difícil que o problema padrão? [AMO 6.25]
O problema 2.A do fluxo máximo pode ser formulado muito naturalmente na linguagem da programação linear: dada uma rede de fluxo $(D,u,r,s)$, encontrar um vetor $(x_e : e\in E)$ que \begin{equation}\label{lp:max-flow-1} \begin{split} \text{maximize} \enspace \xinout(s) & \\ \text{sob as restrições} \enspace \xinout(v) & \ = \ 0 \enspace \text{para $v$ em $V\setm \conj{r,s}$}\\ x_e & \ \leq \ u_e \enspace \text{para $e$ em $E$}\\ x_e & \ \geq \ 0 \enspace \text{para $e$ em $E$} \end{split} \end{equation}
sendo $V:=V(D)$ e $E:=E(D)$. Todo fluxo viável na rede $(D,u,r,s)$ é solução viável desse pl. Reciprocamente, toda solução viável do pl é um fluxo viável na rede. Portanto, $x$ é um fluxo de intensidade máxima se e somente $x$ é solução ótima do pl.
Convém escrever o pl \eqref{lp:max-flow-1} em notação matricial. Seja $A$ a matriz de incidências de $D$ e $\Id$ a matriz identidade indexada por $E\times E$. Além disso, adote as abreviaturas $V' := V\setm \conj{r,s}$, $A' := A[V',E]$ e $c := A[s,E]$. Com essa notação, o pl \eqref{lp:max-flow-1} fica assim: \begin{equation}\label{lp:max-flow-1-matrix} \begin{split} \text{maximize} \quad cx & \\ \text{sob as restrições} \quad A' x & \ = \ 0\\ \Id x & \ \leq \ u\\ x & \ \geq \ 0 \end{split} \end{equation}
sendo o primeiro $0$
o vetor nulo
indexado por $V'$
e o segundo $0$
o
vetor nulo indexado por $E$.
Programa dual. O dual do pl \eqref{lp:max-flow-1-matrix} consiste em encontrar um vetor $(y'_v : v\in V')$ e um vetor $(z_e : e \in E)$ que \begin{equation}\label{lp:min-cut-1-matrix} \begin{split} \text{minimizem} \quad y'0+zu & \\ \text{sob as restrições} \quad y'A' + z\Id & \ \geq \ c\\ z & \ \geq \ 0\,\text{.} \end{split} \end{equation}
(Para comprovar a relação de dualidade, considere a sequência de desigualdades $cx \leq (y'A' + z \Id) x = \text{}$ $y' (A' x) + z (\Id x) = \text{}$ $y' 0 + zx \leq \text{}$ $y' 0 + zu$ que prova o teorema fraco da dualidade e observe que essa sequência usa todas as restrições dos dois pl's.) Veja o pl \eqref{lp:min-cut-1-matrix} escrito por extenso: \begin{equation}\label{lp:min-cut-1} \begin{array}{rl} \text{minimize} \enspace \textstyle\sum (z_{vw}u_{vw} : vw \in E) & \\[0.5ex] \text{sujeito a} \enspace y'_w - y'_v + z_{vw} \geq \ph{-}0 & \text{ $vw$ em $E$ com $v$ e $w$ em $V'$} \\ \ph{y'_w} - y'_v + z_{vr}\hspace{0.5ex} \geq \ph{-}0 & \text{ $vr$ em $E$ com $v$ em $V'$} \\ y'_w \ph{{}- y'_r} + z_{rw}\hspace{0.2ex} \geq \ph{-}0 & \text{ $rw$ em $E$ com $w$ em $V'$} \\ \ph{y'_w} - y'_v + z_{vs}\hspace{0.5ex} \geq \ph{-}1 & \text{ $vs$ em $E$ com $v$ em $V'$} \\ y'_w \ph{{}- y'_s} + z_{sw}\hspace{0.2ex} \geq -1 & \text{ $sw$ em $E$ com $w$ em $V'$} \\ z_{rs}\hspace{0.7ex} \geq \ph{-}1 & \text{ se $rs \in E$} \\ z_{sr}\hspace{0.7ex} \geq -1 & \text{ se $sr \in E$} \\ z_{vw}\hspace{0.2ex} \geq \ph{-}0 & \text{ $vw$ em $E$.} \end{array} \end{equation}
Para tornar este pl mais simples,
acrescentaremos duas componentes constantes
ao vetor $y'$.
Mais precisamente, substituiremos $y'$ por um vetor $y$ indexado por $V$
tal que $y_r := 1$, $y_s := 0$ e
$y_v := y'_v$ para cada $v$ em $V'$.
Com isso,
as restrições $y_w - y_v + z_{vw} \geq 0$ podem ser aplicadas
a todos os arcos sem exceção e
absorvem as restrições
$z_{rs} \geq 1$ se $rs \in E$
e $z_{sr} \geq -1$ se $sr \in E$.
O pl \eqref{lp:min-cut-1}
pode então ser escrito assim:
\begin{equation}\label{lp:min-cut-2}
\begin{split}
\text{minimize} \enspace \textstyle\sum (z_{vw}u_{vw} : vw \in E) & \\
\text{sob as restrições} \hspace{12ex}
y_r \ & = \ 1 \\
y_s \ & = \ 0 \\
y_w - y_v + z_{vw} \ & \geq \ 0 \quad \text{para $vw$ em $E$} \\
z_{vw} \ & \geq \ 0 \quad \text{para $vw$ em $E$.}
\end{split}
\end{equation}
Para todos os efeitos, este é o dual do pl \eqref{lp:max-flow-1}.
O pl \eqref{lp:min-cut-2} está intimamente relacionado com o problema do corte mínimo. Com efeito, se $\cutout(R)$ é um corte que separa $r$ de $s$ e $y$ é o vetor característico de $R$ e $z$ é o vetor característico de $\cutout(R)$ então $(y,z)$ é uma solução viável do pl. A recíproca vale para soluções binárias: qualquer solução viável binária $(y,z)$ de \eqref{lp:min-cut-2} é o vetor característico de um corte que separa $r$ de $s$.
O problema do fluxo máximo (problema 2.A) pode também ser formulado como um programa linear que representa a decomposição de fluxos em caminhos e ciclos (lema 2.5). Se denotarmos por $\Pcal$ o conjunto de todos os caminhos dirigidos simples de $r$ a $s$, o problema pode ser formulado assim: encontrar um vetor $(w_P : P\in \Pcal)$ que \begin{equation}\label{lp:max-weight-collection-of-paths} \begin{split} \text{maximize} \enspace \textstyle\sum (w_P :P \in\Pcal) & \\ \text{sujeito a} \enspace \textstyle\sum (w_P : e \in P \in \Pcal) & \leq u_e \quad \text{para $e \in E$}\\ w_P & \geq 0 \quad \text{para $P \in \Pcal$.} \end{split} \end{equation}
O número de variáveis é enorme, pois $|\Pcal|$ pode aumentar exponencialmente com o número de nós. Ainda assim, o pl é conceitualmente interessante. O dual do pl consiste em encontrar um vetor $(z_e : e\in E)$ que \begin{equation}\label{lp:cut-all-paths} \begin{split} \text{minimize} \enspace \textstyle\sum (z_eu_e : e \in E) & \\ \text{sujeito a} \enspace \textstyle\sum (z_e : e \in P) & \geq 1 \quad \text{para $P \in \Pcal$}\\ z_e & \geq 0 \quad \text{para $e \in E$.} \end{split} \end{equation}
(Em outras palavras, trata-se de atribuir pesos não-negativos $z$ aos arcos de modo que a soma dos pesos em cada caminho de $\Pcal$ seja pelo menos $1$.) Para qualquer corte que separa $r$ de $s$, o vetor característico $z$ do corte é solução viável de \eqref{lp:cut-all-paths}.
Para entender a relação entre os pl's \eqref{lp:max-flow-1} e \eqref{lp:min-cut-2} e o problema 2.A, é preciso estudar os poliedros dos pl's. Quais são as propriedades geométricas desses poliedros? Como são os vértices desses poliedros?
Seja $X(D,u,r,s)$ o poliedro do pl \eqref{lp:max-flow-1}, isto é, o conjunto de todos os vetores $x$ que satisfazem as restrições do pl. É claro que todo vetor de $X(D,u,r,s)$ é um fluxo de $r$ a $s$ e vice-versa. O poliedro não é vazio e é limitado. Portanto, tem vértices.
Se $x$ é um vértice de $X(D,u,r,s)$ então (i) não existe ciclo (dirigido ou não) em $D$ cujos arcos não estão vazios nem cheios de fluxo e (ii) não existe caminho (dirigido ou não) de $r$ a $s$ em $D$ cujo arcos não estão vazios nem cheios de fluxo. (Veja o exercício abaixo.) Em outras palavras, se $x$ é um vértice do poliedro então (i) todo ciclo no suporte de $x$ tem algum arco cheio de fluxo e (ii) todo caminho de $r$ a $s$ no suporte que $x$ tem algum arco cheio de fluxo. Reciprocamente, se $x$ é um vetor do poliedro $X(D,u,r,s)$ para o qual valem (i) e (ii) então $x$ é vértice do poliedro.
Exemplo 2.6: Considere a rede descrita abaixo por sua matriz de adjacências e sua função-capacidade.
O poliedro $X(D,u,r,s)$ é limitado pois $0 \leq x\leq u$ para todo $x$ no conjunto. O poliedro não é vazio pois contém o vetor $0$. Os vetores $x'$ e $x''$ descritos a seguir também estão no poliedro.
O vetor $x'''$ abaixo está em $X(D,u,r,s)$ mas não é vértice pois tanto $x'''+\d'''$ quanto $x'''-\d'''$ também estão no poliedro. Observe que o suporte de $\d'''$ é o ciclo $(v,w,s,v)$. Observe também que o conjunto de colunas da matriz de incidências que correspondem ao ciclo é l.d. (veja o lema F.4).
O vetor $x''''$ está em $X(D,u,r,s)$ mas não é vértice porque $x''''+\d''''$ e $x''''-\d''''$ estão no poliedro. Observe que o suporte de $\d''''$ é o caminho $(r,w,v,s)$.
Já os vetores $x'$ e $x''$ descritos acima são vértices do poliedro.
De acordo com o corolário C.3 no apêndice C, para qualquer vetor de custos $c$, alguma solução ótima do pl \eqref{lp:max-flow-1} é um vértice do poliedro $X(D,u,r,s)$.
Qualquer solução ótima do pl \eqref{lp:max-flow-1} é um fluxo máximo de $r$ a $s$. Portanto, qualquer algoritmo de programação linear — como o Simplex, por exemplo — resolve o problema 2.A. Mas é claro que um algoritmo especializado, como o de Edmonds–Karp, é mais eficiente.
Seja $Y(D,r,s)$ o poliedro do pl \eqref{lp:min-cut-2}, isto é, o conjunto de todos os pares $(y,z)$ que satisfazem as restrições do pl. O poliedro não é vazio e não é limitado, como passamos a mostrar. Seja $y$ qualquer vetor indexado por $V$ tal que $y_r=1$ e $y_s=0$. Faça $z_{pq} := \max\,(0,y_p-y_q)$ para todo arco $pq$. (Em outras palavras, se $y_q \geq y_p$ então $z_{pq}:=0$ e se $y_q \lt y_p$ então $z_{pq}:=y_p-y_q$.) Com $z$ assim definido, o par $(y,z)$ pertence ao poliedro.
Exemplo 2.7: Considere novamente a rede do exemplo 2.6. Veja as restrições do pl \eqref{lp:min-cut-2} escritas por extenso: \[ \begin{array}{ll*{5}{l}@{\enspace}c@{\enspace}l} y_r& & & & & & & = & 1\\ y_s& & & & & & & = & 0\\ y_v&\ha {}-y_r&\hb {}+z_{rv}& & & & & \geq & 0\\ y_w&\ha {}-y_r& &\hb {}+z_{rw}& & & & \geq & 0\\ y_w&\ha {}-y_v& & &\hb {}+z_{vw}& & & \geq & 0\\ y_s&\ha {}-y_v& & & &\hb {}+z_{vs}& & \geq & 0\\ y_s&\ha {}-y_w& & & & &\hb {}+z_{ws}& \geq & 0\\ & &\hd z_{rv} & & & & & \geq & 0\\ & & &\hd z_{rw} & & & & \geq & 0\\ & & & &\hd z_{vw} & & & \geq & 0\\ & & & & &\hd z_{vs} & & \geq & 0\\ & & & & & &\hd z_{ws}& \geq & 0 \end{array} \] Veja a seguir uma amostra de elementos do poliedro $Y(D,r,s)$.
Muitos outros vetores de $Y(D,r,s)$ podem ser obtidos a partir desses se observarmos que, para todo $(y,z)$ em $Y(D,r,s)$ e qualquer $z'\geq z$, o vetor $(y,z')$ também está em $Y(D,r,s)$. Com isso, fica claro que $Y(D,r,s)$ não é limitado.
O poliedro não tem vértices, como passamos a mostrar. Seja $(y,z)$ um elemento de $Y(D,r,s)$ e tome qualquer nó $p$ diferente de $r$ e de $s$. Se trocarmos $y_p$ por $y_p+1$ e trocarmos $z_{pq}$ por $z_{pq}+1$ para cada arco $pq$ que sai de $p$, o vetor modificado estará em $Y(D,r,s)$. Analogamente, se trocarmos $y_p$ por $y_p-1$ e $z_{qp}$ por $z_{qp}+1$ para cada arco $qp$ que entra em $p$, o vetor resultante estará em $Y(D,r,s)$.
Agora considere um vetor binário $(y,z)$ em $Y(D,r,s)$. Seja $R$ o conjunto de nós cujo vetor característico é $y$. Então $r\in R$, $s\notin R$, $z_{pq}\geq 1$ para todo arco em $\cutout(R)$, e $z_{pq}\geq 0$ para os demais arcos. Se $(y,z)$ minimiza $zu$ e $u$ não tem componentes nulas, temos $z_{pq}=1$ para todo $pq$ em $\cutout(R)$ e $z_{pq}=0$ para todos os demais arcos. Assim, $z$ é o vetor característico de $\cutout(R)$.
Ocasionalmente, somos levados a considerar redes de fluxo em que alguns arcos têm capacidade infinita, contrariando a definição de capacidade no início da seção 2.2. Atribuir capacidade $\infty$ a um arco $e$ da rede equivale a eliminar a restrição $x_e \leq u_e$. Mostraremos a seguir como é possível tratar dessa extensão do problema 2.A.
Se alguns arcos de uma rede de fluxo $(D,u,r,s)$ têm capacidade infinita, a correspondente instância do problema 2.A pode ser ilimitada (ou seja, a intensidade do fluxo pode ser arbitrariamente grande). Isso acontece se e somente se a rede tem um caminho dirigido de $r$ a $s$ cada um de cujos arcos tem capacidade infinita.
Entretanto, se cada caminho dirigido de $r$ a $s$ tem algum arco de capacidade finita, podemos substituir as ocorrências de $\infty$ por um número suficientemente grande e assim voltar ao problema 2.A. Por exemplo, podemos substituir $\infty$ por um número maior que $\sum (u_e : e \in E')$, onde $E'$ o conjunto de arcos da rede que têm capacidade finita.
see a parte
somente se.) [CCPS 3.3]