Seja $A$ a matriz e $x$ o vetor abaixo. Quanto vale $Ax$?
Mostre um subconjunto linearmente independente maximal do conjunto de linhas da matriz abaixo. Mostre um segundo subconjunto l.i. maximal.
Seja $y$ um potencial viável numa rede $(D, c, r).$ Seja $P$ um caminho dirigido de $r$ a $s.$ Mostre que $c(P) = y_s - y_r$ se e somente se todos os arcos de $P$ estão justos.
Suponha que $y$ é um potencial viável numa rede $(D, c).$ Deduza do lema 1.1 das minhas notas de aula que a rede não tem ciclos dirigidos negativos.
Acrescente código ao algoritmo de Ford-Bellman para que ele devolva um ciclo dirigido negativo se tal existir.
Seja $A$ a matriz de incidências de um grafo dirigido. Sejam $r$ e $s$ dois nós do grafo. Seja $b$ o vetor definido por $b_r = -1,$ $b_s = +1$ e $b_v = 0$ para todo $v$ diferente de $r$ e de $s.$ Seja $X$ o poliedro $\conj{x \geq 0 : Ax = b}$.
Parte 1: Suponha que $X$ é vazio e prove que $s$ não está ao alcance de $r$ no grafo.
Parte 2: Você acha que a recíproca é verdadeira? Dê uma justificativa informal para sua resposta.
Mostre todos os caminhos dirigidos mínimos a partir do nó $r.$ Mostre um potencial viável que prove a minimalidade dos caminhos.
Suponha dadas tarefas $T_1,\ldots,T_n$. A execução de cada tarefa $T_i$ exige um tempo $t_i.$ Para certos pares $(i,j),$ a execução de $T_i$ deve preceder a execução de $T_j$ (ou seja, o processamento de $T_j$ só pode começar depois que o processamento de $T_i$ tiver terminado). Queremos planejar a execução das tarefas de modo que as restrições de precedência sejam respeitadas e cada tarefa seja concluída tão cedo quanto possível. (Note que várias tarefas podem ser executadas ao mesmo tempo.)
Reduza esse problema ao cálculo de um potencial viável máximo em um DAG.
Sejam $r$ e $s$ dois nós de um grafo dirigido. Dizemos que um corte dirigido separa $s$ de $r$ se existe um conjunto $S$ de nós tal que $s \in S,$ $r \notin S$ e $\cutin(S)$ é vazio.
Mostre que um corte dirigido separa $s$ de $r$ se e somente se não existe caminho dirigido de $r$ a $s.$
Considere a rede com custos representada na figura. Exiba um potencial viável $y$ que maximize a $y_i - y_1$ para cada nó $i.$ Prove que sua resposta está correta.
Seja $(D, u)$ uma rede capacitada. Seja $x$ é um fluxo de $r$ a $s$ que respeita a capacidade $u$ e $C$ um corte que separa $r$ de $s.$ Prove que $\intens(x) \leq \capac(C).$
Parte 1: Encontre um fluxo de $s$ a $t$ que respeite as capacidades e tenha intensidade máxima. Prove que o fluxo é máximo.
Parte 2: Mostre um fluxo $x'$ que tenha intensidade um pouco menor que a máxima. Em seguida, mostre um caminho de aumento para $x'$.
Exiba um fluxo $x$ de $s$ a $t$ que respeite as capacidades, tenha intensidade máxima, mas não seja vetor extremo do poliedro. Explique cuidadosamente por que $x$ não é extremo.
Encontre um emparelhamento máximo e uma cobertura mínima no grafo da figura. Faça isso por redução ao problema do fluxo máximo e corte mínimo. Faça figuras para mostrar como você resolveu o problema.
Encontre um emparelhamento máximo e uma cobertura mínima no grafo da figura.
Suponha dado um grafo não-dirigido e um custo $c_e$ para cada aresta $e$ do grafo. Queremos encontrar um emparelhamento de custo máximo.
Parte 1: Formule o problema como um pl e calcule o seu dual.
Parte 2: Descreva o dual como um problema sobre uma rede.
Prove que as condições de Gale são necessárias.
Deduza o teorema MFMC 2.9 do teorema de Gale 3.7 e do lema 3.6.
Mostre que as condições de Gale são equivalentes às seguintes: $-\uout(X) \leq b(X) \leq \uin(X)$ para todo $X \subseteq V.$
Seja $b$ uma função-demanda em um grafo dirigido $D:=(V,E).$ Mostre que a rede $(D,b)$ tem um fluxo que satisfaz $b$ se e somente se $b(V) = 0$ e $b(X)\leq 0$ para todo $X\subseteq V$ tal que $\cutin(X)=\emptyset.$
Encontre um fluxo viável na rede $(D,b,u)$ descrita a seguir. Os nós são $r \ a \ b \ c \ d \ s$ e as tabelas definem as funções $b$ e $u$:
Suponha dado um conjunto $P$ de transmissores e um conjunto $Q$ de receptores. Para cada $v$ em $P\cup Q,$ é dado um inteiro não-negativo $d_v.$ Queremos estender fios ligando transmissores a receptores de modo a obedecer as seguintes regras:
É possível fazer isso? Mostre que as seguintes condições são necessárias e suficientes para que o problema tenha solução: $d(P)=d(Q)$ e \[ d(B) \leq d(A) + |E(P\setm A,B)| \] para todo $A\subseteq P$ e todo $B\subseteq Q.$ Estamos usando a seguinte notação: para qualquer $A'\subseteq P$ e qualquer $B'\subseteq Q,$ a expressão $E(A',B')$ representa o conjunto de todos os pares $ab$ com $a\in A'$ e $b\in B'.$
[Folgas complementares] Sejam $d,$ $x$ e $u$ vetores indexados por um conjunto $E.$ Suponha que $d\geq 0$ e $x\leq u.$ Prove que $dx = du$ se e somente se, para cada $i$ em $E,$ tem-se $d_i=0$ ou $x_i=u_i.$
Considere o pl (2), que é o dual do pl do fluxo viável de custo mínimo. Mostre que toda instância do pl (2) é viável. (Ou seja, exiba alguma solução viável $(y,z)$ do pl (2).)
Considere = olhe com atenção, refleta sobre, pense sobre
Considere ≠ suponha
[Custo versus custo reduzido.] Seja $(D,b,c)$ uma rede em que $b$ é uma função-demanda e $c$ é uma função-custo. Seja $x$ um fluxo que satisfaz $b$ e $y$ é um vetor arbitrário. Seja $\cbar$ o custo reduzido associado a $y.$ Mostre que $\cbar x = cx - yb.$
A figura mostra um fluxo viável $x$ numa rede $(D,b,u,c).$ Os número ao lado de cada arco $e$ são $c_e,u_e,x_e.$ O custo do fluxo é $cx=25.$ Encontre um ciclo de aumento. Calcule um fluxo viável de custo menor que o de $x.$
A figura representa uma árvore orientada com demandas nos nós. Calcule um fluxo que satisfaça as demandas. (Sugestão: resolva o problema de maneira simples e inocente.)
Atribuição de terminais a concentradores. Uma rede de teleprocessamento tem um grande número de terminais geograficamente dispersos e uma CPU. É dado um conjunto de concentradores, instalados em certos lugares, sendo cada um ligado à CPU por uma linha de grande capacidade e velocidade. Cada terminal precisa ser ligado à CPU. A ligação pode ser direta ou pode passar por um concentrador. Cada concentrador pode cuidar de no máximo $k$ terminais. Para cada terminal $i,$ o custo de uma ligação direta com a CPU é $c_{i}$ e o custo de uma ligação com um concentrador $j$ é $c_{ij}.$ (O custo da ligação de um concentrador à CPU é nulo.)
Queremos determinar a maneira mais barata de ligar os terminais à CPU. Formule esse problema como um problema de fluxo viável de custo mínimo.
Mostre que o problema do fluxo de intensidade máxima de um nó $r$ a um nó $s$ numa rede capacitada é um caso particular do problema do fluxo de custo mínimo. (Dica: acrescente arco $sr$ ao grafo.)
Rede residual.
Considere o exemplo 1 da seção 4.1 do meu livro
.
Faça uma figura da rede residual correspondente ao fluxo $x$.
Faça uma figura da rede residual correspondente ao fluxo $x'.$
Enuncie o problema do fluxo viável de custo máximo. Escreva o pl do problema. Escreva o pl dual (e verifique que o dual está correto).
Como podemos usar um algoritmo para o problema 4.A
do meu livro
para resolver o problema do fluxo viável de custo máximo?
Legenda: $c_e,u_e, x_e.$ Exiba um fluxo viável de custo mínimo e um potencial que prove a otimalidade do fluxo.
Considere o grafo capacitado da figura. Para cada par $(r,s)$ de nós, seja $M[r,s]$ é a capacidade de um corte $(r,s)$-mínimo. Exiba a matriz $M.$ Parte 2: Exiba um corte $(b,d)$-mínimo e prove a minimalidade do corte. Parte 3: Exiba um corte $(b,e)$-mínimo e prove a minimalidade do corte.
Considere o grafo capacitado $(G,u)$ da figura. Seja $X$ o conjunto $\conj{a,c,e}$ e $Y$ o conjunto $\conj{c,d}.$ Exiba os valores de $u(X),$ $u(Y),$ $u(X\cap Y)$ e $u(X\cup Y).$
Sejam $r$ e $s$ dois nós de um grafo capacitado $(G,u).$ Seja $\cut(X)$ um corte $(r,s)$-mínimo. Suponha que $X$ separa dois nós $p$ e $q.$ É verdade que $\cut(X)$ é um corte $(p,q)$-mínimo? (Dica: considere um ciclo $(r,s,p,q,r).$)
Seja $r$ um nó de uma árvore $T.$ Para cada aresta $e$ de $T,$ seja $X_e$ o conjunto de nós da componente conexa de $T-e$ que não contém $r.$ Mostre que a coleção $\conj{X_e : e\in E(T)}$ é laminar.
Sejam $r,$ $s,$ $p$ e $q$ quatro nós de uma rede capacitada $(G,u).$ Seja $\cut(X)$ um corte $(r,s)$-mínimo e $\cut(Y)$ um corte $(p,q)$-mínimo. Suponha que $X\cap Y$ separa $r$ de $s$ (ou $s$ de $r$) e que $X\cup Y$ separa $p$ de $q$ (ou $q$ de $p$). Prove que $\cut(X\cap Y)$ é um corte $(r,s)$-mínimo.
Seja $M$ um emparelhamento em um grafo $G.$ Use o método de prova do teorema de Berge para mostrar que há pelo menos $\nu(G)-|M|$ caminhos aumentadores sem nós em comum.
Suponha que um grafo $G$ consiste em um ciclo simples de comprimento $2k+1$ e nada mais. Mostre que $\min_{A\subseteq V(G)}\,(n - \oc(G{-}A) + |A|)/2 = k.$
Prove que o emparelhamento indicado na figura é máximo.
Exiba um emparelhamento com $7$ arestas no grafo da figura. Mostre que o emparelhamento é máximo.
Seja $G$ um grafo e $A$ um subconjunto de $V(G).$ Mostre que o número $\frac{1}{2}\,\big(n - \oc(G{-}A) + |A|\big)$ é inteiro.
Prove a restrição do teorema de Tutte--Berge 6.3 a árvores.
Prove o teorema de Tutte 6.4 a partir do teorema Tutte--Berge 6.3.
Mostre que uma árvore $T$ tem um ep
se e somente se $\oc(T-v)=1$ para cada nó $v.$
(Dica: Enuncie e prove as parte se
e somente se
em separado.)
Aplique o algoritmo EmpBipartidoPerfeito ao grafo com bipartição $(P,Q)$ representado pela matriz binária $P\times Q$ abaixo. (Use o gabarito de posição dos nós para fazer uma figura.)
Mostre que as folhas de toda árvore $M$-alternante são pretas (ou seja, estão a uma distância par da raiz $r$).
Aplique o algoritmo das flores ao grafo $G$ definido pela matriz de adjacências abaixo. (Use o gabarito de posição dos nós para fazer uma figura.)
a b c d e f g h i
a - 1 1 - - - - - -
b 1 - - 1 1 - - - -
c 1 - - - 1 - - 1 -
d - 1 - - - 1 1 1 -
e - 1 1 - - - - - -
f - - - 1 - - - 1 -
g - - - 1 - - - - 1
h - - 1 1 - 1 - - 1
i - - - - - - 1 1 -
b d
g
a e f
i
c h
Comece com o emparelhamento $M:=\conj{bd,ce,fh,gi}$ e a árvore $M$-alternante $T$ definida pelo conjunto de arestas \[ ab, ac, bd, ce, df, dg, fh, gi. \]
Faça uma figura no início de cada iteração. Mostre as cores dos nós e indique claramente as flores.
Na primeira iteração, acrescente a aresta $dh.$
Na segunda iteração, acrescente a aresta correspondente a $hi.$
Encontre um emparelhamento máximo a partir do emparelhamento indicado na figura. Encontre também um conjunto de nós que certifique a maximalidade do emparelhamento. Use o algoritmo EmpPerfeito (algoritmo de Edmonds, algoritmo das flores) repetidas vezes para resolver o problema.
Dica: Execute o algoritmo EmpPerfeito a partir da raiz $a.$ Depois execute o algoritmo a partir da raiz $p.$
Encontre um emparelhamento perfeito a partir do emparelhamento indicado na figura. (Execute o algoritmo EmpPerfeito de modo a obter flores, de preferência várias flores.)
Mostre que no fim da execução da linha 11
EmpBipartidoPerfeito
o grafo $G{-}A(T)$ tem mais que $|A(T)|$ nós isolados.
(Atenção:
A linha em questão é devolva $A$ e pare
.
O número da linha pode ter mudado no meu livro
.)
Seja $G$ um grafo bipartido com bipartição $(P,Q).$ Seja $M$ um emparelhamento em $G$ e $T$ uma árvore $M$-alternante com raiz em $P.$ Seja $A$ o conjunto dos nós brancos e $B$ o conjunto dos nós pretos. Mostre que $A\subseteq Q$ e $B\subseteq P.$ Suponha agora que $T$ é frustrada e mostre que $N(B)\subseteq A,$ sendo $N(B)$ o conjunto de todos os vizinhos de nós de $B.$
Deduza o teorema de König 3.3 do algoritmo que calcula um emparelhamento máximo num grafo bipartido. (Você pode supor que o nome do algoritmo é EmpBipartidoMaximo.)
Uma cobertura por arestas de um grafo $G$ é qualquer subconjunto $D$ de $E(G)$ que incide em cada nó de $G$ (ou seja, tal que cada nó é ponta de alguma aresta de $D).$ Mostre como uma cobertura por arestas mínima de um grafo sem nós isolados pode ser calculada a partir de um emparelhamento máximo. Prove que o tamanho de uma cobertura por arestas mínima é $n-\nu(G),$ sendo $n:=|V(G)|.$ (Cuidado: não confunda "$\nu$" com "$v$".)
Verifique que o dual do pl para o problema do emparelhamento de custo mínimo está correto. Prove também que a condição de folgas complementares está correta.
Seja $G$ um grafo completo com $n$ nós. Suponha que toda aresta tem custo $-10.$ Exiba um ep de custo mínimo. Exiba uma solução ótima $x$ do pl do ep mínimo e uma solução ótima $y$ do dual do pl. Em cada caso, prove a minimalidade.
Suponha que $a_1b_1+a_2b_2+\cdots+a_mb_m = 0$ sendo $a_1,a_2,\ldots,a_m$ e $b_1,b_2,\ldots,b_m$ números não-negativos. É verdade que $a_1=\cdots=a_m=0$ ou $b_1=\cdots=b_m=0$? Mostre que, para cada $j,$ temos $a_j=0$ ou $b_j=0.$
Parte 2: Descreva, em poucas palavras, a relação entre essa tarefa e as folgas complementares da programação linear.
Mostre que o pl primal do ep mínimo tem uma solução viável se e somente se existe um conjunto de arestas e circuitos ímpares tal que todo nó do grafo pertence a exatamente um dos circuitos ou a exatamente uma das arestas, mas não ambos.
(Motivação: O teorema de Tutte separa os grafos que têm ep dos que não têm ep. Esta questão procura separar as instâncias pl primal que têm solução das instâncias que não têm solução.)
Mostre que o novo potencial calculado pelo algoritmo Húngaro nas linhas 11 a 18 é viável. Em seguida, mostre que o conjunto justo para o novo potencial pode não ser um superconjunto do conjunto justo do potencial anterior, mas contém $M$ e $E(T).$
Calcule um ep mínimo no grafo bipartido completo com bipartição $(\conj{a,b,c},\conj{d,e,f})$ que tem os custos indicados abaixo. Procure escolher o potencial inicial $y$ de modo que o subgrafo justo $G(y)$ tenha muitas arestas. \[ \begin{array}[t]{l@{\quad}*{9}{r}} & ad & ae & af & bd & be & bf & cd & ce & cf \\[0.5ex] c & +20 & +10 & +50 & +40 & +30 & +30 & +50 & +40 & +20 \end{array} \] Veja nos exemplos 7 e 8 das notas de aula uma maneira de apresentar um resumo do rastreamento da execução do algoritmo.
Encontre um ep mínimo no grafo da figura. Encontre também soluções ótimas dos pls (6) e (7). (Esse é o pl que descreve o problema do emparelhamento perfeito mínimo e o seu dual.)
Você deve usar um software de programação linear para resolver essa tarefa. Comece resolvendo o pl (6) sem as desigualdades florais. Analise o subgrafo induzido pelas arestas $e$ que têm $0 < x_e < 1.$ Isso irá sugerir as desigualdades florais mais promissoras. Acrescente essas desigualdades ao pl (6) e resolva o pl novamente.
Sua resposta deve ser um pequeno relatório com a análise dos resultados.
Anexe à sua resposta um arquivo em formato txt com a identificação do software de programação linear, uma cópia da descrição das duas versões do pl (6) que você submeteu ao software.
Se $(G,c)$ o grafo o custos nas arestas da figura. Redefina assim os custos de duas arestas: $c_{ci} := -1$ e $c_{hi} := 4.$
1. Encontre um vetor $x$ de $FPM(G)$ que minimize $cx$. Encontre também a correspondente solução do pl dual. Verifique que a solução está correta.
2. Encontre um vetor $x$ em $PM(G)$ que minimize $cx$. Encontre também a correspondente solução do pl dual. Verifique que a solução está correta.
3. Você deve usar algum software de programação linear para resolver essa tarefa. No caso do item 2, use a solução do item 1 como pista para decidir quais desigualdades florais você quer usar.
4. Faça um pequeno relatório com a análise dos resultados. Procure fazer um relatório claro e organizado. Diga quais desigualdades florais foram usadas. Separe muito bem os vários itens da tarefa e da análise.
5. Anexe à sua resposta um arquivo em formato txt com a identificação do software de programação linear usado e uma cópia da descrição do pl do item 2 que você submeteu ao software. Dê nomes legíveis às variáveis (xab, xbc, xcd, etc.). Dê nomes legíveis às restrições (ra, rb, rc, rabc, etc.). Siga a ordem alfabética (xfg e não xgf, etc.).
Reduza o problema do ep mínimo em grafos bipartidos ao problema 4.A do fluxo de custo mínimo. Em seguida, use o teorema 4.4 para provar o teorema de Birkhoff do exercicio 7.16.
Lema 8.2: Para todo grafo bipartido $G,$ um vetor $x$ de $F\!P\!M(G)$ é vértice se e somente se $x$ é binário.
Prove o lema. Justifique cuidadosamente cada passo da prova.