Embed Size (px)
Citation preview
Perguntas e respostas deOtimização Combinatória
www.ime.usp.br/~pf/otimizacao-combinatoria/
Paulo FeofiloffDepartamento de Ciência da Computação
Instituto de Matemática e Estatística
Universidade de São Paulo
2018-03-12
2 FEOFILOFF
Prefácio
Estas notas de aula em estilo perguntas-e-respostas — ainda muito incompletas —estão sendo escritas para as disciplinas de Otimização Combinatória do Instituto deMatemática e Estatística da Universidade de São Paulo.
As notas pretendem discutir algoritmos para alguns problemas de otimização com-binatória, como o problema do caminho mínimo, do fluxo máximo, do fluxo viávelde custo mínimo, do corte não-dirigido mínimo, do emparelhamento máximo, e doemparelhamento perfeito de custo mínimo.
Supõe-se que o leitor tem algum conhecimento prévio de teoria dos grafos, de progra-mação linear, de análise de algoritmos, e de estruturas de dados básicas.
As notas estão sendo extraídas do meu texto Otimização Combinatória, baseado noslivros de Cook, Cunningham, Pulleyblank e Schrijver [CCPS98], Schrijver [Sch03],Ahuja, Magnanti e Orlin [AMO93], e Cormen, Leiserson, Rivest e Stein [CLRS01].Apelidei esses livros de CCPS, Sch, AMO e CLRS, respectivamente. A maior partedas figuras foi copiada de CCPS (descaradamente, sem permissão).
Os exercícios marcados com “?” complementam pontos que o texto indicou mas nãodesenvolveu. Exercícios particularmente interessantes ou importantes também sãomarcados com “?”. Mas essas indicações não são sistemáticas nem consistentes.
—P.F.
i
ii FEOFILOFF
Sumário
1 Preliminares 1
1.1 Digrafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Grafos não-dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Programação linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Complexidade de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Comparação assintótica de funções . . . . . . . . . . . . . . . . . . . . . . 11
1.6 Convenções gerais de notação e terminologia . . . . . . . . . . . . . . . . 11
2 Caminhos dirigidos de custo mínimo 13
2.1 O problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Potencial viável . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.3 Algoritmo de Ford . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Algoritmo de Ford-Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Dicircuitos negativos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.6 Programas lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7 Algoritmo especial para redes acíclicas . . . . . . . . . . . . . . . . . . . . 15
2.8 Algoritmo especial para custos não-negativos . . . . . . . . . . . . . . . . 15
2.9 Custos unitários e busca em largura . . . . . . . . . . . . . . . . . . . . . 15
3 Fluxo máximo e corte mínimo 17
3.1 Fluxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Capacidades e o problema do fluxo máximo . . . . . . . . . . . . . . . . 19
3.3 Fluxos versus dicaminhos . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4 Algoritmo de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5 Fluxos versus cortes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.6 Versão Edmonds-Karp do algoritmo . . . . . . . . . . . . . . . . . . . . . 24
iii
iv SUMÁRIO FEOFILOFF
3.7 Programas lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Bibliografia 29
Índice Remissivo 30
Capítulo 1
Preliminares
Muitos problemas de otimização combinatória são formuladas sobre grafos. Examinaresses problemas sob o prisma da programação linear é muito revelador. Para estudara eficiência dos algoritmos que resolvem os problemas é preciso conhecer um mínimodas técnicas de análise de algoritmos.
1.1 Digrafos
O que é um digrafo? Um digrafo (= digraph) é um par (V,E) de conjuntos, sendo Vqualquer conjunto finito e E um conjunto de pares ordenados de elementos de V . Oselementos de V são chamados nós e os elementos de E são chamados arcos. O conjuntode nós de um digrafo G é denotado por V (G) e o conjunto de arcos por E(G).1
Qual a diferença entre digrafo e grafo dirigido? Nenhuma. Digrafos também sãoconhecidos como grafos dirigidos (= directed graphs). O neologismo “digrafo” é fácil deescrever, mas desagradável de pronunciar. Em discussões orais, prefiro dizer “grafodirigido”.
Como podemos falar da relação entre um arco e seus nós? Um arco (v, w) pode serdenotado simplesmente por vw. O nó v é a ponta inicial (= tail) e o nó w é a ponta final(= head) do arco. Dizemos que um tal arco sai de v e entra em w.
Um digrafo pode ter arcos paralelos? Pode ter laços? Não. Dois arcos diferentes nãopodem ter a mesma ponta inicial e a mesma ponta final. Além disso, as pontas iniciale final de cada arco são distintas.
1 As letras “V ” e “E” são as iniciais de “vertex” e “edge”, respectivamente. Teria sido mais coerenteusar as iniciais “N” e “A” de “node” e “arc”.
1
2 PRELIMINARES FEOFILOFF
O que é um digrafo simétrico? Dois arcos vw e v′w′ de um digrafo são antiparalelos,ou mutuamente inversos, se v′ = w e w′ = v. Um digrafo é simétrico se a presença deum arco implica na presença do arco inverso.
Qual a notação para o número de nós e de arcos? O número de nós de um digrafoé denotado por n e o número de arcos por m. Portanto, se G é o digrafo em discussãoentão n := |V (G)| e m := |E(G)|. É claro que m ≤ n(n− 1) < n2.
O que é um subdigrafo? Um subdigrafo de um digrafoG é qualquer digrafoG′ tal queV (G′) ⊆ V (G) e E(G′) ⊆ E(G). Se V (G′) = V (G), dizemos que G′ é um subdigrafogerador (= spanning). Dado um subconjunto V ′ de V (G), se E ′ é o conjunto de todosos arcos de G que têm ambas as pontas em V ′, dizemos que o subdigrafo (V ′, E ′) éinduzido por V ′. Dado um subconjunto E ′ de E(G), se V ′ é o conjunto de todos os nósde G que incidem em arcos de E ′, dizemos que subdigrafo (V ′, E ′) é induzido por E ′.
O que significam as expressões G− v e G− e? Se v é um nó de um digrafo G entãoG−v é o subdigrafo induzido por V (G)rv. Se e é um arco entãoG−e é o subdigrafoque tem conjunto de nós V (G) e conjunto de arcos E(G)r e. Para qualquer par (i, j)de nós, denotamos por G + ij o digrafo que tem conjunto de nós V (G) e conjunto dearcos E(G) ∪ ij.
O que é a matriz de um digrafo? A matriz de adjacências tem linhas e colunas indexa-das pelos nós. A componente da matriz na posição (v, w) vale 1 se vw é um arco e vale0 em caso contrário.
A matriz de incidências tem linhas indexadas pelos nós e colunas indexadas pelos arcos.A coluna que corresponde a um arco vw tem um−1 na posição v e um +1 na posiçãow,sendo o resto da coluna igual a 0. Portanto, a linha da matriz que corresponde ao nóv tem um +1 na coluna correspondente a cada arco que entra em v, um −1 na posiçãocorrespondente a cada arco que sai de v, e 0 em todas as demais posições.
Por exemplo, o digrafo com nós u v w z e arcos uw vw zu uz zw tem a matriz de ad-jacências representada à esquerda (com “−” no lugar de “0”) e a matriz de incidênciasrepresentada à direita:
u v w z
u − − 1 1v − − 1 −w − − − −z 1 − 1 −
uw vw zu uz zw
u −1 0 +1 −1 0v 0 −1 0 0 0w +1 +1 0 0 +1z 0 0 −1 +1 −1
O que é um caminho? Um caminho (= path) num digrafo é qualquer sequência alter-nante (v0, e1, v1, e2, . . . , ep, vp) de nós e arcos tal que cada arco ek tem pontas vk−1 e vk.Se ek = vk−1vk, o arco ek é direto; se ek = vkvk−1, o arco ek é inverso. O nó v0 é a origem
FEOFILOFF PRELIMINARES 3
do caminho e vp é o término. Dizemos que o caminho vai de v0 a vp. O conjunto de nósde um caminho P é denotado por V (P ) e o conjunto de arcos por E(P ).
Um caminho é dirigido se todos os seus arcos são diretos. Caminhos dirigidos tambémsão chamados dicaminhos (= dipaths). (O neologismo “dicaminho” é feio, mas cômodoem texto escrito.)
O que é o comprimento de um caminho? O comprimento de um caminho (v0,e1, v1, . . . , ep, vp) é o número p, ou seja, o número de termos da sequência que são arcos.O comprimento de um caminho P é pelo menos |E(P )|, valendo a igualdade somentese P não tem arcos repetidos.
Posso representar um caminho por uma sequência de nós? Sim. O caminho (v0, e1,v1, e2, . . . , ep, vp) pode ser indicado pela sequência (v0, v1, . . . , vp) de seus nós, emboraessa abreviatura seja ambígua quando o digrafo tem arcos antiparalelos.
Posso colar o término de caminho com a origem de outro? Se o término de um cami-nho (v0, v1, . . . , vp) é igual à origem de um caminho (w0, w1, . . . , wq), os dois caminhospodem ser concatenados. O resultado da concatenação é o caminho (v0, v1, . . . , vp, w1,w2, . . . , wq). A concatenação de dois caminhos P e Q é denotada por P ·Q.
O que é um caminho simples? Um caminho é simples se não tem nós repetidos(e portanto não tem arcos repetidos). Se um caminho P é simples, seu comprimentoé |E(P )|. Se Q é um caminho com origem r e término s então alguma subsequência2
de Q é um caminho simples de r a s. Por exemplo, se (u, v, w, x, v, w, z) é um caminhoentão (u, v, w, z) é o correspondente caminho simples.
O que significa um nó estar ao alcance de outro? Dizemos que um nó v de umdigrafo está ao alcance de um nó r se existe um dicaminho de r a v.
O que é um digrafo conexo? O que são componentes conexas? Um digrafo é conexose, para cada par (r, s) de nós, existe um caminho (não necessariamente dirigido) de ra s (e portanto também um caminho de s a r). Uma componente conexa de um digrafo Gé um subdigrafo conexo maximal de G.
Um digrafo é fortemente conexo se, para cada par (r, s) de nós, existe um dicaminho der a s e um dicaminho de s a r.
O que é um circuito? Um circuito (= circuit) é um caminho (v0, e1, v1, . . . , ep−1, vp−1,ep, vp) que satisfaz quatro condições: p ≥ 2, o caminho (v0, e1, v1, . . . , ep−1, vp−1) é sim-ples, vp = v0, e ep 6= ep−1. (A última condição é redundante se p > 2.) Um circuito
2 Por exemplo, (b, c, e, h) é subsequência de (a, b, c, d, e, f, g, h) mas (c, a) não é subsequência de(a, b, c, d).
4 PRELIMINARES FEOFILOFF
é dirigido se todos os seus arcos são diretos. Um circuito dirigido também pode serchamado de dicircuito (= dicircuit).
O que é um DAG? Um DAG (abreviatura de directed acyclic graph) é um digrafoacíclico. Um digrafo é acíclico se não tem dicircuitos.
O que são florestas e árvores? Uma floresta (= forest) é um digrafo sem circuitos (emparticular, sem dicircuitos). Toda floresta é um DAG, mas nem todo DAG é umafloresta. Uma árvore3 (= tree) é uma floresta conexa. Para quaisquer dois nós r e sde uma árvore, existe um e um só caminho simples de r a s. Para todo arco e de umaárvore T , o digrafo T − e é uma floresta com exatamente duas componentes conexas.
O que é uma árvore divergente? Uma árvore divergente, ou arborescência, é uma árvoreT dotada de um nó r que tem a seguinte propriedade: para cada nó v, o único caminhosimples de r a v é dirigido. O nó r é a raiz da arborescência.
No exemplo à esquerda, vemos a matriz de adjacências de uma árvore com nósa b c d e f . À direita, uma árvore divergente com o mesmo conjunto de nós e raiz c.(Faça figuras.)
a b c d e f
a − − − − − −b − − 1 − − −c 1 − − 1 − −d − − − − 1 −e − − − − − −f − − − 1 − −
a b c d e f
a − − − − − −b − − − − − −c 1 1 − 1 − −d − − − − 1 1e − − − − − −f − − − − − −
O que é um digrafo bipartido? Um digrafo G é bipartido se estiver acompanhado deuma bipartição4 P,Q de V (G) tal que todo arco tem uma ponta (a inicial ou a final)em P e outra em Q.
Um digrafo é bipartido se e somente se não tem circuito de comprimento ímpar.
Qual a notação para os arcos que saem de um conjunto de nós? Dado um digrafoG := (V,E) e um subconjunto R de V , denotamos por R o conjunto V r R. Dizemosque um arco vw entra em R se v ∈ R e w ∈ R. Dizemos que vw sai de R se v ∈ R e w ∈ R.O conjunto de todos os arcos que entram em R é denotado por
∂+(R) .
3 Há quem diga “árvore dirigida”.4 Uma bipartição de um conjunto V é um par P,Q de subconjuntos de V tal que P ∪ Q = V e
P ∩Q = ∅. A expressão “P é uma das partições” está errada; diga “P é um dos blocos da partição”.
FEOFILOFF PRELIMINARES 5
Analogamente, ∂−(R) é o conjunto de todos os arcos que saem de R.5 É claro que∂+(R) = ∂−(R). É claro também que ∂+(∅) = ∂+(V ) = ∂−(∅) = ∂−(V ) = ∅. Se v é umnó, usamos a abreviatura ∂+(v) para ∂+(v).
O que são fontes e sorvedouros? O que é o grau de um nó? Um nó v é fonte (= source)se ∂+(v) = ∅ e sorvedouro (= sink) se ∂−(v) = ∅. O número |∂+(v)| é o grau de entrada(= indegree) de v e o número |∂−(v)| é o grau de saída (= outdegree) de v. É claro que|∂+(v)| ≤ n − 1 e |∂−(v)| ≤ n − 1. É claro também que
∑(|∂+(v)| : v ∈ V ) = m e∑
(|∂−(v)| : v ∈ V ) = m.
O que é um corte? Um corte (= cut) em um digrafo G é o conjunto de todos os arcosque saem de algum conjunto de nós. Em outras palavras, um corte é qualquer con-junto da forma ∂−(R), com R ⊆ V (G). (À primeira vista pode parecer que um cortedeveria ser definido como ∂+(R) ∪ ∂−(R), mas a definição que adotamos é mais útil.)O conjunto R é a margem negativa do corte e R é a margem positiva.
Então um corte não é um conjunto de nós? Isso mesmo. Um corte é um conjunto dearcos. Mas para definir o corte precisamos de um conjunto de nós (a margem do corte).
O que é uma rede? Uma rede (= network) é um digrafo juntamente com uma oumais funções que atribuem números aos arcos e/ou aos nós do digrafo. O conceitoé propositalmente vago e informal. Por exemplo, se G é um digrafo e c é uma funçãode E(G) em Q, podemos dizer que (G, c) é uma rede. Da mesma forma, se b é umafunção de V (G) em Q, podemos dizer que (G, b, c) é uma rede.
Exercícios
1.1 Seja v um nó de um digrafo. Mostre que∑
(|∂+(v)| : v ∈ V ) = m e∑
(|∂−(v)| : v ∈ V ) = m.
1.2 Seja R um conjunto de nós de um digrafo G. Mostre que não existe dicaminho em G− ∂−(R) quecomeça em R e termina em R.
1.2 Grafos não-dirigidos
O que é um grafo não-dirigido? Um grafo não-dirigido (= undirected graph) é um par(V,E) em que V é um conjunto finito e E é um conjunto de pares não ordenados deelementos de V . Os elementos de E são chamados arestas (= edges). Uma aresta v, wpode ser denotada por vw ou por wv. Os nós v e w são as pontas da aresta. Quando
5 CCPS escreve “δ(R)” e “δ(R)” no lugar dos meus “∂+(R)” e “∂−(R)” respectivamente. Acho queminha notação é mais sugestiva. Para justificar os superscritos “+” e “−”, você pode imaginar que osnós são contas bancárias e os arcos representam movimentação de dinheiro. Tudo que entra em umaconta é somado ao saldo e tudo que sai é subtraído.
6 PRELIMINARES FEOFILOFF
o contexto permite, podemos dizer simplesmente “grafo”, deixando o “não-dirigido”subentendido.
Um grafo é o mesmo que um digrafo simétrico? É verdade: basta trocar cada arestapor dois arcos antiparalelos. Mas às vezes essa representação é inconveniente. É me-lhor tratar grafos não-dirigidos como um conceito independente.
O que são caminhos, graus, subgrafos etc. em grafos? As definições de caminho, cir-cuito, grau de nó, subgrafo, bipartição, etc. em grafos são análogas às correspondentesdefinições para digrafos. É claro que não há distinção entre caminhos e dicaminhos,circuitos e dicircuitos, grau de entrada e grau de saída, etc. Tipos de grafos — comoárvores não-dirigidas, por exemplo — também são definidos por analogia com os cor-respondentes tipos de digrafos.
O que são as matrizes de adjacências e incidências de um grafo? A matriz de adja-cências de um grafo não-dirigido é a matriz de adjacências do correspondente digrafosimétrico. A matriz de incidências de um grafo é binária, ou seja, suas componentesestão em 0, 1. As linhas da matriz são indexadas pelos nós e as colunas são inde-xadas pelas arestas; a coluna que corresponde a uma aresta vw tem um 1 na linha ve um 1 na linha w, sendo o resto da coluna igual a 0. Portanto, a linha da matriz quecorresponde ao nó v tem um 1 na coluna correspondente a cada aresta que incide em ve 0 em todas as demais colunas. Por exemplo, veja a matriz de incidências (com “−”representando “0”) do grafo que tem nós u v w z e arestas uw vw zu uz zw:
uw vw zu uz zw
u 1 − 1 1 −v − 1 − − −w 1 1 − − 1z − − 1 1 1
1.3 Programação linear
O que é um programa linear? Considere o seguinte exemplo: encontrar números x1,x2, x3, x4, x5 que maximizem o valor da combinação linear
51x1 + 52x2 + 53x3 + 54x4 + 55x5
enquanto satisfazem as restrições lineares
11x1 + 12x2 + 13x3 + 14x4 + 15x5 = 1621x1 + 22x2 + 23x3 + 24x4 + 25x5 = 2631x1 + 32x2 + 33x3 + 34x4 + 35x5 = 3641x1 + 42x2 + 43x3 + 44x4 + 45x5 = 46
FEOFILOFF PRELIMINARES 7
e as restrições de sinal x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 e x5 ≥ 0. O valor ótimo desseprograma linear é o valor máximo de 51x1 + 52x2 + 53x3 + 54x4 + 55x5 respeitadasas restrições. Os valores dos coeficientes nesse exemplo nada têm de especial: oscoeficientes poderiam ser quaisquer números racionais, positivos, negativos, ou nulos.O número de variáveis poderia ser diferente de 5, o número de restrições poderia sermaior ou menor, e as restrições poderiam ter “≥” ou “≤” no lugar de um ou maisdos “=”. Também poderíamos ter “minimize” no lugar de “maximize”.
O que é um pl? Ocasionalmente usamos a expressão “pl” como abreviatura de “pro-grama linear” (ou “problema de programação linear”).
Podemos usar notação matricial para descrever um pl? Sim. O problema que exibi-mos acima pode ser escrito assim: encontrar um vetor x que
maximize cx
sob as restriçõesAx = b e x ≥ 0 .
(1)
Nesse exemplo, A é a matriz representada abaixo, b é o vetor representado na verticalà direita de A e c é o vetor representado na horizontal abaixo de A:
11 12 13 14 15 1621 22 23 24 25 2631 32 33 34 35 3641 42 43 44 45 46
51 52 53 54 55
A expressão cx representa a soma c1x1 + . . .+ c5x5. Muita gente escreve “cTx” no lugardo meu “cx”, mas eu prefiro a notação mais simples!
O que é uma solução viável de um pl? O que é uma solução ótima? Ocasionalmenteusaremos a expressão “pl” como abreviatura de “programa linear” (ou “problema deprogramação linear”). Uma solução viável do pl (1) é qualquer vetor x que satisfaça asrestrições Ax = b e x ≥ 0. Uma solução ótima do pl (1) é qualquer solução viável x quemaximize cx.6
O que é um pl viável? um pl ilimitado? O pl (1) é viável (= feasible) se tem umasolução viável e inviável no caso contrário. O pl é ilimitado se for viável mas não tiversolução ótima, ou seja, se existirem soluções viáveis x para as quais cx é tão grandequanto se queira.
6 Essa terminologia tradicional é um tanto ilógica, pois a definição do pl (1) inclui a maximizaçãode cx e portanto o “ótima” da expressão “solução ótima” é redundante. Por outro lado, uma “soluçãoviável” não é, a rigor, uma solução pois não maximiza cx.
8 PRELIMINARES FEOFILOFF
Dualidade
O que é o dual de um pl? O dual do pl (1) consiste em encontrar um vetor y que
minimize yb
sob as restriçõesyA ≥ c .
(2)
A expressão yA representa a combinação linear das linhas de A com coeficientes y1,y2, . . . , da mesma forma que a expressão Ax representa a combinação linear das colu-nas de A com coeficientes x1, x2, . . . Muita gente escreve “yTA” ou “ATy” no lugar domeu “yA”, mas eu prefiro a expressão mais simples! Na minha notação, o produto devetor por matriz não é comutativo: yA não é o mesmo que Ay (em geral, um deles nemfaz sentido).
O que é uma solução viável do dual? Os conceitos de solução viável e solução ótimapara o pl dual (2) são análogos aos do pl “primal” (1). Também são análogos os con-ceitos de pl viável e pl ilimitado.
O que é o teorema fraco da dualidade? A relação básica entre os pl’s (1) e (2) éconhecida como teorema fraco da dualidade. Esse teorema dá uma delimitação supe-rior para a expressão que queremos maximizar e, ao mesmo tempo, uma delimitaçãoinferior para expressão que queremos minimizar: para qualquer solução viável x doproblema primal e qualquer solução viável y do dual, tem-se
cx ≤ yb . (3)
A prova dessa desigualdade tem apenas uma linha, mas é muito instrutiva. Ela en-volve todas as restrições dos dois pl’s (e a associatividade do produto de vetor pormatriz):
cx ≤ (yA)x = y(Ax) = yb . (4)
Se cx = yb então y certifica a otimalidade de x? Certo. Se cx = yb então, em virtudede (3), x é solução ótima do pl primal e y é solução ótima do pl dual. Portanto, paramostrar que uma solução viável x do primal é ótima, basta exibir uma solução viávely do dual tal que cx = yb.
Vale a recíproca? A recíproca é garantida pelo teorema forte da dualidade: Se osprogramas lineares (1) e (2) são viáveis então existe uma solução viável x do primeiroe uma solução viável y do segundo tais que cx = yb.
Como se demonstra o teorema? A prova do teorema é algorítmica: o algoritmo Sim-plex recebe A, b e c, decide se os dois pl’s são viáveis e, em caso afirmativo, devolve xe y tais que cx = yb. (Veja o livro de Chvátal [Chv83].)
FEOFILOFF PRELIMINARES 9
Folgas complementares
O que são folgas? Suponha que x é uma solução viável de (1) e y é uma soluçãoviável de (2). Dizemos que x é justo em um índice j se xj = 0 e folgado em j se xj > 0.Analogamente, y é justo em j se (yA)j = cj e folgado em j se (yA)j > cj . (Nesse pardual de pl’s, as folgas envolvem apenas os índices das colunas de A. Em outros pl’s, asfolgas podem envolver também os índices das linhas de A.)
O que são folgas complementares? As folgas de x e y são complementares se x é justosempre que y é folgado ou, o que dá no mesmo, se y é justo sempre que x é folgado.No caso dos pl’s (1) e (2), as folgas das soluções viáveis x e y se, para cada índice j,
(yA)j > cj implica em xj = 0 (5)
ou, equivalentemente, xj > 0 implica em (yA)j = cj . Para apresentar essas condiçõesde forma mais simétrica, você pode dizer “(yA)j = cj ou xj = 0”. (O “ou” não éexclusivo, pois podemos ter (yA)j = cj e xj = 0 para algum j.)
O que diz o teorema das folgas complementares? Para qualquer x viável em (1) equalquer y viável em (2), cx = yb se e somente se as folgas de x e y são complementares(veja o exercício 1.5). Esse é o teorema das folgas complementares. É fácil deduzir issode (4).
Um exemplo importante
O que acontece se a matriz de um pl só tem zeros e uns? Considere novamenteo pl que consiste em maximizar cx sob as restrições Ax = b e x ≥ 0. Suponhaque cada coluna de A tem exatamente uma componente igual a −1, exatamente umacomponente igual a +1, e todas as demais componentes nulas, como no exemplo aseguir.
−1 0 +1 −1 00 −1 0 0 0
+1 +1 0 0 +10 0 −1 +1 −1
Então A é a matriz de incidências de um digrafo, digamos G. As linhas de A e o vetorb são indexados por V (G); as colunas de A e o vetor c são indexados por E(G). Asrestrições Ax = b podem ser entendidas assim: para cada nó v,∑
(xe : e ∈ ∂+(v)) −∑
(xe : e ∈ ∂−(v)) = bv ,
ou seja, a soma das componentes de x nos arcos que entram em v menos a soma dascomponentes nos arcos que saem de v deve ser igual a bv.
10 PRELIMINARES FEOFILOFF
Programas lineares inteiros
O que é um pl inteiro? Um pl é inteiro se, além das restrições usuais de um pl,tiver restrições de integralidade, ou seja, se exigir que os valores das variáveis sejamnúmeros inteiros. Por exemplo, se acrescentarmos as restrições
xi ∈ Z para cada i
ao pl (1), teremos um programa linear inteiro.
A relaxação linear de um programa linear inteiro é o pl que se obtém quando as restri-ções de integralidade são removidas.
Exercícios
1.3 Seja A a matriz representada abaixo, b o vetor representado à direita de A e c o vetor representadosob A. Escreva por extenso o seguinte pl: maximize cx sujeito às restrições Ax ≤ b. Escreva porextenso o seguinte pl: maximize yb sujeito às restrições yA ≤ c.
11 12 13 14 1521 22 23 24 2531 32 33 34 35
41 42 43 44
1.4 Encontrar x que maximize x1 + 2x2 + 3x3 sob as restrições x1 ≥ 0, x2 ≥ 0, x3 ≥ 0,
x1 + x2 + x3 = −10 ex1 + 4x3 = −20 .
Esse pl é viável? inviável? ilimitado? O dual desse pl é viável? inviável? ilimitado?
1.5 Suponha que a1b1 + a2b2 + · · · + ambm = 0 sendo a1, a2, . . . , am e b1, b2, . . . , bm números não-negativos. Mostre que, para cada j, aj = 0 ou bj = 0.
1.6 O enunciado do teorema forte da programação linear tem como hipótese a viabilidade dos pl’sprimal e dual. Complete o enunciado de modo a cuidar dos pl’s inviáveis e dos ilimitados.
1.7 Considere o seguinte pl: minimizar cx sob as restriçõesAx = b e x ≥ 0. Enuncie o pl dual. Prove oteorema fraco da dualidade para esse par de pl’s. Enuncie as condições de folgas complementares.Enuncie o teorema forte da dualidade.
1.8 Considere o seguinte pl: maximizar cx sujeito às restrições Ax ≤ b e x ≥ 0. Enuncie o pldual. Prove o teorema fraco da dualidade para esse par de pl’s. Enuncie as condições de folgascomplementares. Enuncie o teorema forte da dualidade.
1.4 Complexidade de algoritmos
Como medir o consumo de tempo de um algoritmo? Adotaremos um modelo decomputação em que o consumo de tempo de cada operação aritmética entre dois nú-meros consome apenas O(1) unidades de tempo, ou seja, não depende do tamanho dosnúmeros.7
7 Para problemas que precisam lidar com números muito grandes é mais apropriado supor que aoperação a+ b, por exemplo, consome O(log a+ log b) unidades de tempo.
FEOFILOFF PRELIMINARES 11
O que é um algoritmo pseudopolinomial? Suponha que A é um algoritmo queopera sobre uma rede (G, c) em que c é uma função de E(G) em Q. A delimi-tação superior do consumo de tempo de A depende, em geral, do número C :=max (|ce| : e ∈ E(G)). O número de iterações que A executa pode, por exemplo, serproporcional a C ou talvez a logC.
Dizemos que A é pseudopolinomial se consome O(npmq C) unidades de tempo paraalgum p em Z+ e algum q em Z+.
O que é um algoritmo polinomial? fortemente polinomial? Dizemos queA é polino-mial se consome O(npmq logC) unidades de tempo. Note que logC é, essencialmente,o número de dígitos decimais de C.
Dizemos que A é fortemente polinomial se consome O(npmq) unidades de tempo paraalgum p em Z+ e algum q em Z+. O consumo de tempo não depende de C nesse caso.
1.5 Comparação assintótica de funções
O que é O()? Suponha que T e f são funções reais de uma variável inteira n. Dizemosque T é O(f) se existe uma constante k e um número n0 tais que 0 ≤ T (n) ≤ k f(n)para todo n ≥ n0. Assim, a expressão “T é O(f)” tem o sabor de “T ≤ f”.
O que é Ω()? Dizemos que T é Ω(f) se existe uma constante k e um número n0 taisque 0 ≤ k f(n) ≤ T (n) para todo n ≥ n0. Assim, a expressão “T é Ω(f)” tem o sabor de“T ≥ f”.
O que é Θ()? Dizemos que T é Θ(f) se T é O(f) e Ω(f). Portanto, a expressão“T é Θ(f)” tem o sabor de “T = f”.
Exercícios
1.9 Um grafo bipartido G é completo se existe uma bipartição (P,Q) de V (G) tal que pq ∈ E(G) paracada p em P e q em Q. Escreva um algoritmo que receba um grafo bipartido completo G e calculea bipartição (P,Q). O algoritmo deve consumir O(n) unidades de tempo, sendo n o número denós de G.
1.6 Convenções gerais de notação e terminologia
Zero é positivo? Não. Um número r é positivo se r > 0 e negativo se r < 0.8 Umnúmero r é não-negativo se r ≥ 0 e não-positivo se r ≤ 0.
8 Alguns livros preferem dizer que r é positivo se r ≥ 0 e negativo se r ≤ 0.
12 PRELIMINARES FEOFILOFF
Qual a notação para o conjunto dos reais, dos racionais e dos inteiros? O conjuntodos números reais é denotado por R e o conjunto dos reais não-negativos por R+.O conjunto dos números racionais é denotado por Q e o conjunto dos racionais não-negativos por Q+. O conjunto dos inteiros e o conjunto dos inteiros não-negativossão denotados por Z e Z+ respectivamente. Assim, Z = . . . ,−2,−1, 0,+1,+2, . . . eZ+ = 0, 1, 2, . . ..
Convém lembrar que computadores não sabem o que são números irracionas (como√2, por exemplo); eles conhecem apenas um pequeno conjunto de racionais. Os núme-
ros conhecidos como reais no mundo da computação são do tipo float ou double, etodos esses números são racionais.
Qual a diferença entre vetor e função? Um vetor é o mesmo que uma função. Umvetor indexado por um conjunto finito V é o mesmo que uma função com domínio V .O conjunto de tais funções e vetores com valores racionais pode ser denotado por QV .Um vetor c indexado por V pode ser denotado por (cv : v ∈ V ).
O que é um vetor inteiro? Um vetor é inteiro se todos as suas componentes perten-cem a Z. Um vetor é binário, ou booleano, se todas as suas componentes estão em 0, 1.Da mesma forma, uma matriz é binária, ou booleana, se todas as suas componentes estãoem 0, 1.
O que é um vetor característico? O vetor característico de um subconjunto S de umconjunto V é o vetor binário (xv : v ∈ V ) tal que xv = 1 se v ∈ S e xv = 0 se v ∈V r S. Reciprocamente, todo vetor binário x indexado por V representa o subconjuntov : xv = 1 de V .
Qual a notação para a soma de alguns componentes de um vetor? Para qualquervetor (ci : i ∈ V ) e qualquer subconjunto S de V , a soma de todos os ci em S é denotadapor c(S), ou seja,9
c(S) :=∑
(ci : i ∈ S) .
Para quaisquer vetores c e x indexados por um mesmo conjunto V , denotamos por cxa soma de todos os produtos cixi para i em S:
cx :=∑
(cixi : i ∈ V ) .
Se x é um vetor binário e S é o conjunto representado por x então cx = c(S).
9 No jargão de linguagens de programação, essa notação é um overload do símbolo c.
Capítulo 2
Caminhos dirigidos de custo mínimo
Este capítulo discute o problema dos dicaminhos de custo mínimo numa rede. Al-goritmos para esse problema são usados como ferramenta na resolução de muitosproblemas de otimização combinatória.
A rede consiste em um digrafo G e uma função c que atribui um número racional —positivo, negativo, ou nulo — a cada arco de G. Dizemos que c é uma função-custo.Para cada arco e, o número ce é o custo do arco.
2.1 O problema
O que é o problema dos caminhos mínimos? Dada uma rede (G, c) com função-custo c e um nó r em V (G), encontrar, para cada nó v, um dicaminho de r a v que tenhacusto mínimo.
2.2 Potencial viável
O que é um potencial? Um potencial numa rede (G, c) é qualquer função que atribuium número racional a cada nó da rede.1 Usamos a seguinte terminologia para descre-ver a relação entre um potencial y e um arco vw:
se yv + cvw ≥ yw então vw está relaxado,se yv + cvw = yw então vw é justo,se yv + cvw < yw então vw está tenso.2
1 O conceito de potencial não depende de um nó inicial.2 Para justificar as palavras “tenso” e “relaxado”, você pode imaginar que cada nó v é o ponto de
ordenada yv de uma reta e cada arco vw é um barbante de comprimento cvw. Ignore as direções dosarcos e suponha cvw ≥ 0.
13
14 CAMINHOS DIRIGIDOS DE CUSTO MíNIMO FEOFILOFF
O que é um potencial viável? Um potencial y é viável (= feasible) se deixa todos osarcos relaxados, ou seja, se yv + cvw ≥ yw para cada arco vw.
2.3 Algoritmo de Ford
FORD (G, c, r) (G, c) não tem dicircuitos de custo negativo1 para cada w em V (G) faça yw ←∞2 yr ← 0
3 enquanto o potencial y não é viável faça4 escolha vw em E(G) tal que yv + cvw < yw vw está tenso5 yw ← yv + cvw relaxação de vw6 p(w)← v
7 devolva y e p
2.4 Algoritmo de Ford-Bellman
FORDBELLMAN (G, c, r)
1 para cada w em V (G) faça yw ←∞2 yr ← 0
3 repita |V (G)| − 1 vezes4 para cada arco vw em E(G) faça5 se yv + cvw < yw vw está tenso6 então yw ← yv + cvw relaxação de vw7 p(w)← v
8 devolva y e p
2.5 Dicircuitos negativos
2.6 Programas lineares
maximize ys − yrsob as restrições
yw − yv ≤ cvw para cada vw em E(G) .(1)
Pl dual:
FEOFILOFF CAMINHOS DIRIGIDOS DE CUSTO MíNIMO 15
minimize∑
(cexe : e ∈ E(G))
sob as restriçõesx+(r)− x−(r) = −1
x+(v)− x−(v) = 0 para cada v em V (G) r r, sx+(s)− x−(s) = +1
xe ≥ 0 para cada e em E(G)
(2)
sendo x+(v) :=∑
(xuv : uv ∈ E(G)) e x−(v) :=∑
(xvw : vw ∈ E(G)).
2.7 Algoritmo especial para redes acíclicas
FORDBELLMANDAG (G, c, (v1, . . . , vn))
1 para cada w em V (G) faça yw ←∞2 yv1 ← 0
3 para i← 1 até n− 1 faça4 para cada vw em ∂−(vi) faça5 se yv + cvw < yw6 então yw ← yv + cvw7 p(w)← v
8 devolva y e p
2.8 Algoritmo especial para custos não-negativos
DIJKSTRA (G, c, r) c ≥ 0
01 para cada w em V (G) faça yw ←∞02 yr ← 0
03 Q← V (G) r r04 enquanto Q 6= ∅ faça05 escolha v em Q tal que yv é mínimo06 Q← Qr v07 para cada vw em ∂−(v) faça08 se yv + cvw < yw vw está tenso09 então yw ← yv + cvw relaxação de vw10 p(w)← v
11 devolva p e y
2.9 Custos unitários e busca em largura
BUSCAEMLARGURA (G, r)
16 CAMINHOS DIRIGIDOS DE CUSTO MíNIMO FEOFILOFF
01 para cada w em V (G) faça yw ←∞02 yr ← 0
03 Q← INICIALIZAFILA (r)
04 enquanto FILANÃOVAZIA (Q) faça05 v ← TIRADAFILA (Q)
06 para cada vw em ∂−(v) faça07 se yv + cvw < yw vw está tenso08 então yw ← yv + cvw relaxação de vw09 p(w)← v
10 PÕENAFILA (Q,w)
11 devolva p e y
Capítulo 3
Fluxo máximo e corte mínimo
O problema do fluxo máximo entre dois nós de uma rede com restrições de capacidadenos arcos é um modelo fundamental em otimização combinatória.
O que é um fluxo máximo? Devagar! Primeiro é preciso entender o que é um fluxo.
Por que misturar fluxo máximo e corte mínimo na mesma sentença? Boa pergunta.Como veremos adiante, há uma relação fundamental entre os dois conceitos. A relaçãoé a mesma que existe entre um programa linear e o seu dual.
3.1 Fluxos
O que é um fluxo? Um fluxo é qualquer função que atribui números racionais não-negativos aos arcos de um digrafo. Se G é o digrafo em questão, podemos dizer queum fluxo é uma função de E(G) em Q+.
O “não-negativos” é importante na resposta anterior? Sim. Não queremos que ovalor do fluxo em um arco seja negativo.
Um fluxo não deveria deve satisfazer “restrições de conservação” em cada nó? Não.Nestas notas, qualquer função que atribui números racionais não-negativos aos arcos dodigrafo é um fluxo.
A “quantidade” total de fluxo que entra em um nó é um conceito importante? Sim.Precisamos inventar uma notação para o conceito. Se x é um fluxo num digrafo e v éum nó, denotamos por x+(v) a soma dos valores de x nos arcos que entram em v e porx−(v) a soma dos valores de x nos arcos que saem de v. De um modo mais geral, se Ré um conjunto de nós do digrafo, denotamos por x+(R) a “quantidade” de fluxo que
17
18 FLUXO MÁXIMO E CORTE MíNIMO FEOFILOFF
entra em R, ou seja,x+(R) :=
∑(xe : e ∈ ∂+(R)) .
Analogamente, x−(R) :=∑
(xe : e ∈ ∂−(R)). É claro que x−(R) = x+(R), sendo R ocomplemento de R, isto é, o conjunto V rR, onde V é o conjunto de nós do digrafo.1
Qual a relação entre o fluxo que entra e o fluxo que sai? Não há relação. O que entraem um conjunto R de nós pode ser maior ou menor que o que sai. Se x é um fluxo, oexcesso, ou acúmulo, ou saldo (= net flow) de x em R é a “quantidade” de fluxo que fica“retida” em R. O excesso é denotado por x+
−(R):
x+
−(R) := x+(R) − x−(R) .
O número x+−(R) é muito mais importante que x+(R) e x−(R), podendo ser positivo,
negativo ou nulo.
Minha intuição diz que o excesso em R é igual à soma dos excessos nos nós de R.Intuição correta. Esse fato é conhecido como “propriedade da soma dos excessos”:
Para qualquer fluxo x em um digrafo G e qualquer subconjunto R de V (G),∑(x+
−(v) : v ∈ R) = x+−(R).
PROVA: Queremos mostrar que∑
v∈R x+(v)−
∑v∈R x
−(v) = x+(R)− x−(R). Para isso,basta verificar que cada arco do digrafo dá a mesma contribuição para o lado esquerdoe o direito dessa igualdade. Um arco ij que tem ambas as pontas em R contribui xijpara o primeiro somatório e xij para o segundo somatório, e portanto a contribuiçãototal 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 ambasas pontas em R. Um arco que entra em R contribui apenas para o primeiro somatóriodo lado esquerdo e para o primeiro termo do lado direito. Analogamente, um arcoque sai deR contribui apenas para o segundo somatório do lado esquerdo e o segundotermo do lado direito.
O que é um fluxo de um nó a outro nó? Seja x é um fluxo e (r, s) um par de nós.Dizemos que x é um fluxo de r a s se satisfaz duas condições:
1. x+−(v) = 0 para todo nó v exceto r e s e
2. x+−(s) ≥ 0.
Este capítulo trata (quase) exclusivamente de fluxos de r a s. Note que um fluxo de r as é orientado: ele “começa” em r e “termina” em s. Um fluxo de r a s não tem relaçãoalguma com um fluxo de s a r.
1 Para justificar os superscritos “+” e “−”, você pode imaginar que os nós são contas bancárias e osarcos representam movimentação de dinheiro: tudo que entra numa conta é somado ao saldo e tudoque sai é subtraído.
FEOFILOFF FLUXO MÁXIMO E CORTE MíNIMO 19
É verdade que x+−(r) é igual a x+
−(s)? Quase. Se x é um fluxo de r a s então x+−(r) =
−x+−(s). Isso decorre da propriedade da soma de excessos. Portanto, x+
−(r) ≤ 0, x+−(s) ≥
0 e |x+−(r)| = |x+
−(s)|.
Por que não exigir x+(r) = 0 e x−(s) = 0 na definição de fluxo? Parece atraente, masnão é uma boa ideia. Isso tornaria a manipulação de fluxos mais suja e difícil.
Como se define o “tamanho” ou “força” de um fluxo? A palavra certa é intensidade.A intensidade de um fluxo x de r a s é o excesso de x em s. É conveniente denotara intensidade de x por int(x). (Mas “int” não é abreviatura e “inteiro”!) Portanto,int(x) := x+
−(s).
Então nossa missão é encontrar um fluxo de intensidade máxima? Não. Isso nãofaz sentido, pois existem fluxos de r a s de intensidade tão grande quanto se queira.Antes de falar máximo, é preciso introduzir o conceito de capacidade.
3.2 Capacidades e o problema do fluxo máximo
O que é a capacidade de um arco? Uma função-capacidade para um digrafo G é qual-quer função que leva E(G) em Q+ ∪ ∞. A função-capacidade será denotada por u.2
O número ue que a função u atribui a um arco e é a capacidade do arco. (Você podeimaginar que e é uma rodovia e ue é a largura, ou o número de pistas, de e.)
Por que permitir capacidades infinitas? Não haveria grande prejuízo se disséssemosque u leva E(G) em Q+. Mas é mais cômodo permitir∞.
O que é uma rede capacitada? Uma rede capacitada é um par (G, u) em que G é umdigrafo e u é uma função-capacidade.
Qual é, então, o problema do fluxo máximo? Eis o problema, em toda a sua glória:
Dados nós r e s de uma rede capacitada (G, u), encontrar um fluxo x de r a s, deintensidade máxima, tal que x ≤ u.
Dizer “x ≤ u” é o mesmo que dizer “xe ≤ ue para cada arco e.” Dizemos que um fluxocom esse propriedade respeita u. Para simplificar ainda mais, dizemos que um fluxo éviável se vai de r a s e respeita u. Dizemos também que (G, u, r, s) é uma rede de fluxo(= flow network).
2 A letra “u” é a inicial de upper bound.
20 FLUXO MÁXIMO E CORTE MíNIMO FEOFILOFF
O que é um “fluxo máximo”? A expressão “fluxo máximo” é uma abreviatura de“fluxo viável de intensidade máxima”.
Toda instância do problema tem solução? Excelente pergunta. A primeira parte daresposta é positiva: para qualquer rede de fluxo (G, u, r, s), existe um fluxo viável(o fluxo nulo, por exemplo). Mas a segunda parte da resposta é negativa: existemredes de fluxo (G, u, r, s) que têm fluxos viáveis de intensidade arbitrariamente grande.(Considere, por exemplo, uma instância em que há um dicaminho de r a s de capaci-dade infinita.)
3.3 Fluxos versus dicaminhos
Podemos entender um fluxo como uma coleção de dicaminhos? Basicamente, sim.Suponha que P1, . . . , Pk é uma família de dicaminhos simples de r a s no digrafo. Paracada arco e do digrafo, seja xe o número de dicaminhos que contêm o arco e. Entãox é um fluxo de r a s e int(x) = k. Reciprocamente, todo fluxo de r a s pode serrepresentado por uma família de dicaminhos simples:
Para todo fluxo x de r a s em um digrafo, existem dicaminhos simples P1, . . . , Pk
de r a s e números positivos β1, . . . , βk tais que∑
(βi : Pi 3 e) ≤ xe para cadaarco e e β1 + · · ·+ βk = int(x).
ESBOÇO DA PROVA: Em cada iteração, escolha um dicaminho P tal que xe > 0 paracada arco e de P . Calcule β := min (xe : e ∈ P ). Agora subtraia β de xe para cada arcoe de P . Depois dessa operação, x continua sendo um fluxo de r a s. Repita o processoenquanto isso for possível.
Não podemos garantir que∑
(βi : Pi 3 e) seja igual a xe porque o fluxo pode “conter”dicircuitos.
O processo de decomposição do fluxo em dicaminhos pode produzir um fluxo má-ximo? Vamos tentar. Cada iteração começa com um fluxo viável x. Em cada iteração,encontre um dicaminho simples P de r a s tal que xe < ue em cada arco e; seja ε omínimo de ue − xe para e ∈ P ; some ε a xe para todo e em P ; comece nova iteração.
Esse processo produz um fluxo viável. Infelizmente, o fluxo não é máximo em geral.(Encontre um exemplo!)
3.4 Algoritmo de Ford-Fulkerson
É possível aperfeiçoar a tentativa de algoritmo da seção anterior? Sim. Para come-çar, troque o dicaminho P por um caminho. É claro que os arcos inversos do caminhodeverão ter um tratamento diferenciado.
FEOFILOFF FLUXO MÁXIMO E CORTE MíNIMO 21
Para qualquer caminho P , seja E(P ) o conjunto dos arcos diretos de P e E(P ) o con-junto dos arcos inversos. Um caminho P é de incremento se xe < ue para cada e ∈ E(P )
e xe > 0 para cada e ∈ E(P ), ou seja, os arcos diretos de P não estão cheios de fluxoe os inversos não estão vazios. Um caminho de incremento que vai r a s merece otítulo de caminho aumentador (= augmenting path). (É claro que esses conceitos só fazemsentido no contexto de um fluxo viável x.)
Se “acrescentarmos” um caminho aumentador ao fluxo, a intensidade do fluxo au-menta? Sim. Digamos que a largura de um caminho aumentador P é o maior númeroε tal que xe+ε ≤ ue para cada e em E(P ) e xe−ε ≥ 0 para cada e em E(P ). A operaçãode envio de ε unidades de fluxo ao longo de P consiste em fazer
xe ← xe + ε para cada e em E(P ) e xe ← xe − ε para cada e em E(P ).
Essa operação produz um novo fluxo viável. A intensidade do novo fluxo é int(x) + ε.
A largura de um caminho aumentador pode ser infinita? De fato, podemos ter ε =
∞. Isso acontece se E(P ) = ∅ e ue =∞ para todo e em E(P ). Se isso acontece, o fluxox pode aumentar sem limite e portanto essa instância do problema do fluxo máximonão tem solução.
É esse, então, o célebre algoritmo de Ford e Fulkerson? Sim. O algoritmo recebeuma rede de fluxo (G, u, r, s) e devolve um fluxo máximo (ou constata que a rede nãotem fluxo máximo). O algoritmo foi descoberto (em 1956) por Ford e Fulkerson e porKotzig.
FORDFULKERSON (G, u, r, s)
01 x← 0
02 repita03 R← CAMINHOSINCR (G, u, r, x)
04 se s /∈ R05 então devolva x e pare problema resolvido06 P ← CAMINHOAUM (G, u, r, x)
07 ε1 ← min (ue − xe : e ∈ E(P ))
08 ε2 ← min (xe : e ∈ E(P ))
09 ε← min (ε1, ε2)
10 se ε =∞11 então pare problema ilimitado12 x← ENVIAFLUXO (G, x, P, ε)
A rotina CAMINHOSINCR (G, u, r, x) devolve o conjunto dos términos de todos os ca-minhos de incremento que começam em r. A rotina CAMINHOAUM (G, u, r, x) produzum caminho aumentador para x (supondo que um tal corte existe). Na linha 12, arotina ENVIAFLUXO (G, x, P, ε) envia ε unidades de fluxo ao longo do caminho P edevolve o fluxo resultante.
22 FLUXO MÁXIMO E CORTE MíNIMO FEOFILOFF
O fluxo produzido pelo algoritmo tem intensidade máxima? Excelente pergunta.É fácil ver que no começo de cada iteração x é um fluxo viável. Mas não é nada óbvioque a intensidade de x é máxima na linha 05. Para mostrar a maximalidade, precisamosentender a relação entre fluxos e cortes.
Exercícios
3.1 Descreva a rotina ENVIAFLUXO em código.
3.2 Árvores divergentes. Aplique o algoritmo de Ford-Fulkerson a uma rede de fluxo (G, u, r, s) em queG é uma árvore divergente (veja a seção 1.1).
3.5 Fluxos versus cortes
Os cortes relevantes são os que separam r de s? Certo. Conforme a seção 1.1, umcorte ∂−(R) separa r de s (dizemos também que está entre r e s) se r ∈ R e s ∈ R. Noteque ∂−(R) consiste dos arcos que vão deR paraR e não inclui arcos que vão na direçãocontrária.
Qual a relação entre cortes e fluxos? Para qualquer fluxo x de r a s e qualquer corte∂−(R) que separa r de s, tem-se int(x) = −x+
−(R). (Prove essa relação. Ela decorre dapropriedade da soma de excessos discutida na seção 3.1, página 18.)
Como veremos a seguir, há uma relação mais importante, que envolve a capacidadedos cortes.
O que é a capacidade de um corte? A capacidade de um corte ∂−(R) é a soma dascapacidades dos arcos que saem de R, ou seja,
∑(ue : e ∈ ∂−(R)). Esse número é
denotado por u−(R). A capacidade de um corte C também pode ser denotada porcap(C). Portanto,
cap(C) := u−(R),
sendo R a margem negativa de C.
Qual a relação entre intensidade de fluxos e capacidade de cortes? A capacidade decada corte entre r e s limita a intensidade de qualquer fluxo viável:
Para qualquer fluxo viável x e qualquer corte C entre r e s, int(x) ≤ cap(C).
(Prove essa cota superior. A prova é elementar, ou seja, segue imediatamente dasdefinições, sem qualquer argumentação sofisticada.)
Então, basta exibir um corte pequeno para provar que um fluxo é máximo? Exata-mente. Para mostrar que um fluxo viável x é máximo, basta exibir um corte C entre re s tal que cap(C) = int(x).
FEOFILOFF FLUXO MÁXIMO E CORTE MíNIMO 23
Podemos usar essa observação para provar que o algoritmo de Ford-Fulkerson estácorreto? Suponha que a execução do algoritmo termina na linha 05. Então s /∈ R eportanto R separa r de s. A definição de R na linha 03 garante que xe = ue para cada eem ∂−(R) e xe = 0 para cada e em ∂+(R). Portanto,
x−(R) = u−(R) e x+(R) = 0 .
Segue daí que int(x) = −x+−(R) = x−(R)− x+(R) = u−(R). Logo, int(x) = cap(∂−(R)).
Essa igualdade prova que x tem intensidade máxima!
O próprio algoritmo fornece a prova de que produziu o resultado correto? Exata-mente! O conjunto R na linha 05 de FORDFULKERSON é a margem de um corte queprova a maximalidade de int(x). Além disso, na linha 11, temos implicitamente umdicaminho de r a s cujos arcos têm capacidade infinita, e isso prova que não existefluxo viável máximo na rede dada. Algumas pessoas dizem que algoritmos como esse,que provam sua própria correção, são “robustos”.
Não deveríamos colocar essa informações na documentação do algoritmo? Tem ra-zão. O algoritmo de Ford-Fulkerson recebe (G, u, r, s) e devolve (1) um fluxo viável x eum corte C entre r e s tal que int(x) = cap(C) ou (2) um dicaminho de r a s cujos arcostêm capacidade infinita.
Quantas iterações o algoritmo de Ford-Fulkerson faz? Excelente pergunta. Seue < ∞ para todo arco e, e portanto ue ∈ Q+ para todo e, a execução do algoritmotermina depois de um número finito de iterações. (Prove esse fato. Veja o exercício 3.6.)O número de iterações pode depender dos valores de u, e portanto o algoritmo épseudopolinomial. (Se u tivesse valores irracionais, o número de iterações poderiaser infinito ou o algoritmo poderia produzir resultados errados.)
O algoritmo de Ford-Fulkerson também calcula um corte mínimo? Sim. Se a exe-cução do algoritmo termina na linha 05 então o corte ∂−(R) tem capacidade mínimadentre todos os cortes que separam r de s.
O que é o famoso teorema MFMC? A sigla é formada pelas iniciais de “Max-FlowMin-Cut”. O teorema resume os efeitos do algoritmo de Ford e Fulkerson:
TEOREMA MFMC: Em qualquer rede de fluxo (G, u, r, s), se existe um fluxo viá-vel máximo então maxx int(x) = minC cap(C) , sendo maxx tomado sobre todosos fluxos viáveis x e minC tomado sobre todos os cortes C que separam r de s.
A condição “se existe um fluxo viável máximo” poderia ser eliminada se aceitássemoscomo válido um fluxo de intensidade infinita e um corte de capacidade infinita.
24 FLUXO MÁXIMO E CORTE MíNIMO FEOFILOFF
Exercícios
3.3 Encontre um fluxo máximo e um corte mínimo entre r e s na rede da figura. [CCPS 3.2]
3.4 A matriz abaixo dá as capacidades dos arcos de uma rede de fluxo. (Faça uma boa figura). En-contre, iterativamente, um fluxo viável máximo. Exiba o fluxo no início de cada iteração. Mostreum corte entre r e s que tenha capacidade mínima. [AMO 6.14]
r a b c d e sr − 4 3 − − − −a 4 − − 2 3 − −b 3 − − 2 − − −c − 2 2 − − 5 −d − 3 − − − 4 −e − − − 5 4 − 8s − − − − − 8 −
3.5 Seja G o digrafo definido pela matriz de adjacências abaixo. (Faça uma boa figura). Encontre umacoleção disjunta máxima de dicaminhos simples de r a s. Faça uma lista de todos os cortes entrer e s. [AMO 6.15]
r t u v w s
r − 1 1 1 − −t − − 1 − − −u − − − 1 − 1v − − − − 1 1w − − − − − 1s − − − − − −
3.6 ? Capacidades inteiras. Aplique o algoritmo de Ford-Fulkerson a uma rede (G, u, r, s) em que afunção-capacidade u é inteira. Supondo que um fluxo máximo tem intensidade K < ∞, mostreque o algoritmo executa no máximoK iterações. Deduza daí que se u for racional então o númerode iterações é finito.
3.6 Versão Edmonds-Karp do algoritmo
Por que o algoritmo de Ford-Fulkerson é tão lento? A seção anterior sugere quealgoritmo FORDFULKERSON pode ser muito lento. De fato, o consumo de tempo podeaumentar linearmente com o número max (ue : e ∈ E(G)). Ou seja, multiplicar todasas capacidades por 100 pode multiplicar o consumo de tempo por 100. Isso aconteceporque FORDFULKERSON permite escolher qualquer caminho de aumento quando hámais de um.
FEOFILOFF FLUXO MÁXIMO E CORTE MíNIMO 25
Existe um bom critério de escolha dos caminhos de aumento? Sim. Uma ideia natu-ral e intuitiva é usar apenas caminhos de aumento de comprimento (número de arcos)mínimo. Dinits e Edmonds e Karp mostraram (1972) que esse aperfeiçoamento faz comque o algoritmo execute no máximo nm iterações, sendo n o número de nós e m onúmero de arcos do digrafo.
TEOREMA DE EDMONDS E KARP: Se cada iteração do algoritmo de Ford-Fulkerson usar um caminho de aumento de comprimento mínimo, o algoritmonão fará mais que nm iterações.
Como se demonstra o teorema de Edmonds e Karp? A prova é elementar mas não éóbvia.
Como procurar por caminhos de aumento de comprimento mínimo? Basta integraros códigos das rotinas CAMINHOSINCR e CAMINHOAUM e implementá-las usandouma variante da busca em largura (seção 2.9, página 15). Essa adaptação exige atençãopois deve procurar por caminhos não-dirigidos, enquanto a versão original procuradicaminhos. Para fazer isso, podemos usar um digrafo auxiliar (V (G), E ′) definidoassim: vw ∈ E ′ se e somente se vw ∈ E(G) e xvw < uvw ou wv ∈ E(G) e xwv > 0.(Nessa expressão lógica, o “e” tem precedência sobre o “ou”.) Os dicaminhos nessedigrafo auxiliar correspondem aos caminhos de incremento no digrafo original.
Quanto tempo a versão Edmonds-Karp consome? Cada iteração do algoritmo con-some tempo O(m). Como o número de iterações da versão Edmonds-Karp não passade nm, o algoritmo todo consome
O(nm2)
unidades de tempo. Como essa delimitação não depende das capacidades u, podemosdizer que o algoritmo é fortemente polinomial.
3.7 Programas lineares
O problema do fluxo máximo pode ser formulado como um programa linear? Fácil.Dada uma rede de fluxo (G, u, r, s), encontrar um vetor (xe : e ∈ E) que
maximize x+−(s) sob as restrições
x+−(v) = 0 para cada v em V r r, sxe ≤ ue para cada e em E
xe ≥ 0 para cada e em E,
(1)
sendo V := V (G) e E := E(G).
Qual o dual desse pl? O dual desse pl é um tanto feito, pois trata em separado dosnós r e s.
26 FLUXO MÁXIMO E CORTE MíNIMO FEOFILOFF
É possível reformular o pl de modo que seu dual seja mais bonito? A seguinteformulação alternativa do problema é mais apropriada: dada uma rede capacitada(G, u) e um arco sr de capacidade∞, encontrar uma circulação x que respeite u e ma-ximize xsr. Essa forma do problema pode ser apresentada como o seguinte programalinear: encontrar um vetor x que
maximize xsr sob as restriçõesx+
−(v) = 0 para cada v em V
xe ≤ ue para cada e em E
xe ≥ 0 para cada e em E.
(2)
Qual o dual desse pl? Antes de escrever o dual, convém escrever o pl em notaçãomatricial. Para isso, introduzimos um vetor (ce : e ∈ E) tal que csr = 1 e ce = 0 paratodos os demais arcos. O pl pode então ser escrito assim: maximize cx sujeito a
Ax = bIx ≤ ux ≥ 0
(3)
sendo I a matriz identidade indexada por E × E e b o vetor nulo indexado por V .O dual desse pl consiste em minimizar yb+ zu sujeito a
yA+ zI ≥ cz ≥ 0 .
(4)
Como fica o pl (4) quando escrito por extenso? Fica assim:
minimize∑
(ueze : e ∈ E) sob as restrições−yv + yw + zvw ≥ 0 para vw ∈ E r sr−ys + yr + zsr ≥ 1
ze ≥ 0 para e ∈ E.
(5)
O pl (5) descreve o problema do corte mínimo? Exatamente! Se ∂−(R) é um corteque separa r de s então o par de vetores (y, z) definido a seguir é uma solução viáveldo pl (5):
yv = 1 para cada v em R,yv = 0 para cada v em R,ze = 1 para cada e em ∂−(R),ze = 0 para cada e em E r ∂−(R).
Reciprocamente qualquer solução viável (y, z) de (5) que tem valores em 0, 1 des-creve um corte que separa r de s.
FEOFILOFF FLUXO MÁXIMO E CORTE MíNIMO 27
Outro programa linear
A decomposição do fluxo em dicaminhos não leva a um pl mais simples que (1)?Talvez (veja a decomposição de fluxo em dicaminhos na seção 3.3). Se P o conjunto detodos os dicaminhos simples de r a s no digrafo, o problema do fluxo máximo podeser formulado assim: encontrar um vetor (wP : P ∈ P) que
maximize∑
(wP : P ∈ P) sujeito a∑(wP : e ∈ P ∈ P) ≤ ue para cada e ∈ E
wP ≥ 0 para cada P ∈ P .(6)
O número de variáveis é enorme, pois |P| pode aumentar exponencialmente com onúmero de nós. Ainda assim, o pl é conceitualmente muito interessante. O dual do plconsiste em encontrar um vetor (ze : e ∈ E) que
minimize∑
(zeue : e ∈ E) sujeito a∑(ze : e ∈ P ) ≥ 1 para cada P ∈ P
ze ≥ 0 para cada e ∈ E.(7)
(Em outras palavras, trata-se de atribuir pesos não-negativos z aos arcos de modo quecada dicaminho de r a s esteja “coberto”.) Se z é o vetor característico de um corte∂−(R) entre r e s então é claro que z é solução viável de (7).
Exercícios
3.7 Escreva o dual do pl (1). Prove que sua resposta está correta.
3.8 Verifique que o pl (3) é o dual o pl (4). Reciprocamente, verifique que (4) é dual de (3).
3.9 Mostre que qualquer corte entre r e s corresponde a uma solução viável (y, z) do pl (5) e que ovalor uz da solução viável (y, z) é igual à capacidade do corte. Mostre ainda que qualquer cortemínimo entre r e s define uma solução ótima do pl (5). (Sugestão: use o teorema MFMC paraobter uma solução ótima do pl (2).)
3.10 ? Capacidades infinitas. A rigor, o pl (2) só está correto se ue <∞ para todo arco e. Quando ue =∞(em particular, quando e = sr), a restrição xe ≤ ue deveria ser ignorada, fazendo desaparecer acomponente ze de z. Reescreva o pl de forma correta. Como fica o dual? Escreva as condições defolgas complementares para o par dual de programas lineares.
3.11 Prove que o pl (7) é o dual do pl (6). Reciprocamente, prove que (6) é dual de (7).
28 FLUXO MÁXIMO E CORTE MíNIMO FEOFILOFF
Bibliografia
[AMO93] R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory, Algorithmsand Applications. Prentice Hall, 1993. i
[CCPS98] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver. Combina-torial Optimization. John Wiley, 1998. i
[Chv83] V. Chvátal. Linear Programming. W.H. Freeman, 1983. 8
[CLRS01] T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algo-rithms. MIT Press and McGraw-Hill, second edition, 2001. i
[Sch03] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer,2003. i
29
Índice
?, iyTA, 8cTx, 7δ(·), 5∂+(·), 4∂−(·), 5P ·Q, 3R, 4G− v, 2G− e, 2G+ ij, 2Ω(·), 11Θ(·), 11
acúmulo de fluxo, 18alcance, 3algoritmo
de busca em largura, 15de Dijkstra, 15de Ford, 14de Ford-Bellman, 14de Ford-Bellman para DAGs, 15de Ford-Fulkerson, 21do dicaminho mínimo, 14do fluxo
máximo, 21polinomial, 11Simplex, 8
AMO, iao alcance, 3arborescência, 4arco, 1
antiparalelo, 2direto, 2inverso, 2justo, 13paralelo, 1que entra, 1que sai, 1relaxado, 13tenso, 13
aresta, 5
paralela, 1árvore, 4
dirigida, 4divergente, 4não-dirigida, 6
assintótica, 11
binário, 6, 12bipartição, 4bipartido, 4booleano, 12
c, 13caminho, 2
aumentador, 21de incremento, 21dirigido, 3simples, 3vai de r a s, 3
cap(·), 22capacidade
de arco, 19de corte, 22
CCPS, icircuito, 3
dirigido, 4ímpar, 4
CLRS, icomplexidade de algoritmos, 10componente
conexa, 3comprimento de caminho, 3concatenação de caminhos, 3condições de otimalidade
de fluxo máximo, 23corte, 5
entre dois nós, 22separa dois nós, 22
custode arco, 13
δ(·), 5∂+(·), 4
30
FEOFILOFF ÍNDICE 31
∂−(·), 5DAG, 4dicaminho, 3
simples, 3dicircuito, 4digrafo, 1
acíclico, 4bipartido, 4conexo, 3fortemente conexo, 3induzido, 2simétrico, 2
Dinits, 25dipath, 3dualidade
teorema forte, 8teorema fraco, 8
E(·), 1edge, 1Edmonds, 25excesso de fluxo, 18
feasible, 7floresta, 4
dirigida, 4fluxo, 17
de r a s, 18máximo, 20respeita capacidade, 19viável, 19
folgas complementares, 9fonte, 5Ford, 21forest, 4fortemente
polinomial, 11fortemente conexo, 3Fulkerson, 21função, 12
-capacidade, 19-custo, 13
grafo, 6bipartido, 6
completo, 11conexo, 3dirigido, 1induzido, 2não-dirigido, 5
grau, 6
de entrada, 5de saída, 5
ilimitado, 7indegree, 5int(·), 19intensidade de fluxo, 19
Karp, 25Kotzig, 21
largurade caminho aumentador, 21
m, 2margem
de corte, 5negativa, 5positiva, 5
matrizbinária, 12booleana, 12de adjacências, 2, 6de incidência, 2, 6
MFMC, 23
n, 2não-negativo, 11não-positivo, 11negativo, 11network, 5nó, 1notação assintótica, 11
O(·), 11origem de caminho, 2outdegree, 5overload, 12
partição, 4pl, 7
ilimitado, 7inviável, 7viável, 7
polinomial, 11fortemente, 11pseudo-, 11
pontade aresta, 5final, 1inicial, 1
positivo, 11
32 ÍNDICE FEOFILOFF
potencial, 13viável, 14
problemado dicaminho mínimo, 13do fluxo máximo, 19
programa linear, 6dual, 8ilimitado, 7inteiro, 10inviável, 7viável, 7
pseudopolinomial, 11
Q, 12Q+, 12QV , 12
R, 12R+, 12raiz
de arborescência, 4rede, 5
capacitada, 19de fluxo, 19
relaxaçãolinear, 10
respeita capacidade, 19
saldo de fluxo, 18Sch03, isimétrico, 2Simplex, 8sink, 5solução, 7
ótima, 7viável, 7
sorvedouro, 5source, 5spanning subdigraph, 2subdigrafo, 2
gerador, 2induzido, 2
subgrafo, 6
teoremada dualidade, 8das folgas complementares, 9de Edmonds-Karp, 25forte da dualidade, 8fraco da dualidade, 8
teoria dos grafos, 1
término de caminho, 3tree, 4
u−(·), 22u+(·), 22
V (·), 1valor de fluxo, 19valor ótimo de pl, 7vértice, 1vetor, 12
binário, 12booleano, 12característico, 12inteiro, 12
viável, 19
x−(·), 18x+(·), 17x+
−(·), 18
Z, 12Z+, 12
