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

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

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

D

satisfaz uma função-demanda

b

se tem excesso

b_{v}

em cada nó

v

, ou seja, se

x_{-}^{+} (v) = b_{v}

para cada nó

v

. Assim, se

b_{v} < 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) > u_{}^{+} (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 $(\overset{ˇ}{D}, \overset{ˇ}{u})$ a rede capacitada definida da seguinte maneira. O conjunto de nós de $\overset{ˇ}{D}$ é $V \cup {r, s}$ , sendo $r$ e $s$ dois novos nós, e o conjunto de arcos de $\overset{ˇ}{D}$ é definido assim:

para cada $p$ em $P$ , há um arco $r p$ em $\overset{ˇ}{D}$ com ${\overset{ˇ}{u}}_{r p} := - b_{p}$ ;
para cada $q$ em $Q$ , há um arco $q s$ em $\overset{ˇ}{D}$ com ${\overset{ˇ}{u}}_{q s} := b_{q}$ ;
para cada arco $v w$ de $D$ , há um arco $v w$ em $\overset{ˇ}{D}$ com ${\overset{ˇ}{u}}_{v w} := u_{v w}$ .

Seja $R$ um conjunto que separa $r$ de $s$ em $\overset{ˇ}{D}$ . A capacidade do corte $\partial_{}^{-} (R)$ na rede $(\overset{ˇ}{D}, \overset{ˇ}{u})$ é a soma de três parcelas: as capacidades dos arcos que vão de $r$ a $P ∖ 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 ∖ R$ . Adote a notação $R^{'} := V ∖ R$ e observe que $\begin{aligned} {\overset{ˇ}{u}}_{}^{-} (R) & = - b (P ∖ R) + b (Q \cap R) + u_{}^{+} (R^{'}) \\ \geq - b (P ∖ R) + b (Q \cap R) + b (R^{'}) \\ = - b (P ∖ R) + b (Q \cap R) + b (P ∖ R) + b (Q ∖ R) \\ = b (Q \cap R) + b (Q ∖ R) \\ = b (Q) . \end{aligned}$ Concluímos assim que todo corte que separa $r$ de $s$ na rede $(\overset{ˇ}{D}, \overset{ˇ}{u})$ tem capacidade pelo menos $b (Q)$ . Segue daí, pelo teorema MFMC (teorema 2.9), que existe um fluxo viável $\overset{ˇ}{x}$ na rede $(\overset{ˇ}{D}, \overset{ˇ}{u}, r, s)$ tal que $int (\overset{ˇ}{x}) = b (Q)$ . Como $int (\overset{ˇ}{x}) =$ ${\overset{ˇ}{x}}_{}^{+} (s) \leq$ ${\overset{ˇ}{u}}_{}^{+} (s) = b (Q)$ , todos os arcos que entram em $s$ estão cheios de fluxo e portanto ${\overset{ˇ}{x}}_{q s} = b_{q}$ para todo $q$ em $Q$ . Como $b (V) = 0$ e portanto $b (P) = - b (Q)$ , temos também ${\overset{ˇ}{x}}_{r p} = - b_{p}$ para todo $p$ em $P$ .

Seja $x$ a restrição de $\overset{ˇ}{x}$ aos arcos da rede original $(D, u)$ . É claro que $x$ respeita $u$ . Resta mostrar que $x$ satisfaz $b$ . Para cada $q$ em $Q$ temos $x_{-}^{+} (q) =$ ${\overset{ˇ}{x}}_{-}^{+} (q) + {\overset{ˇ}{x}}_{q s} =$ ${\overset{ˇ}{x}}_{q s} = b_{q}$ . Analogamente, $x_{-}^{+} (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 $(\overset{ˇ}{D}, \overset{ˇ}{u}, r, s)$ construída na prova do teorema 3.2 (complete a figura). A segunda tabela mostra um fluxo viável $\overset{ˇ}{x}$ de $r$ a $s$ na rede $(\overset{ˇ}{D}, \overset{ˇ}{u}, r, s)$ .

\begin{array}{lrrrrrr} r & p & i & j & q & s \\ r & - & - & 1 & - & 1 & - \\ p & - & - & 1 & 1 & - & 1 \\ i & - & - & - & - & 1 & - \\ j & - & - & 1 & - & 1 & 1 \\ q & - & 1 & - & - & - & - \\ s & - & - & - & - & - & - \end{array}

\begin{array}{lrrrrrrrrrr} r i & r q & p i & p j & i q & j i & j q & q p & p s & j s \\ \overset{ˇ}{u} & 2 & 1 & 6 & 4 & 3 & 1 & 2 & 3 & 2 & 1 \\ \overset{ˇ}{x} & 2 & 1 & 0 & 1 & 2 & 0 & 0 & 3 & 2 & 1 \end{array}

\begin{array}{ccccc} r \\ i \\ p & q \\ j \\ s \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_{q p}$ .)

\begin{array}{lccccr} p & i & j & q & b \\ p & - & 1 & 1 & - & + 2 \\ i & - & - & - & 1 & - 2 \\ j & - & 1 & - & 1 & + 1 \\ q & 1 & - & - & - & - 1 \end{array} \begin{array}{lcccccc} p i & p j & i q & j i & j q & q p \\ u & 6 & 4 & 3 & 1 & 2 & 2 \end{array}

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

Tal como apresentada acima, a condição de Gale é assimétrica. Mas ela equivale à seguinte condição simétrica:

- u_{}^{-} (X) \leq

b (X) \leq

u_{}^{+} (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

u

são definidas assim:

b_{p} = - a_{p}

para cada

p

P

b_{q} = a_{q}

para cada

q

Q

, e

u_{p q} = \infty

para cada arco

p q

D

. Como

D

é bipartido, temos

x_{-}^{+} (p) = x^{-} (p)

para todo

p

P

x_{-}^{+} (q) = x^{+} (q)

para todo

q

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

Q

, denotamos por

N (Y)

o conjunto de todos os nós

p

P

para os quais existe um arco

p q

com

q

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 u_{}^{+} (X)$ para todo subconjunto $X$ de $V (D)$ . Há dois casos a considerar. Se $\partial_{}^{+} (X) \neq \emptyset$ então $u_{}^{+} (X) = \infty$ e portanto $b (X) \leq u_{}^{+} (X)$ . Por outro lado, se $\partial_{}^{+} (X) = \emptyset$ então $u_{}^{+} (X) = 0$ e $N (Q \cap X) \subseteq P \cap X$ . Segue daí que $a (P \cap X) \geq$ $a (N (Q \cap X) \geq$ $a (Q \cap X)$ , donde $b (X) =$ $b (P \cap X) + b (Q \cap X) =$ $- a (P \cap X) + a (Q \cap X) \leq$ $- a (Q \cap X) + a (Q \cap X) = 0$ , e assim $b (X) \leq u_{}^{+} (X)$ . Concluímos que em ambos os casos temos $b (X) \leq u_{}^{+} (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: $- u_{}^{-} (X) \leq b (X) \leq u_{}^{+} (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 u_{}^{+} (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} - x_{-}^{+} (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}{lrrrrrr} r & a & b & c & d & s \\ b & + 3 & + 2 & + 2 & - 1 & - 3 & - 3 \end{array}$ $\begin{array}{lccccccc} r a & r b & a c & b d & c s & d s & s r \\ 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 $\partial_{}^{+} (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 $v w$ por $w v$ ) resulte em um grafo dirigido $\overset{ˇ}{D}$ tal que $| \partial_{}^{+} (v) | = | \partial_{}^{-} (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 é, $| \partial_{}^{-} (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 $α_{1}, \dots, α_{n}$ e $β_{1}, \dots, β_{n}$ números inteiros não-negativos. Queremos construir um grafo dirigido com conjunto de nós ${v_{1}, \dots, v_{n}}$ tal que cada nó $v_{i}$ tem grau de saída $α_{i}$ e grau de entrada $β_{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}, \dots, d_{n})$ represente um torneio. Dê um algoritmo que decida se $(d_{1}, \dots, 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 R_{+}^{E}

. [A letra

l

é a inicial de lower bound.] Dizemos que um fluxo

x

no grafo satisfaz a demanda

l

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

l_{}^{-} (X)

u_{}^{+} (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

l_{}^{-} (X) > u_{}^{+} (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 $- l_{-}^{+}$ 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 $l_{-}^{+} (v)$ de fluxo em cada nó $v$ . Em virtude do lema 2.1 do capítulo 2, $\begin{matrix} (1) & - l_{-}^{+} (V) = 0 . \end{matrix}$

Agora considere a hipótese $l_{}^{-} (X) \leq u_{}^{+} (X)$ . Se subtrairmos $l_{}^{+} (X)$ dos dois lados da desigualdade teremos $\begin{matrix} (2) & - l_{-}^{+} (X) \leq (u - l)_{}^{+} (X) . \end{matrix}$

Nossa rede $(D, l, u)$ pode ser vista como uma instância $(D, b, \overset{ˇ}{u})$ do problema de Gale com $b$ e $\overset{ˇ}{u}$ definidos assim: $b := - l_{-}^{+} e \overset{ˇ}{u} := u - l .$

O parâmetro $b$ é uma função-demanda. Como $l \leq u$ , o parâmetro $\overset{ˇ}{u}$ é uma função-capacidade. Graças a $(1)$ e $(2)$ , a rede $(D, b, \overset{ˇ}{u})$ satisfaz a condição de Gale: $b (V) = 0 e b (X) \leq {\overset{ˇ}{u}}_{-}^{+} (X)$ para cada $X \subseteq V$ . O teorema 3.2 garante então que a rede $(D, b, \overset{ˇ}{u})$ tem um fluxo $\overset{ˇ}{x}$ tal que ${\overset{ˇ}{x}}_{-}^{+} = b$ e $\overset{ˇ}{x} \leq \overset{ˇ}{u}$ . Para retornar à rede original $(D, l, u)$ , considere o fluxo $x := \overset{ˇ}{x} + l$ (trata-se de um fluxo pois $\overset{ˇ}{x} \geq 0$ e $l \geq 0$ ). É claro que $l \leq$ $x \leq$ $\overset{ˇ}{u} + l = u$ . Ademais, $x$ é uma circulação pois $\begin{aligned} x_{-}^{+} (v) & = {\overset{ˇ}{x}}_{-}^{+} (v) + l_{-}^{+} (v) \\ = b_{v} + l_{-}^{+} (v) \\ = - l_{-}^{+} (v) + l_{-}^{+} (v) \\ = 0 \end{aligned}$

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

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

\begin{array}{lc} b \\ p & + 2 \\ i & - 2 \\ j & + 1 \\ q & - 1 \end{array} \begin{array}{lcccccc} p i & p j & i q & j i & j q & q p \\ \overset{ˇ}{u} & 6 & 4 & 3 & 1 & 2 & 3 \\ \overset{ˇ}{x} & 0 & 1 & 2 & 0 & 0 & 3 \end{array}

A tabela acima mostra um fluxo

\overset{ˇ}{x}

que satisfaz

b

e respeita

\overset{ˇ}{u}

. Essa rede

(D, b, \overset{ˇ}{u})

é 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_{q p}$ . A rede não tem circulação viável pois o conjunto $X := {p, j}$ não satisfaz a condição $l_{}^{-} (X) \leq u_{}^{+} (X)$ .

\begin{array}{lcccc} p & i & j & q \\ p & - & 1 & 1 & - \\ i & - & - & - & 1 \\ j & - & 1 & - & 1 \\ q & 1 & - & - & - \end{array} \begin{array}{lccccccc} p i & p j & i q & j i & j q & q p \\ 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 $l_{}^{-} (X) \leq u_{}^{+} (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 $R_{+}$ . 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$ $min (u_{e} : e \in E)$ . Parte 2: Supondo que $max (l_{e} : e \in E) >$ $min (u_{e} : e \in E)$ , 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}{cccccccc} r a & r b & a c & b d & c s & d s & s r \\ 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}{cccccccc} r a & r c & a b & d c & b s & d s & s r \\ 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 $l_{}^{+} (X) \leq u_{}^{-} (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 $| \partial_{}^{+} (v) | = | \partial_{}^{-} (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

r

s

significa que

x_{-}^{+} (s) \geq 0

x_{-}^{+} (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

s

e satisfaz as condições

x \geq l

int (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

s

. (Como se sabe, um corte

\partial_{}^{-} (X)

é dirigido se

\partial_{}^{+} (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

s

. Numa rede fonte-sorvedouro, algum fluxo

x

r

s

é tal que

x \geq l

. Como não existe caminho dirigido de

s

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 $\overset{ˇ}{D}$ acrescentando um novo arco $s r$ a $D$ e seja $\overset{ˇ}{E}$ o conjunto de arcos de $\overset{ˇ}{D}$ . Seja $\overset{ˇ}{l}$ a função de $\overset{ˇ}{E}$ em $R_{+}$ definida por ${\overset{ˇ}{l}}_{s r} = 0$ e ${\overset{ˇ}{l}}_{e} = l_{e}$ para cada $e$ em $E$ . Seja $\overset{ˇ}{u}$ a função-capacidade definida em $\overset{ˇ}{E}$ pelas seguintes propriedades: ${\overset{ˇ}{u}}_{s r} = k e {\overset{ˇ}{u}}_{e} = \infty para cada e em E$ É claro que $l \leq u$ . Para provar que rede $(\overset{ˇ}{D}, \overset{ˇ}{l}, \overset{ˇ}{u})$ satisfaz a condição de Hoffman resta mostrar que ${\overset{ˇ}{l}}_{}^{-} (X) \leq {\overset{ˇ}{u}}_{}^{+} (X)$ para todo subconjunto $X$ de $V (\overset{ˇ}{D})$ . Há três casos a considerar, dependendo dos valores de $\partial_{}^{-} (X)$ e $\partial_{}^{+} (X)$ em $D$ :

Se $\partial_{}^{+} (X) = \partial_{}^{-} (X) = \emptyset$ em $D$ então ${\overset{ˇ}{l}}_{}^{-} (X) = 0 \leq {\overset{ˇ}{u}}_{}^{+} (X)$ onde quer que o arco $s r$ esteja em relação a $X$ .
Se $\partial_{}^{+} (X) \neq \emptyset$ então ${\overset{ˇ}{l}}_{}^{-} (X) \leq {\overset{ˇ}{u}}_{}^{+} (X)$ pois algum arco de $D$ entra em $X$ e portanto ${\overset{ˇ}{u}}_{}^{+} (X) = \infty$ .
Suponha agora que $\partial_{}^{+} (X) = \emptyset$ e $\partial_{}^{-} (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 $\partial_{}^{-} (X)$ é dirigido, temos $r \in X$ e $s \notin X$ , ou seja, $X$ separa $r$ de $s$ . Logo $l_{}^{-} (X) \leq u_{}^{+} (X)$ , e portanto ${\overset{ˇ}{l}}_{}^{-} (X) =$ $l_{}^{-} (X) \leq$ $u_{}^{+} (X) \leq {\overset{ˇ}{u}}_{}^{+} (X)$ .

Como ${\overset{ˇ}{l}}_{}^{-} (X) \leq {\overset{ˇ}{u}}_{}^{+} (X)$ para todo subconjunto $X$ de $V (\overset{ˇ}{D})$ , o teorema 3.6 garante que a rede $(\overset{ˇ}{D}, \overset{ˇ}{l}, \overset{ˇ}{u})$ tem uma circulação viável, digamos $\overset{ˇ}{x}$ . A restrição de $\overset{ˇ}{x}$ ao conjunto $E$ de arcos é um fluxo $x$ de $r$ a $s$ em $D$ . Ademais, $x \geq l$ e $int (x) \leq$ ${\overset{ˇ}{u}}_{s r} = 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 $(\overset{ˇ}{D}, \overset{ˇ}{l}, \overset{ˇ}{u})$ construída na prova do teorema 3.9:

\begin{array}{rcccc} p & i & j & q \\ r = p & - & 1 & 1 & - \\ i & - & - & - & 1 \\ j & - & 1 & - & 1 \\ s = q & 1 & - & - & - \end{array} \begin{array}{lccccccc} p i & p j & i q & j i & j q & q p \\ \overset{ˇ}{l} & 1 & 1 & 0 & 1 & 1 & 0 \\ \overset{ˇ}{u} & \infty & \infty & \infty & \infty & \infty & 3 \\ \overset{ˇ}{x} & 1 & 2 & 2 & 1 & 1 & 3 \end{array}

(A rede $(\overset{ˇ}{D}, \overset{ˇ}{l}, \overset{ˇ}{u})$ só difere da rede do exemplo 3.6 porque $\overset{ˇ}{u}$ é diferente.) A última linha da tabela dá uma circulação $\overset{ˇ}{x}$ tal que $\overset{ˇ}{l} \leq$ $\overset{ˇ}{x} \leq \overset{ˇ}{u}$ .

Exemplo 3.11: Para verificar que não existe fluxo $2$ -viável na rede do exemplo 3.9, tome o conjunto $X := {p, j}$ e observe que o corte dirigido $\partial_{}^{-} (X)$ separa $r$ de $s$ e que $l_{}^{-} (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}{ccccc} r a & a s & s b & b r \\ 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}{ccccccc} r a & r b & a c & b d & c s & d s \\ 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}{ccccccc} r a & r c & a b & d c & b s & d s \\ 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}{cccccc} r a & a r & a b & b s & s b \\ 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

P

é uma cobertura e

C

é um corte dirigido então é evidente que

| P | \geq | C |

. Se vale a igualdade, a cobertura

P

é 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, $| P | \geq | C |$ para qualquer cobertura $P$ e qualquer corte dirigido $C$ . Resta mostrar que $| P | = | C |$ para alguma $P$ e algum $C$ .

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

Seja $l$ a função-demanda definida sobre os arcos de $\overset{ˇ}{D}$ pelas seguintes propriedades: $l_{e} = 1$ para cada $e$ em $E (D)$ e $l_{f} = 0$ para cada $f$ em $E (\overset{ˇ}{D}) ∖ E (D)$ . Na rede $(\overset{ˇ}{D}, 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 $\partial_{}^{-} (X)$ um corte dirigido que maximiza $l_{}^{-} (X)$ dentre os cortes dirigidos que separam $r$ de $s$ . De acordo com o teorema 3.10, $int (x) = l_{}^{-} (X) .$ Denote por $X - r$ o conjunto $X ∖ {r}$ . No grafo $D$ , temos $| \partial_{}^{-} (X - r) | = l_{}^{-} (X)$ , donde $int (x) = | \partial_{}^{-} (X - r) | .$ 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 $int (x)$ caminhos dirigidos simples em $\overset{ˇ}{D}$ , todos de $r$ a $s$ , conforme o lema 2.5 do capítulo 2. Digamos que $P_{1}, \dots, P_{k}$ são os caminhos da decomposição, com $k = int (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 ${Q_{1}, \dots, Q_{k}}$ de caminhos é uma cobertura dos arcos de $D$ . Ademais, o número de caminhos é $k = | \partial_{}^{-} (X - r) |$ e $\partial_{}^{-} (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

P

dos nós e qualquer anticadeia

B

, é claro que

| P | \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, $| P | \geq | B |$ para qualquer cobertura $P$ e qualquer anticadeia $B$ . Resta mostrar que $| P | = | B |$ para alguma $P$ e alguma $B$ .

Seja $D$ o DAG em questão. Construa um grafo dirigido $\overset{ˇ}{D}$ da seguinte maneira. Para cada nó $v$ de $D$ , o grafo $\overset{ˇ}{D}$ tem dois nós, $v_{1}$ e $v_{2}$ , $ligados por um arco v_{1} v_{2} .$ Para cada arco $v w$ de $D$ , o grafo $\overset{ˇ}{D}$ tem um arco $v_{2} w_{1}$ . Além disso, $\overset{ˇ}{D}$ tem dois novos nós, $r$ e $s$ , um arco $r v_{1}$ para cada fonte $v$ de $D$ , e um arco $w_{2} s$ para cada sorvedouro $w$ de $D$ . Os arcos da forma $v_{1} v_{2}$ serão chamados especiais; eles representam os nós de $D$ . A rede $(\overset{ˇ}{D}, r, s)$ é fonte-sorvedouro no sentido da seção 3.3.

Defina uma função-demanda $l$ sobre os arcos de $\overset{ˇ}{D}$ 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 $(\overset{ˇ}{D}, l, r, s)$ garante que existe um fluxo $x$ de $r$ a $s$ tal que $x \geq l$ e existe um corte dirigido $\partial_{}^{-} (X)$ que separa $r$ de $s$ tal que $int (x) = l_{}^{-} (X) .$ 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 $\overset{ˇ}{D}$ . Observe que $| B | = l_{}^{-} (X)$ e portanto $int (x) = | B | .$ 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 $\overset{ˇ}{D}$ , esse caminho corresponde a um caminho dirigido que vai de $v_{2}$ a $w_{1}$ . Portanto, o caminho começa em $V (\overset{ˇ}{D}) ∖ X$ e termina em $X$ , e assim tem um arco em $\partial_{}^{+} (X)$ . Mas isso é impossível, pois o corte $\partial_{}^{-} (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 $int (x)$ caminhos dirigidos simples em $\overset{ˇ}{D}$ , todos de $r$ a $s$ . Sejam $P_{1}, \dots, P_{k}$ esses caminhos, com $k = int (x)$ . É claro que cada arco especial de $\overset{ˇ}{D}$ pertence a algum dos caminhos. Cada $P_{i}$ induz um caminho dirigido $Q_{i}$ em $D$ . O conjunto ${Q_{1}, \dots, 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 $P$ uma cobertura (por caminhos dirigidos) dos arcos de $D$ . Seja $\partial_{}^{-} (X)$ um corte dirigido em $D$ . Dê uma prova elementar da desigualdade $| P | \geq | \partial_{}^{-} (X) |$ , ou seja, prove a desigualdade diretamente.
★ Seja $D$ um grafo dirigido e $P$ uma cobertura (por caminhos dirigidos) dos nós de $D$ . Seja $B$ uma anticadeia em $D$ . Dê uma prova elementar da desigualdade $| P | \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 $P$ 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 $P$ é disjunta, ou seja, que cada nó de $D$ pertence a apenas um dos caminhos de $P$ ?
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_{i j}$ 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 $C$ a coleção de todos os caminhos dirigidos em um grafo dirigido $D$ . Seja $A$ a matriz binária indexada por $V (D) \times C$ 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) ∖ 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}, \dots,$ $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}{rrrrr} j & 1 & 2 & 3 & 4 \\ 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 ${r_{1}, d_{1}, r_{2}, d_{2}, \dots, r_{n}, d_{n}}$ de datas em ordem crescente. Seja $t_{1} < t_{2} < \dots < t_{m + 1}$ o conjunto ordenado de datas, com $m + 1 \leq 2 n$ . 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

3.1 O problema de Gale

Problemas de transporte

Exercícios 3.1

3.2 O problema de Hoffman

Exercícios 3.2

3.3 Fluxo mínimo

Exercícios 3.3

3.4 Coberturas por caminhos

Teorema de Dilworth

Exercícios 3.4

Mais exercícios

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