Lista1-grafos-correcao

Prévia do material em texto

Grafos – Lista de Exercícios
Algoritmos 1 – 2022/1
Exercício 1
Suponha que seja dada uma instância do problema do caminho mais curto
entre dois vértices s e t em um grafo G, no qual todas as arestas têm custos
positivos e distintos (ce > 0 para cada aresta e). Seja P o caminho mais
curto entre s e t em G.. Suponha agora que você substitua todos os pesos ce
da aresta e pelo seu quadrado, (ce)2, assim criando uma nova instância do 
problema com o mesmo grafo mas pesos diferentes. Pode-se afirmar que P 
ainda é o caminho mais curto entre s e t na nova instância?
Exercício 1 - Solução
Falso. Suponha três arestas (u,v), (v,w) e (u,w), a primeira com custo 3, a 
segunda com custo 3.5 e a terceira com custo 5. Neste caso o caminho mais
curto entre u e w seria a aresta direta (custo 5)
Se tomarmos os quadrados dos custos, o caminho mais curto entre u e w 
passaria por v (custo 9+12.25 = 21.25 < 25) 
Exercício 2
A teoria dos seis graus de separação originou-se a partir de um estudo científico
que mostrou que são necessários no máximo seis laços de amizade para que 
duas pessoas quaisquer estejam ligadas. Pede-se: 
a) Apresente um algoritmo que, dada a rede de amizades estabelecidas entre 
usuários do Facebook, determine se a teoria dos seis graus de separação é
válida para todos os usuários da rede. Deixe claro como você modelou o 
problema usando grafos. 
b) Apresente a ordem de complexidade do seu algoritmo.
Exercício 2 - Solução
a)
Modelagem do problema usando grafos: cada usuário do Facebook é um vértice e cada aresta
representa um laço de amizade entre dois usuários. O grafo é não direcionado e não ponderado. 
Problema: O objetivo é determinar se a distância entre cada vértice (origem) e todos os demais
vértices da rede é no máximo 6. 
Solução: Como grafo não é ponderado, o caminho mais curto entre dois vertices (distância) é dado 
pela busca em largura. 
Basta então rodar a busca em largura partindo de cada vértice para todos os demais vertices. Para cada
busca, deve-se verificar se para algum vértice a distância da origem da busca até ele excede 6. 
Se exceder, a teoria não é válida neste grafo. Caso isto não ocorra em nenhuma das buscas, 
a teoria é válida.
Exercício 2 - Solução
b) Considerando V vértices e A arestas no grafo, a ordem de complexidade de uma
busca em largura e O(V + A). 
Deve-se executar uma busca para cada vértice como origem. 
Logo a complexidade da solução é O(V * (V + A)).
Exercício 3
Ainda sobre a questão anterior, considere agora que o objetivo seja avaliar a influência de usuários
do Twitter. Uma teoria derivada da teoria dos seis graus de separação diz que, dados um usuário A e 
um usuário B que segue A, a influência de A sobre B pode ser estimada pelo número de vezes que B 
deu um retweet em uma postagem de A. Mais ainda, a influência de A sobre qualquer usuário C que 
não segue A diretamente pode ser estimada de forma transitiva, somando as influências na cadeia de 
laços seguidor-seguido que conecta A a C. Isto é, se B segue A e C segue B, a influência de A sobre
C é dada pela soma das influências de A sobre B e de B sobre C. 
Se houver múltiplas cadeias de laços seguidor-seguido conectando A a C (p.ex: B e D seguem A, e 
C segue B e D), a influência de A sobre C é estimada pela menor das influências computadas para 
cada cadeia. Considerando o exemplo acima, a influência de A sobre C seria dada pelo menor valor 
entre a soma das influências de A para B e de B para C e a soma das influências de A para D e de D 
para C. Se não houver nenhuma cadeia de laços seguidor-seguido conectando A a C, A não tem
nenhuma influência sobre C.
Exercício 3
Por fim, a influência de um usuário sobre um grupo é dada pela soma das influências dele 
sobre todos os usuários do grupo.
a) Apresente um algoritmo que, dado um conjunto de usuários do Twitter, os laços seguidor-
seguido estabelecidos entre eles e o número de vezes que cada seguidor deu retweet em
postagem do usuário seguido, determine o usuário que tem a maior influência no conjunto. 
Deixe claro como você modelou o problema usando grafos.
b) Apresente a ordem de complexidade do seu algoritmo.
Exercício 3 - Solução
a) Modelagem do problema: 
Suponha que: 
• Usuário u é seguidor de usuário v no Twitter; 
• Usuário u retuítou k tweets de usuário v;
• Usuário v tem influência sobre u (direção reversa)
• Representação:
u v
k Influência de v sobre u = k
Exercício 3 - Solução
a) Modelagem do problema: 
Suponha que: 
• Usuário u retuitou usuário v (k1 vezes); 
• Usuário v retuítou usuário w (k2 vezes);
• Usuário w tem influência sobre u (direção reversa)
• Representação:
Influência de w sobre u = k1 + k2
u v
k1
w
k2
Exercício 3 - Solução
a) Modelagem do problema: 
Suponha que:
u v
k1
w
k2
Influência de w sobre u = min(k1+k2; k3+k4)
xk3 k4
Exercício 3 - Solução
a)
Modelagem do problema: O grafo é direcionado e ponderado, onde cada vértice é um usuário e 
uma aresta ligando vértice u a vértice v implica que v segue u (ordem inversa). O peso da aresta (u, v) 
deve ser a influência de u sobre v, isto é, o número de retweets dados por v de conteúdo postado por u.
Problema: O objetivo é determinar o usuário de maior influência. A influência de um usuário u sobre
um usuário v é dada pelo custo do menor caminho entre u e v no grafo. 
Solução: Assim, a solução consiste em executar o algoritmo de Dijkstra para construir a árvore dos 
caminhos mais curtos partindo de cada vértice para todos os demais, salvando a soma das distâncias
mais curtas para cada vértice. Ao final esta soma é a influência da origem sobre todo o grupo. O 
usuário que tiver a maior soma total é aquele com maior influência no grupo. 
Exercício 3 - Solução
b) 
Cada execução do Algoritmo de Dijskstra tem complexidade O((V+A)*logV ) para 
um grafo com V vértices e A arestas (não necessariamente conectado, ou seja, |A| 
pode ser menor que |V|). Como ele será executado uma vez para cada vértice, a 
complexidade da solução é O(V*(V+A)*logV ).
Exercício 4
Ainda considerando o cenário do item anterior, o objetivo agora é determinar os
maiores grupos de usuários, tal que todo par de usuários A e B dentro de um 
mesmo grupo têm influência mútua (A tem influência sobre B e B tem influência
sobre A). Apresente um algoritmo para resolver este problema e sua ordem de 
complexidade, considerando, como no item anterior, que a influência de um 
usuário sobre outro pode ser por transitividade.
Exercício 4 - Solução
Problema: Ainda considerando o mesmo grafo, o objetivo agora é determinar os
componentes fortemente conectados. 
Solução: Para tal, basta fazer: 
(1) executar a busca em profundidade anotando os tempos de término de cada vértice
(2) construir o grafo transposto (invertendo a direção de todas as arestas), 
(3) executar a busca em profundidade no grafo transposto, partindo sempre do vértice
ainda não visitado com maior tempo de término na primeira busca. 
A complexidade deste algoritmo é O(V + A). 
Exercício 5
O prefeito da cidade Xulambis deseja criar um parque de diversões de última geração
para aumentar o turismo na cidade. Ele já comprou N diferentes brinquedos e contratou
uma empresa para cuidar da instalação do parque em uma área de 10 mil metros 
quadrados nas redondezas da cidade. O projeto contratado da empresa inclui não
somente a instalação dos brinquedos e de uma portaria de entrada mas também a 
construção de rotas asfaltadas conectando os vários brinquedos, já que o terreno
onde os brinquedos foram instalados é muito lamacento e, assim, o deslocamento
a pé entre eles não é fácil. Entretanto, a empresa faliu antes de finalizar o projeto, 
deixando todos os brinquedos e a portaria do parque instalados mas sem nenhuma
estrada asfaltada entre eles.
Exercício 5
A inauguração do parque, amplamente divulgada, está próxima, e o prefeito contrata
você para projetar as estradas/rotas, permitindo assimque a inauguração seja feita. 
Considerando que tanto o orçamento quanto o tempo disponíveis são curtos, o prefeito
impõe a restrição de que o projeto desenvolvido inclua apenas a criação de estradas que 
conecte diretamente pares de brinquedos e/ou um brinquedo e a portaria, de forma que o 
gasto total com asfalto seja o menor possível. Além disto, devido a pequenos acidentes
geográficos no terreno, não é possível criar estradas diretas entre todo e qualquer par de 
brinquedos. Pede-se:
a) Modele o problema de projetar as estradas/rotas como um problema de grafos
b) Apresente um algoritmo para resolver o problema do prefeito. Qual a complexidade
do seu algoritmo? 
Exercício 5 - Solução
a) Modele o problema de projetar as estradas/rotas como um problema de grafos
Modelagem: Brinquedos e a portaria são vértices e arestas representam estradas entre dois
brinquedos (ou entre um brinquedo e uma portaria). Apenas estradas que podem ser criadas
são representadas por arestas. O grafo é não direcionado (pessoas podem caminhar em
ambas direções) e ponderado, sendo que o peso de uma aresta representa a distância entre 
os dois pontos (assume-se que o o custo de construção de uma estrada seja proporcional ao
seu comprimento/distância).
Problema: O problema em questão consiste em se obter uma árvore geradora mínima.
Exercício 5 - Solução
b) Apresente um algoritmo para resolver o problema do prefeito. Qual a 
complexidade do seu algoritmo? 
Algoritmos de Prim ou Kruskal, ambos com complexidade O(A log V)
Kruskal: ordene as arestas em ordem crescente de peso; processe as arestas nesta
ordem, adicionando uma por vez à AGM desde que a aresta não introduza um 
ciclo.
Exercício 6
Suponha que o prefeito, na campanha da divulgação do parque, deseja anunciar
que: O parque foi tão bem projetado que, a partir do portão de entrada, um cliente
pode chegar a qualquer brinquedo em no máximo Y minutos . Dado o projeto de 
rotas criado pelo algoritmo do item anterior e considerando que um cliente se 
desloca a uma velocidade média de X metros por minuto, apresente um algoritmo
para calcular o valor de Y. Qual a complexidade do seu algoritmo?
Exercício 6 - Solução
Problema: Neste caso deseja-se obter o maior caminho mais curto entre a portaria e todo e 
qualquer brinquedo utilizando como grafo de entrada a AGM criada no item anterior. 
Solução: Basta então executar o algoritmo de Dijkstra no grafo (AGM criada no item anterior) 
tendo o vértice que representa a portaria como origem, para se obter os caminhos mais curtos entre 
ele e todos os outros vértices do grafo (brinquedos). Toma-se então o maior caminho mais curto c. 
Suponha que c tenha tamanho Z. Faça Y= Z/X.
Complexidade: O algoritmo de Dijkstra tem complexidade O(A logV). Durante a sua execução
pode-se lembrar o maior caminho mais curto entre a origem e qualquer outro vértice sem alteração
de complexidade. O cálculo de Y pode ser feito em O(1) . Logo a complexidade da solução é
O(AlogV). Alternativamente, como o grafo de entrada é uma árvore (só tem um caminho da 
origem para cada vértice), pode-se também executar a DFS, modificando o algoritmo para 
acumular os pesos das arestas visitadas. Neste caso, a complexidade seria O(V+A) ou
simplesmente O(V) (dado que |A| =|V|-1).
Exercício 7
Suponha que a história seja um pouco diferente. O projeto contratado com a empresa inclui não
somente a instalação dos brinquedos e de uma portaria de entrada mas também a implantação de um 
sistema de transporte interno por trem. Em outras palavras, ele inclui a construção de uma malha de 
trilhos conectando portaria e brinquedos e a implantação uma linha interna de trens. Assim, cada
cliente poderá se deslocar a partir da portaria ou de um brinquedo para qualquer outro brinquedo (ou
de volta à portaria) tomando o trem interno. Em função de alguns acidentes geográficos no terreno, 
só é possível construir trilhos em uma única direção entre alguns pontos do parque. Suponha que a 
única forma de deslocamento seja por trem.
O prefeito suspeita da capacidade técnica da empresa e contrata você como consultor. A dúvida do 
prefeito é se a malha de trilhos projetada está correta. Em outras palavras, será sempre possível fazer
o deslocamento de qualquer ponto do parque (portaria ou brinquedo) para qualquer outro ponto? 
Modele este problema usando grafos e apresente um algoritmo que o resolva.
Exercício 7 - Solução
Modelagem: Neste caso, brinquedos e portaria são representados por vértices e trilhos conectando
dois pontos são representados por arestas. O grafo é direcionado para representar o fato de que o 
deslocamento entre alguns pares de pontos só pode ser feito em uma direção. O grafo não é
ponderado uma vez que a distância entre brinquedos/portaria é irrelevante para o problema em
questão.
Problema: Busca-se determinar se o grafo tem somente um componente fortemente conectado. 
Solução: Para tal, deve-se executar o algoritmo de Kosaraju. Se ele produzir apenas um 
componente, a resposta é afirmativa.
Algoritmo de Kosaraju: execute busca em profundidade e armazene os tempos de término dos nós. 
Construa o grafo transposto e execute a busca em profundidade no grafo transposto, sempre partindo
do vértice de maior tempo de término (na 1a DFS) ainda não visitado.