Exercícios durante as aulas.
E03.1 Exiba uma numeração topológica do digrafo da figura. A numeração não precisa ser injetiva.
E03.2 Verifique se o digrafo cujos arcos são 0-1 1-2 2-3 4-5 5-6 6-7 8-9 9-10 9-11 é uma floresta radicada. Em caso afirmativo, dê uma numeração topológica dos vértices.
E03.3 Exiba um digrafo que tem pelo menos uma fonte, não tem vértices com grau de entrada maior que 1, mas não é uma floresta radicada.
E03.4
Escreva uma função que diga se um dado digrafo é bipartido.
Em caso afirmativo, a função deve devolver uma numeração topológica
que só tem dois valores.
Que informação o algoritmo deve devolver para comprovar uma resposta negativa?
E04.1 Qual o resultado de DIGRAPHdfs() quando G->A vale 0? E quando G->V vale 1?
E04.2
Faça uma busca DFS no exemplo da figura
percorrendo cada linha da matriz de adjacências ao contrário
,
isto é, de V-1 para 0.
Escreva o rastreamento.
E04.3 É possível representar o digrafo ao lado por listas de adjacência de modo que a ordenamento dos vértices em pré-ordem seja 0 4 3 1 2 6 9 7 8 5? Se sua resposta for afirmativa, dê as listas de adjacência. Se for negativa, explique por quê. Repita o exercício com 0 3 1 2 4 5 6 7 9 8?
E04.4 Em geral, a ordem em que os vértices são examinados para determinar o início de uma nova etapa da busca DFS — linha for (v = 0; v < G->V; v++) de DIGRAPHdfs — não é importante. Entretanto, em certos algoritmos (como o das componentes fortes), é necessário examinar os vértices numa determinada ordem. Escreva uma variante de DIGRAPHdfs que examine os vértices na ordem dada por um ordenamento ord[0..V-1] dos vértices (o vetor ord[] é um dos argumentos da função).
E05.1
Considere o grafo
definido pelas arestas
0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5.
Suponha que o grafo é representado por uma matriz de adjacências.
Submeta o grafo à função
DIGRAPHdfs()
e faça o rastreamento da execução da função
e a correspondente classificação dos arcos.
Dê o estado final dos vetores pre[], pos[]
e pai[].
Depois, dê o correspondente ordenamento
dos vértices em pós-ordem.
E05.2 Considere o digrafo definido pelos arcos 0-1 1-2 2-3 3-4 2-4 4-2. Diga qual o tipo — retorno, descendente, ou cruzado — de cada arco.
E05.3 Dê um exemplo de um digrafo e um arco v-w com a seguinte propriedade: depois de uma execução da função DIGRAPHdfs() tem-se pre[v] < pre[w] e pos[v] < pos[w].
E05.4 Escreva uma função que receba os vetores pre[] e pai[] produzidos por DIGRAPHdfs() e imprima o tipo (floresta, de retorno, descendente, ou cruzado) de cada arco. (Dica: basta verificar se uma ponta do arco é ancestral ou descendente de outra.) Qual o consumo de tempo de sua função?
E06.1 Suponha dada uma função booleana DIGRAPHreach() que decide se existe um caminho de um dado vértice v a um dado vértice w em um digrafo G. Use essa função para escrever uma função que decida se um digrafo tem um ciclo. Estime o consumo de tempo de sua função.
E06.2 Encontre um ciclo num digrafo sem sorvedouros. Quanto tempo o seu algoritmo consome?
E06.3 Escreva uma função que decida se um digrafo é acíclico com base na seguinte ideia: recursivamente, remova fontes do digrafo; a ordem em que os vértices são removidos dá um ordenamento topológico se todos os vértices forem removidos; senão, o grafo que sobrar não tem fontes e portanto não é acíclico. Quanto tempo o seu algoritmo consome?
E06.4 Considere o algoritmo de detecção de ciclo que usa as numerações em pré-ordem e pós-ordem. Aplique o algoritmo ao digrafo definido pelas listas de adjacência abaixo. Repita o exercício depois de inverter a direção do arco 5-6.
0: 1
1: 2
2: 3
3: 5 6 4
4: 2
5: 6
6: 1
E07.1 Aplique o algoritmo de detecção de ciclo ao digrafo definido pelas listas de adjacência abaixo à esquerda. Repita o exercício para o digrafo definido pelas listas de adjacência abaixo à direita. (Aproveite para dar a classificação dos arcos.)
0: 1 0: 1
1: 2 1: 2
2: 3 2: 3
3: 5 6 4 3: 5 6 4
4: 2 4: 2
5: 6 5:
6: 1 6: 5 1
E07.2 Quantos arcos, no máximo, pode ter um DAG com V vértices?
E07.3 É verdade que cada arco de um digrafo fortemente conexo pertence a um ciclo?
E07.4 É verdade que cada etapa da busca DFS em um digrafo visita os vértices de uma e uma só componente forte?
E07.5 Em que condições um DAG é fortemente conexo?
E07.6
Que cara
têm as componentes fortes de um DAG?
E08.1 Escreva uma função que decida se um digrafo é fortemente conexo em tempo proporcional a V + A, sendo V o número de vértices e A o número de arcos do digrafo. (Sugestão: faça uma busca no digrafo inverso.)
E08.2 Suponha que um DAG é submetido a uma busca em profundidade. Como o primeiro vértice de cada etapa deve ser escolhido de modo cada árvore da floresta DFS resultante tenha um só vértice?
E08.3 Mostre que uma busca em profundidade em um digrafo fortemente conexo tem uma só etapa (qualquer que seja o vértice inicial da busca). A recíproca é verdadeira?
E08.4 Aplique o algoritmo de Kosaraju-Sharir ao digrafo da figura.
E09.1 Mostre que todos os vértices de qualquer ciclo de um digrafo pertencem à mesma componente forte.
E09.2
Identifique a olho
as componentes fortes do digrafo
e faça um desenho do digrafo das componentes fortes.
E09.3 Escreva um algoritmo simples (mesmo que não seja eficiente) que calcule as componentes fortes de um digrafo G. O algoritmo deve devolver o número de componentes fortes do digrafo e preencher um vetor sc[] indexado pelo vértices tal que sc[v] == sc[w] se e somente se v e w pertencem à mesma componente forte. (Sugestão: use a função DIGRAPHreach().) Quanto tempo o seu algoritmo consome?
E09.4 Suponha que as componentes fortes de um digrafo G são numerados de 0 a k-1. Seja sc[] uma numeração dos vértices de G que associa a cada vértice o número da componente forte a que o vértice pertence. Escreva uma função que receba G e sc[] e construa o digrafo das componentes fortes de G.
E09.5 Aplique o algoritmo de Kosaraju-Sharir ao digrafo da figura.
E09.6 Aplique o algoritmo de Kosaraju-Sharir ao digrafo da figura. Na primeira fase do algoritmo, tome os vértices em ordem decrescente de nomes. %
E09.7
O algoritmo de Kosaraju-Sharir
calcula um ordenamento em pós-ordem,
digamos L1,
dos vértices do digrafo inverso
e depois processa o digrafo original
na ordem inversa de L1.
Não seria mais simples evitar essas duas inversões
e fazer o seguinte:
calcular o ordenamento em pós-ordem,
digamos L0,
dos vértices do
digrafo original
e depois processar o digrafo original
na ordem L0?
(Sugestão:
Considere o digrafo definido pelos arcos
0-1 1-2 2-3 3-1 2-4 3-5 ,
que consiste em um ciclo com três pernas
.)
E10.1 Aplique o algoritmo de Kosaraju-Sharir (função DIGRAPHscKS()) ao digrafo G da primeira figura abaixo. (A segunda figura mostra o digrafo inverso GR.) Tome os vértices em ordem decrescente de nomes.
E10.2
Faça um rastreamento da busca em largura, a partir do vértice 5,
na árvore radicada
da figura.
Observe que a busca em largura percorre a árvore por níveis
.
E10.3 Depois de executar a função DIGRAPHbfs() com argumentos G e s, seja X o conjunto dos vértices v para os quais num[v] é diferente de -1. Descreva o leque de X.
E10.4 Considere uma busca em largura num grafo a partir de um vértice s. Seja v-w um arco do grafo e suponha que w não é filho de v nem pai de v na árvore de busca em largura. Mostre que v não é ancestral nem descendente de w.
E11.1 Seja s um vértice de um digrafo G. Suponha que conhecemos a distância de s a cada um dos demais vértices de G. O que se pode dizer sobre a distância entre dois vértices quaisquer v e w? Repita o exercício com grafo no lugar de digrafo.
E11.2 Mostre que no início de cada iteração de DIGRAPHdist() existe um inteiro positivo d tal que a sequência de valores de dist[] ao longo da fila é d d ... d ou d d ... d d+1 ... d+1. (Não é possível, por exemplo, que a sequência seja d d d d+1 d+1 d d.)
E11.3 A função DIGRAPHbfs() (e também a função DIGRAPHdist()) constrói uma árvore BFS no digrafo. Essa árvore satisfaz a definição de árvore radicada?
E11.4 Um digrafo G é submetido a dois algoritmos de componentes fortes. Cada algoritmo produz uma numeração dos vértices que identifica a componente forte a que cada vértice pertence. O primeiro produz uma numeração sc1[] e o segundo produz uma numeração sc2[]. Se os algoritmos forem corretos, sc1[] e sc2[] devem ser equivalentes. Escreva um algoritmo que decida se sc1[] e sc2[] são equivalentes.
E11.5 Escreva uma função que decida se um digrafo G é uma árvore radicada. Em caso afirmativo, a função deve depositar no vetor pre[] uma numeração topológica de G. (Sugestão: Faça uma busca em profundidade e veja a classificação dos arcos.)
E11.6 Generalize o código de DIGRAPHdist() para calcular caminhos mínimos a partir de um conjunto: dado um conjunto não vazio S de vértices, determinar, para cada vértice t, um caminho mínimo dentre os que começam em S e terminam em t.
E12.1
Considere o grafo cujas arestas são
0-1 0-2 0-3 1-2 1-3 2-3 .
Faça uma lista de todos os ciclos não triviais do grafo
que não sejam equivalentes
entre si.
E12.2 Aplique a função GRAPHhasCircuit() ao grafo cujas arestas são 0-1 0-2 0-3 1-2 1-3 2-3 .
E12.3 A função GRAPHhasCircuit() é capaz de encontrar um circuito em um digrafo não simétrico?
E12.4 Escreva uma função que decida se um dado grafo tem um circuito fazendo uma busca em largura. Use a função que calcula distâncias como inspiração (mas lembre-se de que sua função só se aplica a grafos). Para simplificar, você pode supor que o grafo é conexo.
E12.5 Escreva uma função que construa uma árvore aleatória com V vértices.
E12.6 Mostre que toda árvore com V vértices tem exatamente V − 1 arestas. Mostre que toda floresta com V vértices e C componentes conexas tem exatamente V − C arestas.
E12.7 Prove que toda floresta com pelo menos uma aresta tem pelo menos duas folhas.
E13.1a
O grafo da figura admite bipartição?
(Aqui, admite
é o mesmo que tem
.)
E13.1b
O grafo da figura admite bipartição?
(Aqui, admite
é o mesmo que tem
.)
E13.2 Mostre que toda floresta é bicromática.
E13.3 Suponha que um grafo tem um ciclo ímpar. Mostre que o grafo não admite bipartição.
E13.4 Acrescente código a GRAPHtwocolor() para construir uma floresta DFS durante a busca. Em seguida, mostre que as cores dos vértices são alternadamente 0 e 1 ao longo de qualquer caminho na floresta DFS.
E13.5 Escreva uma função que use busca em largura para reconhecer grafos bipartidos. (Sugestão: comece por calcular a distâncias de um vértice s a cada um dos outros; para toda aresta v-w, as distâncias de s a v e de s a w devem ter paridade diferente, ou seja, uma deve ser par e a outra deve ser ímpar.)
E13.6 [Difícil] Escreva uma função que procure um circuito de comprimento par num grafo. (Sugestão: calcule todas as distâncias a partir de algum vértice s e estude cuidadosamente a árvore das distâncias.)
E14.1 Seja subset[] um vetor de 0s e 1s indexado pelos vértices de um grafo G. Seja X o conjunto de vértices indicado pelos 1s do vetor subset[]. Escreva uma função que calcule as componentes conexas do subgrafo induzido por X.
E14.2 Generalize o código de DIGRAPHdist() para calcular caminhos mínimos a partir de um conjunto: dado um conjunto não vazio S de vértices, determinar, para cada vértice t, um caminho mínimo dentre os que começam em S e terminam em t.
E14.3 [Relação entre bipartição e distância.] Seja s um vértice qualquer de um grafo conexo G. Para cada vértice x, denote por d(x) a distância de s a x. Suponha que d(v) ≠ d(w) para cada aresta v-w. Prove que G é bipartido. (Dica: exiba uma bicoloração do vértices.)
E14.4 Escreva uma função que receba um grafo e encontre uma bicoloração dos vértices ou um ciclo ímpar. Sua função deve usar busca em largura. A bicoloração (se existir) deve ser armazenada num vetor color[]. O ciclo ímpar (se existir) deve ser armazenado num vetor circuit[]. (Dica: O grafo pode ser desconexo. Em cada componente conexa, tome um vértice s e faça uma BFS a partir de s, como estivesse calculando distâncias a partir de s.) Não use vetores dist[] nem num[]; basta usar color[] e pai[].
E14.5 Escreva uma função que construa uma árvore aleatória com V vértices.
E14.6 [Coloração de vértices.] Seja G o seguinte grafo: comece com grade simétrica m-por-n; depois, acrescente diagonais noroeste-sudeste a todos os pequenos quadrados. Mostre que G admite uma coloração válida dos vértices com 3 cores apenas.
E14.7 [Coloração de vértices.] Qual o número mínimo de cores necessário para uma coloração válida do grafo da dama do jogo de xadrez? Trate de tabuleiros 2-por-2, depois de tabuleiros 3-por-3, etc.
E15.1 A primeira iteração de GRAPHsequentialColoring() está correta? A função produz uma coloração válida quando o grafo tem apenas um ou dois vértices? Ela produz uma coloração válida quando o grafo não tem arestas?
E15.2 Quantas cores a função GRAPHsequentialColoring() usa para colorir um grafo bipartido?
E15.3 Aplique GRAPHsequentialColoring() à grade simétrica 4×5 com diagonais.
E15.4 Quantas cores, no máximo, GRAPHsequentialColoring() usa? (Dê uma resposta em função de algum parâmetro do grafo.) Como escolher um bom valor para o tamanho maxk do vetor disponivel[]?
E15.5 Heurística de Brelaz. Esta é uma variante do algoritmo de coloração sequencial. Suponha dada uma coloração parcial válida de um grafo G e suponha que o conjunto de cores é 0 1 2 ... k-1. Em cada iteração, escolha um vértice incolor v que seja adjacente ao maior número de cores diferentes. Aplique a v a menor cor que seja diferente das cores usadas nos vizinhos de v. Implemente esse algoritmo.
E15.6 Implemente o algoritmo de coloração sequencial combinado com a heurística das componentes bicoloridas.
E16.1 Encontre um emparelhamento máximo no grafo da figura.
E16.2 Grade simétrica. Encontre um emparelhamento máximo numa grade simétrica m-por-n.
E16.3 Encontre um caminho aumentador para o emparelhamento vermelho. Encontre dois caminhos alternantes que não sejam aumentadores.
E16.4 Escreva uma função que receba um grafo G e um vetor match[] de vértices indexado por vértices e verifique se o vetor representa um emparelhamento. Segunda parte: imprima a lista de arestas do emparelhamento representado por match[].
E17.1 Calcule um emparelhamento máximo no grafo da figura. Prove que o seu emparelhamento é máximo.
E17.2 Seja K uma cobertura e M um emparelhamento em um grafo. Prove que |K| ≥ |M|.
E17.3 É verdade que em qualquer grafo (bipartido ou não) existe uma cobertura K e um emparelhamento M tais que |K| = |M|?
E17.4 Mostre que, em qualquer grafo (bipartido ou não), o tamanho de um emparelhamento maximal é pelo menos 50% do tamanho de um emparelhamento máximo.
E18.1 Considere o grafo definido pelo conjunto de arestas 0-1 1-2 2-0 1-3 1-4 4-5 5-6 6-4. Para cada aresta, diga se ela é uma ponte ou se seus arcos pertencem a ciclos não-triviais.
E18.2 Considere o grafo definido pelas arestas 0-1 1-2 2-3 3-4 4-5 5-6 6-7 7-8 8-9 9-0. Escolha uma floresta DFS em G e calcule o vetor low[].
E18.3 Mostre o rastro da aplicação do algoritmo GRAPHbridges() ao grafo definido pelas arestas 0-9 9-6 6-1 1-3 3-2 2-7 3-4 4-5 4-8 9-8 6-3 3-7. Suponha que os vértices são sempre examinados em ordem crescente de nomes.
E18.4 Quantas componentes aresta-biconexas tem uma grade simétrica m-por-n?
E19.1 Mostre como o algoritmo de busca em largura (que atua sobre um digrafo sem custos) pode ser usado para calcular um caminho mínimo num digrafo com custos inteiros estritamente positivos nos arcos. (Sugestão: Subdivida os arcos.) Estime o consumo de tempo do seu algoritmo.
E19.2 Multiplicar o custo de cada arco de um digrafo por uma constante estritamente- positiva não muda a solução do problema dos caminhos mínimos (ou seja, os caminhos que eram mínimos continuam mínimos). Certo ou errado?
E19.3 Somar uma constante estritamente positiva ao custo de cada arco de um digrafo não muda a solução do problema dos caminhos mínimos (ou seja, os caminhos que eram mínimos continuam mínimos). Certo ou errado?
E19.4 Considere o digrafo com custos nos arcos definido abaixo. O vetor pai[] dado em seguida é uma árvore radicada com raiz 0 no digrafo. O vetor x[] registra os custos dos caminhos com origem 0 na árvore.
0-2 0-3 0-4 2-4 3-4 3-5 1-4 4-5 5-1 1-2 .7 .2 .8 .1 .7 .1 .1 .0 .3 .3
v 0 1 2 3 4 5
pai[v] 0 5 0 0 0 3
x[v] .0 .6 .7 .2 .8 .3
Essa árvore radicada é uma SPT? (Responda sem executar um algoritmo de caminhos mínimos.)
E19.5 Considere um digrafo com custos positivos nos arcos. Seja s um vértice do digrafo e v-w um arco. Mostre que d(s,v) + cvw ≥ d(s,w), sendo cvw o custo de v-w. Deduza daí que d(s,v) + d(v,t) ≥ d(s,t) para quaisquer vértices s, v e t.
E20.1 A seguinte tabela promete dar as distâncias entre os vértices A,B,C e D de um grafo com custos positivos nas arestas. (Note que o grafo não é dado.)
A B C D
A 0 53 54 48
B 53 0 18 101
C 54 18 0 12
D 48 101 12 0
As distâncias estão corretas? Corrija a tabela se necessário. Construa um grafo com vértices A, B, C, D e custos nas arestas que seja consistente com a tabela corrigida. Procure construir um grafo com o menor número possível de arestas. Faça uma tabela que indique em cada posição (i,j) qual o primeiro vértice no caminho mínimo de i para j.
E20.2 Seja G o digrafo com custos nos arcos descrito a seguir. Seja T a árvore radicada com raiz 0 cujos arcos são 0-1 1-2 1-3 . Seja F a franja de T. Faça uma lista dos arcos de F. Dê todos os caminhos em T + F que começam em 0 e terminam fora de T. Destaque os caminhos de custo mínimo.
0-1 0-5 1-2 1-3 2-5 2-6 3-6 5-1 5-4 5-6 6-3 6-4 .1 .6 .1 .2 .5 .5 .5 .1 .0 .3 .2 .2
E20.3 Aplique o algoritmo de Dijkstra com vértice inicial 0 ao seguinte digrafo com custos nos arcos:
0-1 1-2 2-3 3-4 4-5 0-2 0-5 .1 .1 .1 .1 .1 .3 .6
E20.4 Mostre que a função DIGRAPHsptD0() (implementação ingênua do algoritmo de Dijkstra) consome VA unidades de tempo no pior caso.
E21.1 A tabela define um digrafo com custos positivos nos arcos. Segue o vetor de pais de uma árvore radicada T com raiz 0 e, para cada vértice v, o custo x[v] do único caminho em T que vai de 0 a v. A árvore T é uma SPT? Explique detalhadamente.
0-1 1-2 2-3 4-3 3-5 3-0 0-5 5-4 1-4 4-2 5-1 .41 .51 .50 .36 .38 .45 .29 .21 .32 .32 .29
v 0 1 2 3 4 5
pai[v] 0 0 4 4 5 0
x[v] .0 .41 .82 .86 .50 .29
E21.2 Escreva uma função que receba um digrafo G com custos positivos nos arcos e uma árvore radicada T em G e diga se T é uma SPT de G.
SOLUÇÃO:
boolean isSPT( Digraph G, Vertex *pai) {
int *x = malloc( G->V * sizeof (double));
double INFINITO = somaTodosOsCustos( G);
for (v = 0; v < G->V; v++) x[v] = INFINITO;
for (s = 0; s != pai[s]; s = pai[s]) ;
/* s é a raiz da árvore */
x[s] = 0.0;
distsR( G, pai, s, x);
/* para cada w, x[w] é o custo do caminho
de s a w na árvore */
for (v = 0; v < G->V; v++)
for (a = G->adj[v]; a != NULL; a = a->next)
if (!(x[v] + a->cost >= x[w])) {
free( x);
return FALSE;
}
free( x);
return TRUE;
}
/* Supõe que x[v] é a distância de s a v na árvore.
Para cada descendente w de v na árvore, armazena
em x[w] a distância de s a w na árvore.
*/
void distsR( Digraph G, Vertex *pai, Vertex v, double *x) {
for (a = G->adj[v]; a != NULL; a= a->next)
if (pai[a->w] == v) {
x[a->w] = x[v] + a->cost;
distsR( G, pai, a->w, x[a->w]);
}
}
Se T não for maximal (ou seja, se T não contiver todos os vértices que estão ao alcance de s em G), a resposta será FALSE.
E21.3 Seja G o digrafo com custos nos arcos descrito a seguir. Seja T a árvore radicada com raiz 0 cujos arcos são 0-1 1-2 1-3 . Seja F a franja de T. Faça uma lista dos arcos de F. Dê todos os caminhos em T + F que começam em 0 e terminam fora de T. Destaque os caminhos de custo mínimo.
0-1 0-5 1-2 1-3 2-5 2-6 3-6 5-1 5-4 5-6 6-3 6-4 .1 .6 .1 .2 .5 .5 .5 .1 .0 .3 .2 .2
E21.4 Aplique o algoritmo de Dijkstra com vértice inicial 0 ao seguinte digrafo com custos nos arcos:
0-1 1-2 2-3 3-4 4-5 0-2 0-5 .1 .1 .1 .1 .1 .3 .6
E21.5 Considere o digrafo com custos nos arcos definido a seguir. Uma certa iteração da implementação DIGRAPHsptD0() do algoritmo de Dijkstra começa com a árvore radicada cujos arcos são 6-1 e 6-2. Dê o estado dos vetores pai[] e dist[] no início da próxima iteração.
6-1 6-2 1-2 4-3 5-3 0-3 1-4 2-4 0-4 1-5 6-0 1-0 2-0 1.5 1.6 2.5 2.5 1.5 1.5 4.4 4.2 1.1 4.5 4.7 3.0 3.0
E21.6 Suponha dado um digrafo G com custos positivos nos arcos, um vértice s, e a distância dist[v] de s a v para cada vértice v. Decida se podemos diminuir o custo de um dado arco v-w sem que o vetor de distâncias dist[] sofra alterações.
E21.7 Suponha dado um digrafo G com custos positivos nos arcos, um vértice s, e a distância dist[v] de s a v para cada vértice v. Decida se podemos aumentar o custo de um dado arco v-w sem que o vetor de distâncias dist[] sofra alterações.
E21.8 Considere as implementações DIGRAPHsptD1(), DIGRAPHsptD2() e DIGRAPHsptD3() do algoritmo de Dijkstra? Como começa cada iteração dessas implementações?
E21.8a Explique informalmente, em suas próprias palavras, qual a diferença entre as implementações DIGRAPHsptD2() e DIGRAPHsptD3() do algoritmo de Dijkstra.
E21.9 Custos nos vértices. Suponha dado um digrafo com custos positivos associados aos vértices. O custo de um caminho num tal digrafo é a soma dos custos dos vértices do caminho. Quero encontrar um caminho de custo mínimo dentre os que começam num vértice s e terminam num vértices t. Reduza esse problema ao problema de encontrar um caminho num digrafo com custos nos arcos. (Sugestão: Troque cada vértice v com custo c por um arco v0-v1 com custo c. Os arcos que entravam em v passam a entrar em v0 e os que saíam de v passam a sair de v1.
E22.1 Seja G um grafo conexo com custos nas arestas. Seja T uma MST de G. Mostre que T continua sendo uma MST de G se o custo de cada aresta for multiplicado por um mesmo número m ≥ 0. (A propriedade continua válida se m for estritamente negativo?) Mostre que T continua sendo uma MST de G se somarmos um mesmo número s, positivo ou negativo, ao custo de cada aresta.
Cuidado! Muita gente errou essa questão simples. É uma péssima ideia usar o condição dos circuitos (condição insere-remove) para resolver essa questão!
SOLUÇÃO DA PARTE 1: Para cada aresta e, seja c(e) o custo da aresta. Defina um novo sistema de custos nas arestas: o custo de cada aresta e é agora f(e) := m c(e). Vamos mostrar que T é uma MST para o grafo G com custos f.
PROVA: É claro que T é uma árvore geradora. Resta mostrar que o custo f(T) de T é mínimo. Seja S uma árvore geradora qualquer e vamos mostrar que f(T) ≤ f(S):
| f(T) | = | ∑(f(e) : e em T) |
| = | ∑(m c(e) : e em T) | |
| = | m ∑(c(e) : e em T) | |
| = | m c(T) | |
| ≤ | m c(S) | |
| = | m ∑(c(e) : e em S) | |
| = | ∑(m c(e) : e em S) | |
| = | ∑(f(e) : e em S) | |
| = | f(S). |
(Note como nossas contas dependem da hipótese m ≥ 0.)
SOLUÇÂO DA PARTE 2: Defina um novo sistema de custos nas arestas: o custo de cada aresta e é agora f(e) := c(e) + s. Vamos mostrar que T é uma MST para o grafo G com custos f.
PROVA: É claro que T é uma árvore geradora. Resta mostrar que o custo f(T) de T é mínimo. Seja S uma árvore geradora qualquer e vamos mostrar que f(T) ≤ f(S):
| f(T) | = | ∑(f(e) : e em T) |
| = | ∑(c(e) + s : e em T) | |
| = | (∑(c(e) : e em T)) + (V−1)s | |
| = | c(T) + (V−1)s | |
| ≤ | c(S) + (V−1)s | |
| = | (∑(c(e) : e em S)) + (V−1)s | |
| = | ∑(c(e) + s : e em S) | |
| = | ∑(f(e): e em S) | |
| = | f(S), |
sendo V o número de vértices de G. A prova depende do seguinte fato: toda árvore geradora de G tem exatamente V−1 arestas.
E22.2 Aplique o certificado de minimalidade baseado em circuitos ao grafo da figura. Depois, aplique o certificado de minimalidade baseado em cortes.
4-5 4-7 5-7 0-7 1-5 0-4 2-3 1-7 0-2 1-2 1-3 2-7 6-2 3-6 6-0 6-4
.35 .37 .28 .16 .32 .38 .17 .19 .26 .36 .29 .34 .40 .52 .58 .93
SOLUÇÃO: O custo da aresta 5-1 é ≥ que o custo de qualquer aresta do circuito 5-1-7-5. O custo da aresta 1-3 é ≥ que o custo de qualquer aresta do circuito 1-3-2-0-7-1. Etc. etc.
O custo da aresta 5-7 é ≤ que o custo de qualquer aresta do corte 5-1 5-7 4-7 4-0 4-6. Etc. etc.
E22.3 Mostre que SPTs e MSTs de grafos conexos podem ser muito diferentes. Dê um exemplo de um grafo G com custos positivos nas arestas e uma MST T nesse grafo que tenha a seguinte propriedade: para todo vértice s existe um vértice t tal que a distância de s a t em G é diferente da distância de s a t em T. (Dica: existem exemplos com 4 vértices apenas.)
E22.4 Suponha que todas as arestas de um grafo conexo têm o mesmo custo. Mostre que toda árvore geradora do grafo é uma MST.
E22.5 Suponha que os custos das arestas de um grafo conexo são distintos entre si (ou seja, não há duas arestas com o mesmo custo). Mostre que o grafo tem uma única MST.
E22.6 Seja G um grafo conexo com custos nas arestas. Suponha que uma aresta e de G é mais cara que qualquer outra aresta de G. É verdade que nenhuma MST de G contém e?
E22.7 Suponha que os custos das arestas de um grafo conexo são distintos entre si. Seja C um circuito qualquer. É verdade que a aresta mais barata de C pertence à (única) MST do grafo?
E22.8 Como encontrar uma árvore geradora de custo máximo num grafo conexo com custos nas arestas?
E22.9 Seja a uma aresta de custo mínimo em um grafo G com custos nas arestas. É verdade que a pertence a alguma MST de G? É verdade que a pertence a toda MST de G?
E22.10 Seja C um circuito em um grafo conexo G com custos nas arestas. Suponha que uma aresta e de C é mais cara que qualquer outra aresta de C. É verdade que nenhuma MST de G contém e?
E23.1 Compare o algoritmo de Prim com o algoritmo de Dijkstra para o problema da SPT (caminhos de custo mínimo). Quais as diferenças? Quais as semelhanças?
SOLUÇÃO: O conceito de preço de um vértice é diferente nos dois algoritmos. O resto é praticamente igual.
E23.2 Compare o código de GRAPHmstP1() com o de DIGRAPHsptD1() para o problema da SPT (caminhos de custo mínimo). Quais as diferenças? Quais as semelhanças?
SOLUÇÃO: Apenas duas linhas de código são diferentes! O resto é igual!
E23.3
Escreva uma versão simplificada da função
GRAPHmstP1()
que receba um grafo conexo e
devolva o custo — apenas o custo —
de uma MST do grafo.
Escreva código enxuto
, sem variáveis supérfluas.
E23.4 Modifique o código de GRAPHmstP1() de modo a imprimir um rastreamento da execução da função.
E23.5 Aplique a função GRAPHmstP1() ao grafo com custos nas arestas descrito abaixo. Faça o rastreamento da execução da função.
0-2 2-4 4-1 1-3 3-0 2-3 0-4 0.8 0.2 0.3 0.0 0.8 0.0 0.4
SOLUÇÃO: Será que assim está certo?
pai[] pr[] (x 10) frj[] 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 - - - - 0 * 8 8 4 0 - 0 0 0 0 - - - 0 0 3 2 8 4 0 4 4 0 0 0 - 4 - 0 0 3 2 0 4 0 4 4 2 0 0 - 4 2 0 0 0 2 0 4 0 3 4 2 0 0 3 4 2 0 0 0 2 0 4 0 3 4 2 0
E24.1 O que acontece se as últimas linhas de GRAPHmstK0() forem trocadas pelo código a seguir?
for (v = 0; v < G->V; v++)
if (chefe[v] == chefe[w0])
chefe[v] = chefe[v0];
E24.2 Aplique a função GRAPHmstK1() ao grafo com custos descrito a seguir. Faça uma figura da estrutura union-find definida por ch[].
3-4 2-4 5-6 0-2 0-3 2-3 4-5 4-6 1-2 3-5 1-6 1-4 .2 .3 .4 .5 .8 1.0 1.2 1.4 1.6 1.8 2.6 3.0
SOLUÇÃO: Seguem os vetors ch[], sz[] e mst[] no início das sucessivas iterações da função GRAPHmstK1():
ch[] sz[] mst[]
0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5
0 1 2 3 4 5 6 1 1 1 1 1 1 1
0 1 2 3 3 5 6 1 1 1 2 1 1 1 3-4
0 1 3 3 3 5 6 1 1 1 3 1 1 1 3-4 2-4
0 1 3 3 3 5 5 1 1 1 3 1 2 1 3-4 2-4 5-6
3 1 3 3 3 5 5 1 1 1 4 1 2 1 3-4 2-4 5-6 0-2
3 1 3 3 3 3 5 1 1 1 6 1 2 1 3-4 2-4 5-6 0-2 4-5
3 3 3 3 3 3 5 1 1 1 7 1 2 1 3-4 2-4 5-6 0-2 4-5 2-1
Veja a evolução da estrutura union-find à medida que arestas são acrescentadas à MST:
3
4 2 0 5 1
6
3-4
3
__|
|
4 2 0 5 1
6
2-4
3
__|
| |
4 2 0 5 1
6
5-6
3
__|
| |
4 2 0 5 1
|
6
0-2
3
__|__
| | |
4 2 0 5 1
|
6
4-5
3
__|_____
| | | |
4 2 0 5 1
|
6
2-1
3
__|________
| | | | |
4 2 0 5 1
|
6
E24.3
Escreva uma versão simplificada da função
GRAPHmstK1()
que receba um grafo G possivelmente desconexo e
devolva o custo —
apenas o custo —
de uma floresta geradora maximal de custo mínimo de G.
Escreva o código do union-find tão embutido quanto possível
no código de sua função.
Escreva código enxuto
, sem variáveis supérfluas.
E24.4 [Sedgewick 20.18] Vetor de pais. Escreva uma função GRAPHmstK1_pai() que invoque GRAPHmstK1() e depois calcule o vetor de pais pai[] da árvore gradora que GRAPHmstK1() depositou no vetor mst[].
SOLUÇÃO do Pedro:
Edge mst[1000-1];
Vertex pai[1000];
void GRAPHmstK1_pai( Graph G)
{
int k;
GRAPHmstK1( G);
/* mst[0..V-1] é o conjunto de arestas de uma MST
de G. Temos mst[k].v < mst[k].w para cada k
em virtude da função GRAPHedges().
*/
for (k = 0; k < G->V-1; ++k)
pai[mst[k].w] = mst[k].v;
pai[0] = 0;
}
Eu acho que está certo. O que você acha?
Pensando melhor, acho que não está certo. Você tem um contraexemplo?
E25.1 Dê um caminho mínimo do vértice 0 ao vértice 3 no DAG com 4 vértices e custos nos arcos especificado a seguir. Adote o ordenamento topológico 0 1 2 3 4.
0-1 0-2 1-3 2-3 1.1 2.1 3.1 1.8
E25.2 O seguinte exemplo mostra que a função DAGminPath() não pode ser aplicado a digrafos que têm ciclos. Suponha que queremos determinar as distâncias a partir do vértice 0 no digrafo com custos nos arcos definido abaixo. Verifique que a função produz resultados incorretos se os vértices forem processados na ordem 0 1 2 3 .
0-2 2-1 2-3 1-3 3-2 0.1 0.1 0.9 0.1 0.1
E25.3 Modifique o código de DAGminPath() para que a função calcule uma SPT (ou seja, uma árvore radicada de caminhos mínimos) com raiz s.
E25.4 Calcule caminhos mínimos a partir do vértice 0 no DAG descrito a seguir. Use o ordenamento topológico 0 3 2 4 5 1 .
0-2 0-4 0-3 3-4 3-5 2-1 2-4 4-1 4-5 5-1 2.0 3.0 4.0 -2.0 1.0 1.0 -1.0 0.0 1.0 2.0
E25.5 PERT/CPM. O seguinte problema surge naturalmente na administração de grandes projetos de engenharia. Dado um DAG com custos positivos nos arcos (os custos representam o tempo da execução de uma parte do projeto), encontrar um caminho máximo dentre os máximos, ou seja, um caminho C tal que nenhum outro caminho (quaisquer que sejam sua origem e seu término) tenha custo maior que o de C. Adapte o código de DAGmaxPath() para resolver o problema.