Aplicações de fluxo máximo em grafos

O teorema MFMC (teoremas 2.9) e sua versão inteira (teorema 2.10), ambos no capítulo 2, são ferramentas poderosas e versáteis. Este capítulo usa essas ferramentas para resolver alguns problemas combinatórios. Vários desses problemas são de viabilidade pois procuram um objeto de um certo tipo num grafo e não envolvem maximização nem minimização. Para esses problemas, os teoremas MFMC fornecem certificados de inviabilidade: explicações elementares de por quê uma dada instância não tem solução.

Eis um exemplo simples de problema de viabilidade: dada uma rede de fluxo $(D,u,r,s)$ e um número $k$, encontrar um fluxo viável de $r$ a $s$ que tenha intensidade pelo menos $k$. O teorema MFMC mostra que uma instância desse problema não tem solução somente se houver um impedimento óbvio na forma de um corte que separa $r$ de $s$ e tem capacidade menor que $k$.

3.1 O problema de Gale

Uma função-demanda em um grafo dirigido $D$ é qualquer função que associa um número real $b_v$ a cada nó $v$. Um fluxo $x$ em $D$ satisfaz uma função-demanda $b$ se tem excesso $b_v$ em cada nó $v$, ou seja, se \[ \xinout(v) = b_v \] para cada nó $v$. Assim, se $b_v \lt 0$ então $v$ é produtor de fluxo e se $b_v > 0$ então $v$ é consumidor de fluxo. [Essa interpretação pode desagradar alguns leitores, mas ela é inevitável em face de nossa convenção sobre qual das pontas de um arco é positiva e qual é negativa.]

Uma rede $(D,u)$ com função-demanda $b$ pode ser denotada por $(D,b,u)$. Ademais, denotaremos por $V$ o conjunto de nós de $D$. Para simplificar o palavreado, diremos que um fluxo é viável se satisfaz $b$ e respeita $u$.

O seguinte lema dá uma condição necessária óbvia para a existência de um fluxo viável:

(Como de hábito, $b(X)$ denota a soma $\sum (b_v : v \in X)$.) Assim, para tornar evidente que não existe fluxo viável basta mostrar que $b(V)\neq 0$ ou exibir um conjunto $X$ tal que $b(X) > \uin(X)$. A condição necessária descrita no lema é conhecida como condição de Gale em referência a D. Gale, que mostrou (1957) que a condição é também suficiente:

Prova: A prova é uma redução ao teorema MFMC inteiro (teorema 2.10). [Essa redução é a principal lição desta seção 3.1.] Suponha que a rede $(D,b,u)$ satisfaz as condições do enunciado; vamos mostrar que existe um fluxo viável. Seja $P$ o conjunto dos nós para os quais $b$ é negativo e $Q$ o conjunto dos nós para os quais $b$ é positivo ou nulo. Seja $(\Dcheck,\ucheck)$ a rede capacitada definida da seguinte maneira. O conjunto de nós de $\Dcheck$ é $V\cup\conj{r,s}$, sendo $r$ e $s$ dois novos nós, e o conjunto de arcos de $\Dcheck$ é definido assim:

para cada $p$ em $P$, há um arco $rp$ em $\Dcheck$ com $\ucheck_{rp}:=-b_p$;
para cada $q$ em $Q$, há um arco $qs$ em $\Dcheck$ com $\ucheck_{qs}:=b_q$;
para cada arco $vw$ de $D$, há um arco $vw$ em $\Dcheck$ com $\ucheck_{vw}:=u_{vw}$.

Seja $R$ um conjunto que separa $r$ de $s$ em $\Dcheck$. A capacidade do corte $\cutcheckout(R)$ na rede $(\Dcheck,\ucheck)$ é a soma de três parcelas: as capacidades dos arcos que vão de $r$ a $P\setm R$, as capacidades dos arcos que vão de $Q\cap R$ a $s$, e as capacidades dos arcos que vão de $V\cap R$ a $V\setm R$. Adote a notação $R' := V\setm R$ e observe que \[ \begin{split} \ucheckout(R) & \ = \ -b(P \setm R) + b(Q \cap R) + \uin(R')\\ & \ \geq \ -b(P \setm R) + b(Q \cap R) + b(R')\\ & \ = \ -b(P \setm R) + b(Q \cap R) + b(P\setm R) + b(Q\setm R)\\ & \ = \ b(Q \cap R) + b(Q\setm R)\\ & \ = \ b(Q)\,\text{.} \end{split} \] Concluímos assim que todo corte que separa $r$ de $s$ na rede $(\Dcheck,\ucheck)$ tem capacidade pelo menos $b(Q)$. Segue daí, pelo teorema MFMC (teorema 2.9), que existe um fluxo viável $\xcheck$ na rede $(\Dcheck,\ucheck, r, s)$ tal que $\intens(\xcheck) = b(Q)$. Como $\intens(\xcheck) = \text{}$ $\xcheckin(s) \leq \text{}$ $\ucheckin(s) = b(Q)$, todos os arcos que entram em $s$ estão cheios de fluxo e portanto $\xcheck_{qs}=b_q$ para todo $q$ em $Q$. Como $b(V)=0$ e portanto $b(P) = -b(Q)$, temos também $\xcheck_{rp}=-b_p$ para todo $p$ em $P$.

Seja $x$ a restrição de $\xcheck$ aos arcos da rede original $(D,u)$. É claro que $x$ respeita $u$. Resta mostrar que $x$ satisfaz $b$. Para cada $q$ em $Q$ temos $\xinout(q) = \text{}$ $\xcheckinout(q) + \xcheck_{qs} = \text{}$ $\xcheck_{qs} = b_q$. Analogamente, $\xinout(p) = -b_p$ para cada $p$ em $P$. Portanto, $x$ respeita $b$.

A segunda parte da prova, que trata de fluxo inteiro, é uma mera aplicação do teorema MFMC inteiro (teorema 2.10). ■

Exemplo 3.2: Para a rede $(D,b,u)$ do exemplo 3.1, veja a rede auxiliar $(\Dcheck,\ucheck, r, s)$ construída na prova do teorema 3.2 (complete a figura). A segunda tabela mostra um fluxo viável $\xcheck$ de $r$ a $s$ na rede $(\Dcheck,\ucheck, r, s)$.

\[ \begin{array}[t]{l@{\quad}rrrrrr} & r & p & i & j & q & s \\[0.5ex] r & - & - & 1 & - & 1 & - \\ p & - & - & 1 & 1 & - & 1 \\ i & - & - & - & - & 1 & - \\ j & - & - & 1 & - & 1 & 1 \\ q & - & 1 & - & - & - & - \\ s & - & - & - & - & - & - \end{array} \] \[ \begin{array}[t]{l@{\quad}rrrrrrrrrr} & ri & rq & pi & pj & iq & ji & jq & qp & ps & js \\[0.5ex] \ucheck & 2 & 1 & 6 & 4 & 3 & 1 & 2 & 3 & 2 & 1 \\ \xcheck & 2 & 1 & 0 & 1 & 2 & 0 & 0 & 3 & 2 & 1 \end{array} \] \[ \hspace{1ex} \begin{array}[t]{c@{\hspace{4ex}}c@{\hspace{4ex}}c} & \quad r & \\[1ex] & i & \\[0.9ex] p \hg & & \hg q \\[0.9ex] & j & \\[1ex] & s \quad & \end{array} \]

Exemplo 3.3: Seja $(D,b,u)$ a rede definida a seguir. (Ela é igual à rede do exemplo 3.1 exceto pelo valor de $u_{qp}\,$.)

\[ \begin{array}[t]{l@{\quad}cccc@{\qquad}r} & p & i & j & q & b \\[0.5ex] p & - & 1 & 1 & - & +2 \\ i & - & - & - & 1 & -2 \\ j & - & 1 & - & 1 & +1 \\ q & 1 & - & - & - & -1 \end{array} \hspace{4ex} \begin{array}[t]{l@{\quad}cccccc} & pi & pj & iq & ji & jq & qp\\[0.5ex] u & 6 & 4 & 3 & 1 & 2 & 2 \end{array} \]

Essa rede não tem fluxo viável porque o conjunto $X:=\conj{p,j}$ não satisfaz a condição $b(X) \leq \uin(X)$.

Tal como apresentada acima, a condição de Gale é assimétrica. Mas ela equivale à seguinte condição simétrica: $-\uout(X) \leq \text{}$ $b(X) \leq \text{}$ $\uin(X)$ para todo conjunto $X$ de nós.

Problemas de transporte

As instâncias do problema 3.A em que o grafo $D$ é bipartido e $u_e = \infty$ para todo arco $e$ (ou seja, não há restrições de capacidade) aparecem em muitas aplicações. Essas instâncias podem ser apresentadas em termos de redes de transporte. Uma rede de transporte é um objeto $(D,P,Q,a)$ em que $D$ é um grafo dirigido bipartido, $(P,Q)$ é uma bipartição de $D$, e $a$ é um vetor não-negativo indexado por $P\cup Q$.

O problema 3.A₀ é um caso especial do problema 3.A, como mostraremos a seguir. Dada uma rede de transporte $(D,P,Q,a)$, considere a rede $(D,b,u)$ em que $b$ e $u$ são definidas assim: $b_p = -a_p$ para cada $p$ em $P$, $b_q = a_q$ para cada $q$ em $Q$, e $u_{pq} = \infty$ para cada arco $pq$ de $D$. Como $D$ é bipartido, temos $\xinout(p) = \xout(p)$ para todo $p$ em $P$ e $\xinout(q) = \xin(q)$ para todo $q$ em $Q$. Assim, toda solução da instância $(D,b,u)$ do problema 3.A é solução da instância $(D,P,Q,a)$ do problema 3.A₀ e vice-versa.

Para formular o lema 3.1 e o teorema 3.2 na linguagem do problema 3.A₀, usamos a seguinte notação. Para qualquer subconjunto $Y$ de $Q$, denotamos por $N(Y)$ o conjunto de todos os nós $p$ de $P$ para os quais existe um arco $pq$ com $q$ em $Y$. Podemos dizer que $N(Y)$ é a vizinhança de $Y$. [A letra $N$ é a inicial da palavra neighborhood.]

Esboço da prova: A parte somente se é óbvia. Agora considere a parte se. Suponha que a rede $(D,P,Q,a)$ satisfaz as condições e seja $(D,b,u)$ a correspondente instância do problema 3.A, conforme definição acima. É claro que $b(V) = b(P) + b(Q) = -a(P) + a(Q) = 0$. Mostraremos a seguir que \[ b(X) \leq \uin(X) \] para todo subconjunto $X$ de $V(D)$. Há dois casos a considerar. Se $\cutin(X) \neq \emptyset$ então $\uin(X) = \infty$ e portanto $b(X) \leq \uin(X)$. Por outro lado, se $\cutin(X) = \emptyset$ então $\uin(X) = 0$ e $N(Q \cap X) \subseteq P \cap X$. Segue daí que $a(P \cap X) \geq \text{}$ $a(N(Q\cap X) \geq \text{}$ $a(Q \cap X)$, donde $b(X) = \text{}$ $b(P \cap X) + b(Q \cap X) = \text{}$ $-a(P \cap X) + a(Q \cap X) \leq \text{}$ $-a(Q \cap X) + a(Q \cap X) = 0$, e assim $b(X) \leq \uin(X)$. Concluímos que em ambos os casos temos $b(X) \leq \uin(X)$. Segue do teorema de Gale (teorema 3.2) que existe um fluxo $x$ que satisfaz $b$. Um tal $x$ é solução do problema 3.A₀. ■

A seguinte generalização do problema 3.A₀ é conhecida como problema do transporte e serve de modelo para vários problemas práticos:

Para obter a generalização apropriada do corolário 3.3 basta eliminar a condição $a(P) = a(Q)$:

Exercícios 3.1

★ Prove o lema 3.1. (Dica: Veja o lema 2.1.)
★ Versão simétrica da condição de Gale. Mostre que a condição de Gale é equivalente à seguinte: $-\uout(X) \leq b(X) \leq \uin(X)$ para todo $X \subseteq V$.
Deduza o teorema MFMC (teorema 2.9) do teorema de Gale (teorema 3.2) e do lema 3.1.
Preencha os detalhes da prova do teorema 3.2. Em particular, prove que a condição $b(V)$ é independente da condição $b(X) \leq \uin(X)$ para todo $X$.
★ Prova direta do teorema de Gale. Prove o teorema de Gale sem usar o teorema MFMC (teoremas 2.9). (Dica: A discrepância de um fluxo $x$ é o número $\sum_{i\in V} |b_i - \xinout(i)|$. Use caminhos de aumento, como os da seção 2.4, para diminuir a discrepância de $x$.)
Algoritmo. Escreva um algoritmo que receba uma rede $(D,b,u)$ com função-capacidade $u$ e função-demanda $b$ e devolva (i) um fluxo viável $x$ ou (ii) um subconjunto $X$ de $V$ que viola a condição de Gale. Seu algoritmo deve invocar a versão Edmonds–Karp do algoritmo de Ford–Fulkerson.
Encontre um fluxo viável na rede $(D,b,u)$ descrita a seguir. Os nós são $r \ a \ b \ c \ d \ s$ (não confunda o nó $b$ com a função-demanda $b$) e as tabelas definem as funções $b$ e $u$:
\[ \begin{array}[t]{l@{\quad}rrrrrr} & r & a & b & c & d & s\\[0.1ex] b & +3 & +2 & +2 & -1 & -3 & -3 \end{array} \] \[ \begin{array}[t]{l@{\quad}ccccccc} & ra & rb & ac & bd & cs & ds & sr\\[0.1ex] u & 8 & 7 & 6 & 5 & 7 & 8 & 6 \end{array} \]
★ Algoritmo para árvore orientada sem capacidades. Seja $(T,b)$ uma rede em que $T$ é uma árvore orientada e $b$ uma função-demanda. Escreva um algoritmo que receba $T$ e $b$ e calcule um fluxo em $T$ que satisfaça $b$ ou decida que um tal fluxo não existe. (Sugestão: faça um algoritmo recursivo que começa pelas folhas da árvore.)
Condições para árvore orientada sem capacidades. Seja $(T,b)$ uma rede em que $T$ é uma árvore orientada e $b$ uma função-demanda. Dê uma condição necessária e suficiente para que $(T,b)$ tenha um fluxo que satisfaz $b$. Estabeleça a relação entre essa condição e a condição de Gale.
Problema de Gale em árvore orientada. Seja $(T,b,u)$ uma rede capacitada com demandas em que $T$ é uma árvore orientada. Escreva um algoritmo que encontre um fluxo viável em $(T,b,u)$. Dê uma condição necessária e suficiente para que $(T,b,u)$ tenha um fluxo viável. Estabeleça a relação entre essa condição e a condição geral de Gale.
Seja $r$ um nó de um grafo dirigido $D$ com $n$ nós. Seja $b$ a função-demanda definida por $b_r=-n+1$ e $b_v=+1$ para cada $v\neq r$. Dê uma condição necessária e suficiente para que a rede $(D,b)$ tenha um fluxo que satisfaz $b$.
★ Rede sem capacidades. Seja $b$ uma função-demanda em um grafo dirigido $D$. Mostre que a rede $(D,b)$ tem um fluxo que satisfaz $b$ se e somente se $b(V) = 0$ e $b(X)\leq 0$ para todo $X\subseteq V$ tal que $\cutin(X)=\emptyset$. (Dica: Enuncie e prove em separado a parte se e a parte somente se.)
Prove o teorema 3.4.
Subgrafo bipartido com prescrição de graus. Seja $G$ um grafo não-dirigido bipartido. Suponha dado um inteiro não-negativo $a_v$ para cada nó $v$ de $G$. Queremos encontrar $E' \subseteq E(G)$ tal que o grau de cada nó $v$ no grafo $(V(G),E')$ seja $a_v$. Descreva um algoritmo para o problema. Dê uma condição necessária e suficiente para que o problema tenha solução. Discuta o caso particular do problema em que $a$ é constante. [CCPS 3.18]
Grafo dirigido euleriano. (O adjetivo euleriano é uma referência a Leonhard Euler.) Dado um grafo dirigido $D$, encontrar um conjunto de arcos cuja inversão (isto é, troca de $vw$ por $wv$) resulte em um grafo dirigido $\Dcheck$ tal que $|\cutcheckin(v)| = |\cutcheckout(v)|$ para cada nó $v$. Dê uma condição necessária e suficiente para que o problema tenha solução. [CCPS 4.5]
Orientação de grafo não-dirigido. Dado um grafo não-dirigido $G$ e um inteiro não-negativo $k$, queremos transformar cada aresta de $G$ em um arco de tal forma que no grafo dirigido resultante o grau de saída de cada nó seja no máximo $k$ (isto é, $|\cutout(v)| \leq k$ para todo nó $v$). Dê uma condição necessária e suficiente para que uma instância desse problema tenha solução. Dê um algoritmo para o problema. [CCPS 3.34]
Síntese de grafo dirigido. Sejam $\alpha_1,\ldots, \alpha_n$ e $\beta_1,\ldots, \beta_n$ números inteiros não-negativos. Queremos construir um grafo dirigido com conjunto de nós $\conj{v_1,\ldots,v_n}$ tal que cada nó $v_i$ tem grau de saída $\alpha_i$ e grau de entrada $\beta_i$. Mostre como resolver o problema. [AMO 8.13]
Torneio viável. Imagine um torneio de tênis com $n$ participantes. Suponha que cada participante joga exatamente uma partida com cada um dos outros e suponha que não há empates. Seja $d_i$ o número de derrotas do tenista $i$. Dê uma condição necessária e suficiente para que um dado vetor $(d_1,\ldots,d_n)$ represente um torneio. Dê um algoritmo que decida se $(d_1,\ldots,d_n)$ representa um torneio. [CCPS 3.35]

3.2 O problema de Hoffman

Algumas aplicações exigem que o fluxo em cada arco do grafo tenha um certo valor mínimo. Essas restrições por baixo nos arcos podem ser convertidas em demandas nos nós, tranformando assim a aplicação em uma instância do problema de Gale da seção anterior.

Uma demanda nos arcos de um grafo dirigido é uma função $l$ que associa um número real não-negativo a cada arco do grafo; portanto, $l \in \Rplus^{E}$. [A letra $l$ é a inicial de lower bound.] Dizemos que um fluxo $x$ no grafo satisfaz a demanda $l$ se $x_e \geq l_e$ para cada arco $e$.

Para simplificar a conversa, diremos que uma circulação $x$ é viável se $l \leq x \leq u$.

Uma condição necessária para a existência de uma circulação viável é intuitiva:

(O significado das expressões $\lout(X)$ e $\uin(X)$ foi definido na seção 2.1.) Assim, para tornar evidente que não existe circulação viável basta exibir um arco $e$ tal que $l_e > u_e$ ou exibir um conjunto $X$ de nós tal que $\lout(X) > \uin(X)$. A condição necessária dada no lema 3.5 é conhecida como condição de Hoffman em referência a A. J. Hoffman (não confunda com D.A. Huffman, inventor do código de Huffman), que mostrou (1960) que essa condição é suficiente:

Prova: A prova é uma redução do teorema de Gale (teorema 3.2). Suponha que a rede $(D,l,u)$ satisfaz a condição do teorema. Para mostrar que existe uma circulação viável $x$, usaremos o teorema de Gale com $-\linout$ no papel da função-demanda e a diferença $u-l$ no papel da função-capacidade.

Comece por observar que $l$ é um fluxo em $D$ e considere o excesso $\linout(v)$ de fluxo em cada nó $v$. Em virtude do lema 2.1 do capítulo 2, \begin{equation}\label{eq1:proof:teo:hoffman} -\linout(V) = 0\,\text{.} \end{equation}

Agora considere a hipótese $\lout(X) \leq \uin(X)$. Se subtrairmos $\lin(X)$ dos dois lados da desigualdade teremos \begin{equation}\label{eq2:proof:teo:hoffman} -\linout(X) \leq \inn{(u-l)}(X)\,\text{.} \end{equation}

Nossa rede $(D,l,u)$ pode ser vista como uma instância $(D,b,\ucheck)$ do problema de Gale com $b$ e $\ucheck$ definidos assim: \[ b := -\linout \hspace{3ex} \text{e} \hspace{3ex} \ucheck := u - l\,\text{.} \]

O parâmetro $b$ é uma função-demanda. Como $l\leq u$, o parâmetro $\ucheck$ é uma função-capacidade. Graças a \eqref{eq1:proof:teo:hoffman} e \eqref{eq2:proof:teo:hoffman}, a rede $(D,b,\ucheck)$ satisfaz a condição de Gale: \[ b(V) = 0 \hspace{3ex} \text{e} \hspace{3ex} b(X) \leq \inout{\ucheck}(X) \] para cada $X\subseteq V$. O teorema 3.2 garante então que a rede $(D,b,\ucheck)$ tem um fluxo $\xcheck$ tal que $\xcheckinout = b$ e $\xcheck \leq \ucheck$. Para retornar à rede original $(D,l,u)$, considere o fluxo $x := \xcheck+l$ (trata-se de um fluxo pois $\xcheck\geq 0$ e $l\geq 0$). É claro que $l \leq \text{}$ $x \leq \text{}$ $\ucheck + l = u$. Ademais, $x$ é uma circulação pois \begin{split} \xinout(v) & \ = \ \xcheckinout(v) + \linout(v) \\ & \ = \ b_v + \linout(v) \\ & \ = \ -\linout(v) + \linout(v) \\ & \ = \ 0 \end{split}

para cada nó $v$. Em suma, $x$ é uma circulação viável, como queríamos provar. ■

Exemplo 3.7: Veja a rede $(D,b,\ucheck)$ construída na prova do teorema 3.6 a partir da rede $(D,l,u)$ do exemplo 3.6:

\[ \begin{array}[t]{l@{\quad}c} & b \\[0.5ex] p & +2 \\ i & -2 \\ j & +1 \\ q & -1 \end{array} \hspace{6ex} \begin{array}[t]{l@{\quad}cccccc} & pi & pj & iq & ji & jq & qp\\[0.5ex] \ucheck & 6 & 4 & 3 & 1 & 2 & 3\\ \xcheck & 0 & 1 & 2 & 0 & 0 & 3 \end{array} \]

A tabela acima mostra um fluxo $\xcheck$ que satisfaz $b$ e respeita $\ucheck$. Essa rede $(D,b,\ucheck)$ é igual à rede $(D,b,u)$ do exemplo 3.3.

Exemplo 3.8: A rede $(D,l,u)$ descrita abaixo é igual à rede do exemplo 3.6 exceto por $u_{qp}$. A rede não tem circulação viável pois o conjunto $X:=\conj{p,j}$ não satisfaz a condição $\lout(X) \leq \uin(X)$.

\[ \begin{array}[t]{l@{\quad}cccc} & p & i & j & q \\[0.5ex] p & - & 1 & 1 & - \\ i & - & - & - & 1 \\ j & - & 1 & - & 1 \\ q & 1 & - & - & - \end{array} \hspace{6ex} \begin{array}[t]{l@{\quad\enspace}cccccc} & pi & pj & iq & ji & jq & qp\\[0.5ex] l & 1 & 1 & 0 & 1 & 1 & 0\\ u & 7 & 5 & 3 & 2 & 3 & 2 \end{array} \]

Vale a seguinte generalização comum dos teoremas de Gale (teorema 3.2) e de Hoffman (teorema 3.6):

Exercícios 3.2

Mostre que as partes $l\leq u$ e $\lout(X) \leq \uin(X)$ da condição de Hoffman são independentes.
Seja $D:=(V,E)$ um grafo dirigido que consiste em um ciclo dirigido simples e nada mais. Sejam $l$ e $u$ duas funções de $E$ em $\Rplus$. Parte 1: Supondo que existe uma circulação $x$ tal que $l\leq x\leq u$, mostre que $\max\,(l_e : e \in E) \leq \text{}$ $\min\left(u_e : e \in E\right)$. Parte 2: Supondo que $\max\,(l_e : e \in E) > \text{}$ $\min\left(u_e : e \in E\right)$, mostre que a rede $(D,l,u)$ viola a condição de Hoffman.
★ Prove o lema 3.5.
Encontre uma circulação viável na rede $(D,l,u)$ descrita a seguir. Os nós são $r \ a \ b \ c \ d \ s$ e a tabela dá os arcos e as funções $l$ e $u$:
\[ \begin{array}[t]{c@{\quad}ccccccc} & ra & rb & ac & bd & cs & ds & sr\\[0.5ex] l & 1 & 2 & 3 & 4 & 2 & 1 & 0\\ u &\infty&\infty&\infty&\infty&\infty&\infty& 6 \end{array} \]
Encontre uma circulação viável na rede $(D,l,u)$ descrita a seguir. Os nós são $r \ a \ b \ c \ d \ s$ e a tabela dá os arcos e as funções $l$ e $u$:
\[ \begin{array}[t]{c@{\quad}ccccccc} & ra & rc & ab & dc & bs & ds & sr\\[0.5ex] l & 1 & 1 & 1 & 1 & 1 & 1 & 0\\ u & 9 & 9 & 9 & 9 & 9 & 9 & 8 \end{array} \]
Seja $(D,l,u)$ uma rede acíclica em que $l \neq 0$ e $l\leq u$. Deduza da condição de Hoffman que não existe circulação viável em $(D,l,u)$.
Seja $(D,l,u)$ uma rede em que $l\leq u$. Use a condição de Hoffman para provar a seguinte proposição: se $\lin(X) \leq \uout(X)$ para todo conjunto $X$ de nós então a rede tem uma circulação viável.
Trajeto de caminhão de coleta de lixo. Um ciclo dirigido num grafo dirigido é euleriano, se passa por cada arco e cada nó do grafo. (É claro que um ciclo euleriano passa apenas uma vez por cada arco; mas pode passar mais de uma vez por cada nó.) [O adjetivo euleriano é uma referência a Leonhard Euler.] Mostre que um grafo dirigido $D$ tem um ciclo dirigido euleriano se e somente se $D$ é conexo e $|\cutin(v)| = |\cutout(v)|$ para cada nó $v$. [CCPS 4.4]
Seja $(D,l,u)$ uma rede em que $l_e > 0$ e $u_e=\infty$ para cada arco $e$. Mostre que a rede tem uma circulação viável se e somente se $D$ é fortemente conexo. (Dica: Enuncie e prove em separado a parte se e a parte somente se.) [AMO 3.53]
Prove o teorema 3.7, que generaliza os teoremas de Gale e Hoffman.

3.3 Fluxo mínimo

O problema do fluxo máximo (problema 2.A, capítulo 2) procura um fluxo de intensidade máxima que respeite as capacidades dos arcos. Se tocarmos capacidades dos arcos por demandas nos arcos e intensidade máxima por intensidade mínima seremos levados a considerar o seguinte problema:

(Como de hábito, a expressão fluxo $x$ de $r$ a $s$ significa que $\xinout(s) \geq 0$ e $\xinout(v)=0$ para cada $v$ diferente de $r$ e de $s$.) Para simplificar o palavreado, diremos que um fluxo $x$ numa rede $(D,l,r,s)$ é $k$-viável se vai de $r$ a $s$ e satisfaz as condições $x \geq l$ e $\intens(x) \leq k$. Nosso problema consiste então em encontrar um fluxo $k$-viável.

Para formular condições de existência de um fluxo $k$-viável, vamos recorrer aos cortes dirigidos que separam $r$ de $s$. (Como se sabe, um corte $\cutout(X)$ é dirigido se $\cutin(X)=\emptyset$.) É fácil verificar a seguinte condição necessária:

Essa condição necessária é também suficiente se restringirmos a atenção às redes fonte-sorvedouro. Uma rede $(D,l,r,s)$ é fonte-sorvedouro se

Todo arco de uma tal rede pertence a algum caminho dirigido de $r$ a $s$. Numa rede fonte-sorvedouro, algum fluxo $x$ de $r$ a $s$ é tal que $x\geq l$. Como não existe caminho dirigido de $s$ a $r$, um fluxo $x \geq l$ não pode ter intensidade arbitrariamente pequena.

Prova: A prova é uma redução ao teorema de Hoffman (teorema 3.6). Suponha que a condição enunciada está satisfeita. Seja $E$ o conjunto de arcos de $D$. Construa um grafo dirigido $\Dcheck$ acrescentando um novo arco $sr$ a $D$ e seja $\Echeck$ o conjunto de arcos de $\Dcheck$. Seja $\lcheck$ a função de $\Echeck$ em $\Rplus$ definida por $\lcheck_{sr}=0$ e $\lcheck_e=l_e$ para cada $e$ em $E$. Seja $\ucheck$ a função-capacidade definida em $\Echeck$ pelas seguintes propriedades: \[ \ucheck_{sr}=k \hspace{2ex} \text{e} \hspace{2ex} \ucheck_e=\infty \enspace \text{para cada $e$ em $E$} \] É claro que $l \leq u$. Para provar que rede $(\Dcheck,\lcheck,\ucheck)$ satisfaz a condição de Hoffman resta mostrar que $\lcheckout(X)\leq \ucheckin(X)$ para todo subconjunto $X$ de $V(\Dcheck)$. Há três casos a considerar, dependendo dos valores de $\cutout(X)$ e $\cutin(X)$ em $D$:

Se $\cutin(X) = \cutout(X) = \emptyset$ em $D$ então $\lcheckout(X) = 0 \leq \ucheckin(X)$ onde quer que o arco $sr$ esteja em relação a $X$.
Se $\cutin(X) \neq \emptyset$ então $\lcheckout(X) \leq \ucheckin(X)$ pois algum arco de $D$ entra em $X$ e portanto $\ucheckin(X) = \infty$.
Suponha agora que $\cutin(X) = \emptyset$ e $\cutout(X) \neq \emptyset$. Seja $e$ um arco de $D$ que sai de $X$. Como a rede é fonte-sorvedouro, $e$ pertence a algum caminho dirigido de $r$ a $s$. Como o corte $\cutout(X)$ é dirigido, temos $r\in X$ e $s\notin X$, ou seja, $X$ separa $r$ de $s$. Logo $\lout(X) \leq \uin(X)$, e portanto $\lcheckout(X) = \text{}$ $\lout(X) \leq \text{}$ $\uin(X) \leq \ucheckin(X)$.

Como $\lcheckout(X)\leq \ucheckin(X)$ para todo subconjunto $X$ de $V(\Dcheck)$, o teorema 3.6 garante que a rede $(\Dcheck,\lcheck,\ucheck)$ tem uma circulação viável, digamos $\xcheck$. A restrição de $\xcheck$ ao conjunto $E$ de arcos é um fluxo $x$ de $r$ a $s$ em $D$. Ademais, $x \geq l$ e $\intens(x) \leq \text{}$ $\ucheck_{sr} = k$. Em outras palavras, $x$ é um fluxo $k$-viável. ■

Exemplo 3.10: Para a rede $(D,l,r,s)$ do exemplo 3.9, eis a rede $(\Dcheck,\lcheck,\ucheck)$ construída na prova do teorema 3.9:

\[ \begin{array}[t]{r@{\quad}cccc} & p & i & j & q \\[0.5ex] r=p & - & 1 & 1 & - \\ i & - & - & - & 1 \\ j & - & 1 & - & 1 \\ s=q & 1 & - & - & - \end{array} \hspace{6ex} \begin{array}[t]{l@{\quad\enspace}cccccc} & pi & pj & iq & ji & jq & qp\\[0.5ex] \lcheck & 1 & 1 & 0 & 1 & 1 & 0 \\ \ucheck &\infty&\infty&\infty&\infty&\infty& 3 \\ \xcheck & 1 & 2 & 2 & 1 & 1 & 3 \end{array} \]

(A rede $(\Dcheck,\lcheck,\ucheck)$ só difere da rede do exemplo 3.6 porque $\ucheck$ é diferente.) A última linha da tabela dá uma circulação $\xcheck$ tal que $\lcheck \leq \text{}$ $\xcheck \leq \ucheck$.

Exemplo 3.11: Para verificar que não existe fluxo $2$-viável na rede do exemplo 3.9, tome o conjunto $X:=\conj{p,j}$ e observe que o corte dirigido $\cutout(X)$ separa $r$ de $s$ e que $\lout(X) > 2$.

Exercícios 3.3

Mostre que toda rede fonte-sorvedouro $(D,l,r,s)$ tem um fluxo $x$ de $r$ a $s$ (possivelmente de grande intensidade) tal que $x \geq l$.
É verdade que toda rede dotada de $k$-fluxo é fonte-sorvedouro?
Prove o lema 3.8.
Aponte os detalhes obscuros da prova do teorema 3.9 do fluxo mínimo. Clarifique esses detalhes.
Encontre um fluxo $9$-viável na rede $(D,l,r,s)$ que tem nós $r \ a \ b \ s$ e as demandas nos arcos dadas na tabela.
\[ \begin{array}[t]{c@{\quad}cccc} & ra & as & sb & br \\[0.5ex] l & 1 & 1 & 1 & 1 \end{array} \]
Considere a rede $(D,l,r,s)$ que tem nós $r \ a \ b \ c \ d \ s$ e os arcos dados abaixo. Encontre um fluxo $7$-viável. Encontre um fluxo $6$-viável.
\[ \begin{array}[t]{c@{\quad}cccccc} & ra & rb & ac & bd & cs & ds \\ l & 1 & 2 & 3 & 4 & 2 & 1 \end{array} \]
Considere a rede $(D,l,r,s)$ que tem nós $r \ a \ b \ c \ d \ s$ e os arcos dados abaixo. Encontre um fluxo viável de intensidade $\leq 9$.
\[ \begin{array}[t]{c@{\quad}cccccc} & ra & rc & ab & dc & bs & ds \\ l & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \]
Considere a rede $(D,l,r,s)$ com nós $r \ a \ b \ s$ e os arcos e demandas dados na tabela. Existe fluxo $2$-viável de $r$ a $s$? Existe fluxo $1$-viável de $r$ a $s$?
\[ \begin{array}[t]{c@{\quad}ccccc} & ra & ar & ab & bs & sb \\ l & 2 & 0 & 1 & 3 & 0 \end{array} \]
Fluxo mínimo versus corte máximo. Prove o teorema 3.10.
Programas lineares. Formule os programas lineares que representam o problema do fluxo mínimo e o do corte dirigido máximo. (Veja o exercício Fluxo mínimo versus corte máximo acima.)

3.4 Coberturas por caminhos

O teorema do fluxo mínimo (teorema 3.10) tem duas consequências interessantes que envolvem coberturas de grafos dirigidos por caminhos dirigidos.

Uma cobertura dos arcos (por caminhos dirigidos) de um grafo dirigido $D$ é um coleção de caminhos dirigidos tal que cada arco de $D$ pertence a pelo menos um dos caminhos da coleção. Uma cobertura dos arcos é mínima se nenhum outra tem menos caminhos.

O objeto dual de uma cobertura dos arcos é um corte dirigido. Um corte dirigido num grafo é máximo se nenhum outro tem mais arcos.

Em qualquer grafo dirigido, se $\Pcal$ é uma cobertura e $C$ é um corte dirigido então é evidente que $|\Pcal| \geq |C|$. Se vale a igualdade, a cobertura $\Pcal$ é mínima e o corte $C$ é máximo. O seguinte teorema mostra que a recíproca dessa afirmação é verdadeira em DAGs.

Prova: A prova é uma redução ao teorema do fluxo mínimo e corte máximo (teorema 3.10). Como já observamos, $|\Pcal| \geq |C|$ para qualquer cobertura $\Pcal$ e qualquer corte dirigido $C$. Resta mostrar que $|\Pcal| = |C|$ para alguma $\Pcal$ e algum $C$.

Seja $D$ o DAG em questão. Construa um grafo dirigido $\Dcheck$ da seguinte maneira. O conjunto de nós de $\Dcheck$ é $V(D)\cup \conj{r,s}$, sendo $r$ e $s$ dois novos nós. Todos os arcos de $D$ também são arcos de $\Dcheck$. Além disso, $\Dcheck$ tem um arco $rv$ para cada fonte $v$ de $D$ e um arco $ws$ para cada sorvedouro $w$ de $D$. É claro que $\Dcheck$ é um DAG, que $r$ é a única fonte de $\Dcheck$, e que $s$ é o único sorvedouro de $\Dcheck$. Portanto, a rede $(\Dcheck,r,s)$ é fonte-sorvedouro no sentido da seção 3.3.

Seja $l$ a função-demanda definida sobre os arcos de $\Dcheck$ pelas seguintes propriedades: $l_e=1$ para cada $e$ em $E(D)$ e $l_f=0$ para cada $f$ em $E(\Dcheck) \setm E(D)$. Na rede $(\Dcheck,l,r,s)$, seja $x$ um fluxo de intensidade mínima dentre aqueles que vão de $r$ a $s$ e satisfazem $x \geq l$. Seja $\cutout(X)$ um corte dirigido que maximiza $\lout(X)$ dentre os cortes dirigidos que separam $r$ de $s$. De acordo com o teorema 3.10, \[ \intens(x) = \lout(X)\,\text{.} \] Denote por $X{-}r$ o conjunto $X\setm \conj{r}$. No grafo $D$, temos $|\cutout(X{-}r)| = \lout(X)$, donde \[ \intens(x) = |\cutout(X{-}r)|\text{.} \] De acordo com o adendo do teorema 3.10, podemos supor que $x$ é inteiro. Mais que isso, podemos supor que $x$ é binário. Logo, o fluxo $x$ pode ser decomposto em $\intens(x)$ caminhos dirigidos simples em $\Dcheck$, todos de $r$ a $s$, conforme o lema 2.5 do capítulo 2. Digamos que $P_1,\ldots,P_k$ são os caminhos da decomposição, com $k = \intens(x)$. Como $x\geq l$, cada arco de $D$ pertence a algum dos caminhos. Cada $P_i$ induz um caminho dirigido $Q_i$ em $D$. O conjunto $\conj{Q_1,\ldots,Q_k}$ de caminhos é uma cobertura dos arcos de $D$. Ademais, o número de caminhos é $k = |\cutout(X{-}r)|$ e $\cutout(X{-}r)$ é um corte dirigido em $D$. ■

Teorema de Dilworth

Uma cobertura dos nós (= dipaths cover) de um grafo dirigido $D$ é uma coleção de caminhos dirigidos tal que cada nó de $D$ pertence a pelo menos um dos caminhos da coleção. (Não confunda esse conceito com a cobertura por nós da seção 6.4.) Uma cobertura dos nós é mínima se nenhuma outra tem menos caminhos.

O dual de uma cobertura dos nós é uma anticadeia. Uma anticadeia (= antichain) é qualquer conjunto $B$ de nós tal que não existe caminho dirigido com origem e término em nós distintos de $B$. Uma anticadeia é máxima se nenhuma outra tem mais nós.

Em qualquer grafo dirigido, para qualquer cobertura $\Pcal$ dos nós e qualquer anticadeia $B$, é claro que $|\Pcal| \geq |B|$. Se vale a igualdade, a cobertura é mínima e a anticadeia é máxima. R. P. Dilworth mostrou (1950) que a recíproca dessa afirmação é verdadeira quando o grafo é um DAG. [Dilworth provou o teorema no contexto de ordens parciais. Aqui, o teorema foi traduzido para DAGs.]

Prova: A prova é uma redução ao teorema do fluxo mínimo e corte máximo (teorema 3.10). Como já observamos, $|\Pcal| \geq |B|$ para qualquer cobertura $\Pcal$ e qualquer anticadeia $B$. Resta mostrar que $|\Pcal| = |B|$ para alguma $\Pcal$ e alguma $B$.

Seja $D$ o DAG em questão. Construa um grafo dirigido $\Dcheck$ da seguinte maneira. Para cada nó $v$ de $D$, o grafo $\Dcheck$ tem dois nós, $v_1$ e $v_2$, \[ \text{ligados por um arco $v_1v_2$.} \] Para cada arco $vw$ de $D$, o grafo $\Dcheck$ tem um arco $v_2w_1$. Além disso, $\Dcheck$ tem dois novos nós, $r$ e $s$, um arco $rv_1$ para cada fonte $v$ de $D$, e um arco $w_2s$ para cada sorvedouro $w$ de $D$. Os arcos da forma $v_1v_2$ serão chamados especiais; eles representam os nós de $D$. A rede $(\Dcheck,r,s)$ é fonte-sorvedouro no sentido da seção 3.3.

Defina uma função-demanda $l$ sobre os arcos de $\Dcheck$ da seguinte maneira: $l_e = 1$ se $e$ é um arco especial e $l_{e} = 0$ em caso contrário. O teorema 3.10 aplicado à rede $(\Dcheck,l,r,s)$ garante que existe um fluxo $x$ de $r$ a $s$ tal que $x \geq l$ e existe um corte dirigido $\cutout(X)$ que separa $r$ de $s$ tal que \[ \intens(x) = \lout(X)\,\text{.} \] Seja $B$ o conjunto dos nós de $D$ que $X$ quebra, isto é, o conjunto dos nós $v$ de $D$ tais que $X$ separa $v_1$ de $v_2$ em $\Dcheck$. Observe que $|B| = \lout(X)$ e portanto \[ \intens(x) = |B|\,\text{.} \] Imagine agora, por um momento, que $B$ não é uma anticadeia. Então existe um caminho dirigido em $D$ que vai de um nó $v$ de $B$ a outro nó $w$ de $B$. Em $\Dcheck$, esse caminho corresponde a um caminho dirigido que vai de $v_2$ a $w_1$. Portanto, o caminho começa em $V(\Dcheck)\setm X$ e termina em $X$, e assim tem um arco em $\cutin(X)$. Mas isso é impossível, pois o corte $\cutout(X)$ é dirigido. Essa contradição mostra que $B$ é uma anticadeia.

De acordo com o adendo do teorema 3.10, podemos supor que $x$ é inteiro. Mais que isso, podemos supor que $x$ é binário. Logo, de acordo com o lema 2.5, o fluxo $x$ pode ser decomposto em $\intens(x)$ caminhos dirigidos simples em $\Dcheck$, todos de $r$ a $s$. Sejam $P_1,\ldots,P_k$ esses caminhos, com $k = \intens(x)$. É claro que cada arco especial de $\Dcheck$ pertence a algum dos caminhos. Cada $P_i$ induz um caminho dirigido $Q_i$ em $D$. O conjunto $\conj{Q_1,\ldots,Q_k}$ de caminhos é uma cobertura dos nós de $D$. Ademais, o número de caminhos é $|B|$. ■

Exercícios 3.4

★ Seja $D$ um grafo dirigido e $\Pcal$ uma cobertura (por caminhos dirigidos) dos arcos de $D$. Seja $\cutout(X)$ um corte dirigido em $D$. Dê uma prova elementar da desigualdade $|\Pcal| \geq |\cutout(X)|$, ou seja, prove a desigualdade diretamente.
★ Seja $D$ um grafo dirigido e $\Pcal$ uma cobertura (por caminhos dirigidos) dos nós de $D$. Seja $B$ uma anticadeia em $D$. Dê uma prova elementar da desigualdade $|\Pcal| \geq |B|$, ou seja, prove a desigualdade diretamente.
Desenhe uma árvore radicada com $8$ ou mais nós. Encontre uma cobertura mínima dos arcos e um corte dirigido máximo na árvore. Encontre uma cobertura mínima dos nós e uma anticadeia máxima na árvore.
Mostre uma anticadeia máxima e um cobertura mínima dos nós por caminhos dirigidos no DAG da figura. [CCPS fig 2.5]
★ Complete os detalhes mais obscuros da prova do teorema de Dilworth (teorema 3.12).
Seja $\Pcal$ uma cobertura mínima dos nós de um grafo dirigido $D$ por caminhos dirigidos. Podemos supor que todos os caminhos são simples? Podemos supor que a coleção $\Pcal$ é disjunta, ou seja, que cada nó de $D$ pertence a apenas um dos caminhos de $\Pcal$?
Mostre que num grafo dirigido dotado de ciclos dirigidos uma anticadeia máxima pode ser menor que uma cobertura mínima dos nós por caminhos dirigidos.
★ Escalonamento de aviões. Uma companhia de aviação quer servir $p$ rotas (= flight legs) com o menor número possível de aviões. Para isso, ela precisa combinar essas rotas da maneira mais eficiente possível. O voo da rota $i$ deve começar no horário $a_i$ e terminar no horário $b_i$. Um avião precisa de $r_{ij}$ horas para retornar do destino da rota $i$ à origem da rota $j$. Sugira uma maneira de resolver o problema. [AMO 6.32, CCPS 3.39]
Seja $\Ccal$ a coleção de todos os caminhos dirigidos em um grafo dirigido $D$. Seja $A$ a matriz binária indexada por $V(D)\times \Ccal$ e definida pela seguinte propriedade: $A_{v, C}=1$ se e somente se $v$ está em $C$. Use $A$ para formular o programa linear que corresponde ao problema da cobertura mínima dos nós por caminhos dirigidos. Qual o dual desse programa linear? Qual a relação entre o dual e anticadeias máximas?
★ Seja $D$ um grafo dirigido bipartido com bipartição $(P,Q)$. Mostre que um subconjunto $B$ de $V(D)$ é uma anticadeia se e somente se $V(D)\setm B$ é uma cobertura por nós (no sentido da seção 6.4). Que aparência tem uma cobertura mínima dos nós de $D$ por caminhos dirigidos?
Prove o teorema de Kőnig (teorema 6.4) a partir do teorema de Dilworth (teorema 3.12).
Prove o teorema de Dilworth (teorema 3.12) a partir do teorema de Kőnig (teorema 6.4).

Mais exercícios

★ Escalonamento em máquinas paralelas uniformes. Suponha dadas $n$ tarefas (= jobs) $T_1,$ $T_2,\ldots,$ $T_n$ e $k$ processadores idênticos. Cada tarefa $T_j$ precisa ser processada durante $p_j$ dias em qualquer dos processadores. O processamento permite preemption, ou seja, o processamento de $T_j$ num certo processador pode ser interrompido e depois retomado em outro (ou no mesmo) processador. Em cada instante, cada processador só pode cuidar de uma tarefa e cada tarefa só pode estar sendo excutada por um processador. Cada tarefa $T_j$ está disponível para processamento a partir de uma certa data (= release date) $r_j$ e deve estar concluída até uma certa data (= due date) $d_j$. (Suponha que $d_j \geq r_j + p_j$.) Exemplo:
\[ \begin{array}{r@{\qquad}rrrr} j & 1 & 2 & 3 & 4 \\[0.5ex] p_j & 25 & 31 & 50 & 18 \\ r_j & 10 & 50 & 0 & 20 \\ d_j & 30 & 70 & 60 & 50 \end{array} \]

Formule um problema de fluxo máximo que resolva o escalonamento. (Dica: Coloque o conjunto $\conj{r_1,d_1,r_2,d_2,\ldots,r_n,d_n}$ de datas em ordem crescente. Seja $t_1 \lt t_2 \lt \cdots \lt t_{m+1}$ o conjunto ordenado de datas, com $m+1 \leq 2n$. Agora, basta decidir que parte do processamento de cada tarefa $T_j$ será feita durante o intervalo $(t_i, t_{i+1})$.) [CCPS 3.41] [AMO 6.17]
Custos menos prêmios. Seja $r$ um nó de um grafo dirigido $D$. Para cada arco $e$, seja $c_e$ um número não-negativo que mede o custo de destruir o arco. Se um atacante destrói um conjunto $X$ de arcos, recebe um prêmio $b_v$ para cada nó $v$ que não pode mais ser alcançado por um caminho dirigido a partir de $r$. O atacante quer escolher $X$ de modo a minimizar custos menos prêmios. Sugira um algoritmo. [CCPS 3.44]

Capítulo 3Aplicações de fluxo máximo e corte mínimo