Agoritmos e Grafos - Lista 1

Prévia do material em texto

Q1: Seja G(V, E) o grafo simples não-direcionado e ponderado cuja matriz de 
adjacências é dada abaixo (células em branco indicam arestas inexistentes) 
1 2 3 4 5 
 
 1 4 2 5 
 2 60 13 7 
 3 18 20 
 4 1 
 5 
 
 a) Simule a execução do algoritmo de Kruskal para árvore geradora 
mínima, indicando a cada passo qual a decisão tomada. 
Inicialmente, temos uma floresta com 5 árvores triviais (cada uma com apenas um único 
vértice). Passaremos a olhar as arestas em ordem crescente de custo. 
1a iteração: aresta 4,5 é adicionada pois não fecha ciclo (4 e 5 estão em árvores distintas) 
2a iteração: aresta 1,3 é adicionada pois não fecha ciclo (1 e 3 estão em árvores distintas) 
3a iteração: aresta 1,2 é adicionada pois não fecha ciclo (1 e 2 estão em árvores distintas) 
4a iteração: aresta 1,5 é adicionada pois não fecha ciclo (1 e 5 estão em árvores distintas) 
A árvore geradora formada pelos 5 vértices do grafo e pelas 4 arestas acima é retornada. 
Obs.: Uma estrutura do tipo UNION/FIND para conjuntos disjuntos é utilizada para 
responder se dois vértices estão na mesma árvore, tornando desnecessária uma busca a cada 
aresta que é considerada. Inicialmente, chamamos CREATE_SET(v) para todo vértice v. 
Depois, a cada aresta v,w considerada, perguntamos se FIND(v) != FIND(w). Se forem 
diferentes, podemos adicionar a aresta, após o que chamamos UNION(v, w); se já forem 
iguais, a aresta será simplesmente “pulada". 
 b) Simule a execução do algoritmo de Prim para árvore geradora mínima, 
indicando a cada passo qual a decisão tomada. 
Inicialmente, escolhemos um vértice para iniciar o algoritmo. Começaremos então pelo 
vértice 1, que será colocado e uma heap binária de mínimo usada como estrutura. Esse 
vértice terá na heap prioridade 0, significando que ele poderá entrar na árvore que será 
Algoritmos e Grafos – Lista 1
construída pagando para isso um custo 0 de entrada (pois será o primeiro vértice a entrar, 
não sendo portanto conectado a nenhum outro que lá já estivesse). 
1a iteração: removemos a raiz da heap, que é o vértice 1, adicionamos 1 à árvore que 
estamos montando, marcamos 1 como já presente na árvore, e a seguir iteramos pelos 
vizinhos do vértice 1: os vizinhos do 1 que ainda não estão presentes na árvore são os 
vértices 2, 3 e 5. Colocamos então esses vértices na heap, associados respectivamente às 
prioridades 4, 2 e 5, que são os custos que eles teriam para entrar na árvore sendo 
conectados ao vértice 1. 
2a iteração: removemos a raiz da heap, que é o vértice 3, adicionamos 3 à árvore que 
estamos montando (ligado ao vértice 1 pela aresta 1,3 de custo 2), marcamos 3 como já 
presente na árvore, e a seguir iteramos pelos vizinhos do vértice 3: os vizinhos do 3 que 
ainda não estão presentes na árvore são os vértices 2, 4 e 5. O vértice 2 já está na heap com 
prioridade 4, então nada faremos (já que o custo de entrar na árvore se conectando ao 
vértice 3 seria de 60, que é pior que o custo atual indicado na heap que é 4); o vértice 4 
ainda não está na heap, e será portanto acrescentado, associado à prioridade 18, que é o 
custo que ele teria ao entrar na árvore conectado ao vértice 3); finalmente, o vértice 5 já 
está na heap com prioridade 5, então nada faremos (já que o custo de entrar na árvore se 
conectando ao vértice 3 seria de 20, que é pior que o custo atual indicado na heap que é 5). 
3a iteração: removemos a raiz da heap, que é o vértice 2, adicionamos 2 à árvore que 
estamos montando (ligado ao vértice 1 pela aresta 1,2 de custo 4), marcamos 2 como já 
presente na árvore, e a seguir iteramos pelos vizinhos do vértice 2: os vizinhos do 2 que 
ainda não estão presentes na árvore são os vértices 4 e 5. O vértice 4 já está na heap com 
prioridade 18, então baixaremos essa prioridade agora para 13, que é o custo que ele teria 
ao entrar na árvore conectado ao vértice 2; o vértice 5 já está na heap com prioridade 5, 
então nada faremos (já que o custo de entrar na árvore se conectando ao vértice 2 seria de 7, 
que é pior que o custo atual indicado na heap que é 5). 
4a iteração: removemos a raiz da heap, que é o vértice 5, adicionamos 5 à árvore que 
estamos montando (ligado ao vértice 1 pela aresta 1,5 de custo 5), marcamos 5 como já 
presente na árvore, e a seguir iteramos pelos vizinhos do vértice 5: o único vizinho do 5 que 
ainda não está presente na árvore é o vértice 4. O vértice 4 já está na heap com prioridade 
13, então baixaremos essa prioridade agora para 1, que é o custo que ele teria ao entrar na 
árvore conectado ao vértice 5. 
5a iteração: removemos a raiz da heap, que é o vértice 4, adicionamos 4 à árvore que 
estamos montando (ligado ao vértice 5 pela aresta 4,5 de custo 1), marcamos 4 como já 
presente na árvore, e a seguir iteramos pelos vizinhos do vértice 4: não há vizinhos de 4 que 
ainda não estejam na árvore, então nada a fazer. 
Como a heap nesse momento encontra-se vazia, o algoritmo termina, retornando a árvore 
que foi ao longo dele construída. 
Q2: Para qual das operações abaixo a representação de grafos no computador via 
matriz de adjacências é mais eficiente do que a representação via listas de 
adjacências? 
 a) percorrer cada uma das arestas do grafo em qualquer ordem 
Matriz é MENOS eficiente que listas, porque precisarei olhar a matriz inteira com custo 
O(n^2). Percorrer as listas de vizinhos tem custo O(n+m). 
 b) obter o grau médio dos vértices do grafo 
Matriz é MENOS eficiente que listas, porque novamente precisarei olhar a matriz inteira 
com custo O(n^2). Pegar o tamanho de cada lista pode ser feito em tempo O(1), então 
calcular o grau médio de todos os vértices seria feito em tempo O(n). 
 c) checar se cinco vértices dados constituem um subgrafo completo (todos 
vizinhos de todos) 
Matriz é MAIS eficiente que listas, porque isso seria feito em tempo constante, ou seja, 
O(1), bastando verificar Combinação(5, 2) = 10 células na matriz. Fazer isso em listas de 
adjacências exige que eu itere pelas listas de vizinhos de alguns vértice, algo que pode ter 
custo O(grau máximo do grafo), e que no pior caso pode ser até mesmo linear no número 
de vértices, ou seja, O(n). Essa seria, portanto, a resposta correta. 
 d) localizar o vértice com o maior número de vizinhos de grau menor 
do que 4 
Matriz é MENOS eficiente que listas, porque precisarei no mínimo olhar a matriz inteira 
com custo Omega(n^2), isto é, tenho já um limite inferior quadrático para meu esforço 
total. Fazendo com listas, posso simplesmente iterar pelas listas de vizinhos de cada vértice, 
algo que pode ser feito em tempo O(n+m), já que para cada vizinho olhado posso apenas 
perguntar seu grau em tempo O(1), pois é uma mera consulta ao tamanho de sua lista de 
vizinhos. Então isso já é melhor que o limite INFERIOR para o caso em que uso matriz. 
 e) nenhuma das respostas acima (NRA) 
Q3: Sejam A1 e A2 dois algoritmos para um mesmo problema, que recebem como 
entrada um grafo. Se A1 roda em tempo O(n + m log n) e A2 roda em tempo O(n2), 
onde n é o número de vértices do grafo e m é o número de arestas do grafo, 
podemos afirmar que: 
 a) a execução de A1 leva menos tempo do que a execução de A2 para todo 
grafo acíclico 
Ok, se o grafo é acíclico sabemos que mportanto que A2, que é O(n^2). 
 c) quando o número de vértices é suficientemente grande, A2 sempre 
rodará em mais tempo do que A1 
Isso não é verdade. Vai depender da densidade do grafo, isto é, da relação entre m e n. Se m 
for grande, digamos m = n^2, então A2 mais eficiente, necessariamente rodando em menos 
tempo que A1 a partir de certo tamanho da entrada. 
 d) quando o número de vértices é suficientemente grande e o grau mínimo 
do grafo é metade do número de vértices do grafo, A2 sempre rodará em mais 
tempo do que A1 
Se o grau MÍNIMO é n/2, isso significa que o número de arestas desse grafo é quadrático 
em n, isto é, m = Theta(n^2). Portanto, a complexidade de A1 fica O(n^2 log n). E a frase 
fica claramente falsa. 
 e) NRA 
Esta seria a opção correta: “nenhuma das respostas acima”. 
Q4: Seja o grafo simples não-direcionado G(V,E), onde 
 V = {a,b,c,...,h}, 
 E = {ab, ac, ah, bc, bd, bf, bg, cg, df, ef}. 
a) Desenhe uma árvore de largura de raiz a para G, classificando os 
diferentes tipos de arestas encontradas. 
 
 __ a __ 
 / | \ bc: aresta-irmão 
 b ….. c h df: aresta-irmão 
 / | \ : cg: aresta-tio 
 d …f g todas as outras: arestas de árvore 
 | (ou aresta-pai) 
 e 
 
b) Dê as profundidades de entrada e saída de cada um dos vértices de V 
quando uma busca em profundidade de raiz a é executada em G. 
 …. a _________ PE(a) = 1 PS(a) = 8 
 : | \ PE(b) = 2 PS(b) = 6 
 : b ::::::: . h PE(c) = 3 PS(c) = 2 
 : | \ : : PE(d) = 5 PS(d) = 5 
 :… c d : : PE(e) = 7 PS(e) = 3 
 | | : : PE(f) = 6 PS(f) = 4 
 g f …..: : PE(g) = 4 PS(g) = 1 
 : | : PE(h) = 8 PS(h) = 7 
 : e : 
 : ………….: 
c) Utilize a busca em profundidade do item anterior para determinar os 
vértices “demarcadores”, segundo o algoritmo para determinação de 
articulações e componentes biconexas de um grafo. 
 low(a) = a DEMARC (trivial, raiz) 
 low(b) = a DEMARC (trivial, filho da raiz) 
 low(c) = a 
 low(d) = b DEMARC 
 low(e) = e DEMARC 
 low(f) = b 
 low(g) = b 
 low(h) = h DEMARC (trivial, filho da raiz) 
 
d) Que vértices são articulações de G? 
 Articulações: 
 a (pois é a raiz e tem mais de um filho) 
 b (pois não é a raiz e tem um filho demarcador) 
 f (pois não é a raiz e tem um filho demarcador) 
e) Quais são as componentes biconexas de G? 
 
 {e, f} descoberta quando visitamos a aresta de árvore f,e — momento em que 
 vamos desempilhando da pilha auxiliar todos os vértices até o 
 demarcador “e” (inclusive), anotando esse(s) vértice(s) numa 
 componente juntamente com a própria articulação “f" 
 {d, f, b} descoberta quando visitamos a aresta de árvore b,d — momento em que 
 vamos desempilhando da pilha auxiliar todos os vértices até o 
 demarcador “d” (inclusive), anotando esse(s) vértice(s) numa 
 componente juntamente com a própria articulação “b” 
 {h, a} descoberta quando visitamos a aresta de árvore a,h — momento em que 
 vamos desempilhando da pilha auxiliar todos os vértices até o 
 demarcador “h” (inclusive), anotando esse(s) vértice(s) numa 
 componente juntamente com a própria articulação “a” (note que “h" 
 era o SEGUNDO filho da raiz, por isso fizemos esse procedimento) 
 {b, c, g, a} descoberta quando o algoritmo chega ao fim — é tudo o que sobrou 
 na pilha auxiliar 
 
Q5: Verdadeiro ou Falso? 
a) Se uma aresta uv é aresta de retorno em uma busca de profundidade feita em 
um grafo simples não-direcionado G, então uv será aresta de retorno em toda 
busca em profundidade feita em G. 
Claramente falso. Pode tranquilamente ser uma aresta de árvore, dependendo da raiz que se 
escolha para a busca e da ordem em que os vizinhos de cada vértice são considerados 
durante a busca. 
Exemplo: a …. 
 | : 
 b : 
 | : ac é aresta de retorno aqui, mas 
 c … : 
 b …. 
 | : 
 a : 
 | : ac é aresta de árvore aqui, para o mesmo grafo! 
 c … : 
 
b) Se uma aresta uv é aresta de retorno em uma busca de profundidade feita em 
um grafo simples não-direcionado G, então uv será aresta-pai ou aresta-irmão em 
toda busca em largura feita em G. 
 Também falso, embora o contra-exemplo seja ligeiramente menos óbvio. 
 ….. a 
 : | 
 : b 
 : | 
 : c …. 
 : | : 
 :…. d : 
 | : ec é aresta de retorno aqui, mas 
 e …: 
 a 
 / \ 
 b .. d 
 | : | 
 c :….e ec é aresta-primo aqui, para o mesmo grafo! 
c) Se um grafo simples não-direcionado G é acíclico e desconexo, então o número 
de células não-nulas em uma matriz de incidências para G será menor que o 
número de células não-nulas em uma matriz de adjacências para G. 
Falso. Será igual a 2m nos dois casos. Na verdade, no caso da matriz de adjacências, 
podemos fazer com que esse número seja igual a m, se impusermos que toda aresta x,y 
estará representada apenas na cela M[x][y] da matriz M, se x b é um contra-exemplo. Admite apenas uma topsort: a, b. 
 
Q6: Seja o digrafo D(V,E), onde: 
 V = {a,b,c,d,e} 
 E = {ab, ae, bc, bd, be, ce, dc, de}. 
 a) Encontre uma ordenação topológica para D. 
 a, b, d, c, e 
 b) Quantas arestas possui o menor subgrafo de D que só admite 
ordenações topológicas iniciadas em a e terminadas em e? 
 Uma aresta. Trata-se do subgrafo a —> e com dois vértices e uma aresta. 
 c) Quantas arestas possui o menor subgrafo gerador de D que só admite 
ordenações topológicas iniciadas em a e terminadas em e? 
 Se é gerador precisa ter todos os vértices do grafo original. Para que toda topsort tenha que 
começar em a, precisamos que todosos demais vértices tenham alguma aresta de entrada 
(ou seja, não sejam fontes no nosso subgrafo gerador). Portanto, 4 arestas é um limite 
inferior para a resposta que procuramos. Se conseguirmos um exemplo de subgrafo gerador 
em que todas as topsorts comecem em "a" e terminem em “e”, saberemos que temos uma 
solução ótima (ou seja, saberemos que podemos parar de procurar). 
Esse é o caso do subgrafo gerador seguinte: 
a —> b —> d —> c —> e. 
Quatro arestas. Apenas uma top sort (que começa em “a" e termina em “e”). 
Q7: Preciso ir de bicicleta da cidade A à cidade B, cidades estas ligadas por uma 
única estrada. Carrego na bicicleta um bidon (também conhecido como 
caramanhola, vulgo garrafinha) de 600 mililitros, e preciso ingerir 100 mililitros de 
água a cada 5 Km pedalados, do contrário desidrato e morro. Carrego comigo um 
mapa que indica a localização exata dos postos de combustível ao longo daquela 
estrada, locais esses onde posso beber água e encher minha garrafinha. 
 a) Dê um algoritmo guloso que garanta uma viagem com número mínimo 
de paradas para abastecimento. 
 Algoritmo: a partir da posição inicial na cidade A, a próxima parada será no posto 
mais longe possível da parada anterior que não exceda 35 Km de distância da parada 
anterior. (Sempre que minha garrafinha esvaziar, posso ainda percorrer 5 km, portanto 30 
Km + 5 Km = 35 Km é minha autonomia máxima.) 
 Em pseudo-código. 
 Entrada: um array com as posições de n postos ao longo da estrada, e a posição da 
cidade B. (A cidade A é assumida como estando na posição zero.) 
 Saída: os índices dos postos em que devo parar para abastecer. 
 stop_indexes = [ ] 
 current_pos = 0 
 next_stop_index = 0 
 pos[n+1] = pos[B] 
 i = 1 
 while i 35: 
 if next_stop_index == 0: 
 fail! // não há forma possível de completar o trajeto sem morrer 
 stop_indexes += [next_stop_index] 
 current_pos = pos[next_stop_index] 
 else: 
 next_stop_index = i 
 i++ 
 return stop_indexes 
 
 Complexidade: O(n). 
 
 
 b) Prove a corretude de seu algoritmo usando argumento do tipo cut and 
paste. 
Seja A a saída fornecida pelo algoritmo guloso do item (a) para alguma instância de entrada 
que tenha conjunto viável não-vazio (se o conjunto viável for vazio, o algoritmo certamente 
indicará esse caso corretamente). Suponha, para efeito de contradição, que a solução A = 
[p1, p2, …, pk], k>=0, dada pelo algoritmo, embora claramente viável (por construção), 
não seja uma solução ótima para aquela instância do problema. Vamos agora inferir uma 
contradição. 
Seja S = {T_i}, 0 0 soluções ótimas para aquela 
instância, e seja T* dentre essas aquela que maximiza j, o índice da primeira divergência 
com a solução A. Isto é, T* contém p1, p2, …, p(j-1), mas não contém pj, e nenhuma outra 
solução em S contém prefixo de A com tamanho maior do que j-1. A figura abaixo ilustra 
esse prefixo comum entre A e T*, e o X vermelho indica que pj não está presente na 
solução T*. 
 p1 p2 p3 p(j-1) pj p(j+1) … pk 
A: ____|_______|_____|_____…_______|__________|_________|_____ …______|_____ 
T*:____|_______|_____|_____…_______|______|___X______|_______|__…___|_______ 
 q1 q2 q3 qm 
Note que T* tem outros pontos de parada, à direita de pj, possivelmente coincidentes, mas 
não necessariamente coincidentes com pontos de parada da solução A. Note, também, que é 
necessário que exista um ponto de parada, na solução T*, entre a posição de p(j-1) e a 
posição de pj, uma vez que, pela construção gulosa do algoritmo, pj é o ponto mais distante 
à direta de p(j-1) que pode ser atingido, a partir de p(j-1), sem que o ciclista desidrate. Não 
seria possível, portanto, que na solução T* o ciclista reabastecesse em p(j-1) e depois 
apenas em algum posto à direita de pj. Chamaremos esse ponto de parada entre p(j-1) e pj, 
existente em T*, de q1. 
Agora vamos construir T’ da seguinte maneira: primeiramente, copiamos todos os pontos 
de parada de T* para T’, e forçamos a inclusão do ponto de parada pj nesta solução T’que 
estamos construindo, como mostra a figura abaixo. 
 p1 p2 p3 p(j-1) pj 
 ____|_______|_____|_____…_______|______|____|______|_______|__…___|_______ 
 q1 q2 q3 qm 
Neste ponto, T’ está claramente com um ponto de parada a mais em relação a T*, e, 
portanto, não é uma solução ótima (embora certamente viável). O que faremos agora será 
removermos de T’ justamente o ponto de parada q1. Para isso, precisamos garantir que é 
possível remover esse ponto de parada sem afetar a viabilidade da solução. Ora, remover 
esse ponto de parada tem dois efeitos: (1) após reabastecer em p(j-1), o ciclista seguindo a 
solução T’ vai reabastecer apenas em pj, e não em q1, como teria feito se estivesse seguindo 
a solução T*; e (2) o ciclista chegará em q2 tendo reabastecido em pj, e não em q1. O efeito 
1 é claramente ok, pois sabemos que a distância de p(j-1) a pj é percorrível pelo ciclista, 
uma vez que o ciclista precisa percorrê-la quando segue a solução (viável) A. O efeito 2 
também não fere a viabilidade de T’, uma vez que a distância de pj a q2 será menor do que 
a distância de q1 a q2, que, por sua vez, é percorrível. Chegamos assim à solução viável T’ 
mostrada abaixo: 
 p1 p2 p3 p(j-1) pj 
T’:____|_______|_____|_____…_______|__________|______|_______|__…___|_______ 
 q2 q3 qm 
Finalmente, a solução T’ acima é viável, como já argumentado, e é também ótima, uma vez 
que tem exatamente a mesma quantidade de paradas de T* (pois apenas entrou pj e saiu 
q1). Ocorre que o tamanho do prefixo comum de T’ e de A, sendo maior ou igual a j, é pelo 
menos uma unidade maior que o do prefixo comum de T* e de A, que é j-1. E isso é uma 
contradição, pois T* tinha sido escolhida como sendo a solução ótima que maximizava o 
tamanho do prefixo comum com A. 
Sendo assim, a solução A precisa ser ótima.