AAED - Lista de exercícios 7

Prévia do material em texto

Pós-Graduação em Ciência da Computação Universidade Federal de São Paulo - São José dos Campos
Exerćıcios sobre Algoritmos em Grafos
AAED — Análise de Algoritmos e Estruturas de Dados
Prof. Jurandy G. Almeida Jr.
1o Semestre de 2020
Exerćıcios
1. Utilizando o conceito de grafos, defina uma árvore.
2. Qual é o número máximo de arestas em um grafo não orientado com n vértices? Justifique.
3. Qual é o número máximo de arestas em um grafo orientado com n vértices? Justifique.
4. Os turistas Jensen, Leuzingner, Dufour e Medeiros se encontram em um bar de Paris e
começam a conversar. As ĺınguas dispońıveis são: inglês, francês, português e alemão. Jensen
fala todas. Leuzingner não fala apenas o português. Dufour fala francês e alemão. Medeiros
fala inglês e português. Represente por meio de um grafo orientado todas as possibilidades
de um deles dirigir a palavra a outro, sendo compreendido.
5. Para cada um dos casos abaixo, indique se você usaria uma matriz de adjacência ou uma lista
de adjacência. Justifique a sua escolha.
(a) O grafo tem 10.000 vértices e 20.000 arestas e é importante usar tão pouco espaço quanto
posśıvel.
(b) O grafo tem 10.000 vértices e 20.000.000 arestas e é importante usar tão pouco espaço
quanto posśıvel.
(c) Você precisa informar o vértice adjacente a um dado vértice tão rápido quanto posśıvel.
(d) Você precisa informar se dois vértices estão conectados tão rápido quanto posśıvel.
6. Seja um grafo G cujos vértices são inteiros de 1 a 8 e os vértices adjacentes a cada vértice são
dados pela tabela abaixo:
Vértice Vértices Adjacentes
1 2 3 4
2 1 3 4
3 1 2 4
4 1 2 3 6
5 6 7 8
6 4 5 7
7 5 6 8
8 5 7
(a) Desenhe o grafo G.
(b) Represente o grafo por meio de uma matriz de adjacência.
(c) Represente o grafo por meio de uma lista de adjacência.
7. Um estudante de computação está desesperado porque acha que não vai conseguir dar conta
de algumas disciplinas da matriz curricular de seu curso. Ele resolveu, então, fazer uma lista
dessas disciplinas e seus respectivos pré-requisitos:
• LP (Lógica de Programação): nenhum.
• CUV (Cálculo em Uma Variável): nenhum.
• AEDI (Algoritmos e Estruturas de Dados I): LP.
• GA (Geometria Anaĺıtica): nenhum.
• MD (Matemática Discreta): nenhum.
• AEDII (Algoritmos e Estruturas de Dados II): AEDI.
• CVV (Cálculo em Várias Variáveis): CUV, GA.
• AL (Álgebra Linear): GA.
• PAA (Projeto e Análise de Algoritmos): MD, AEDII.
• CN (Cálculo Numérico): CUV, GA.
(a) Desenhe um grafo orientado que represente a situação descrita acima.
(b) Represente esse grafo por meio de uma matriz de adjacência.
(c) Represente esse grafo por meio de uma lista de adjacência.
8. Explique a modificação que deve ser feita no algoritmo de busca em profundidade para que
ele armazene a ordenação topológica do grafo. Para maior assimilação, considere o grafo de
disciplinas e seus pré-requisitos do exerćıcio anterior e indique os tempos de descoberta d e
finalização f de cada vértice.
9. Explique os passos que devem ser seguidos para determinar os componentes fortemente co-
nexos de um grafo orientado.
10. Considere o grafo abaixo. Assuma que as listas de adjacência que representam esse grafo
estão ordenadas em ordem alfabética de acordo com os rótulos dos vértices:
A B C D
E F G H
I J K L
M N O P
1
2
18
4
20
1 4
10
5
13
6
22
11 5
11
3
4
9
23
12 9
1 9 8
(a) Escreva as listas de adjacência que representam esse grafo.
(b) Aplique o algoritmo de busca em largura nesse grafo tomando o vértice A como origem
e apresente as distâncias d até cada vértice e a árvore de busca em largura π.
(c) Aplique o algoritmo de busca em profundidade nesse grafo iniciando no vértice A e
apresente os instantes de d e f de cada vértice e a floresta de busca em profundidade π.
(d) Aplique o algoritmo de Dijsktra nesse grafo tomando o vértice A como origem e apresente
a sequência dos vértices processados S, a estimativa do custo d de cada vértice e a árvore
de caminhos mı́nimos π.
11. Considere o grafo abaixo. Assuma que as listas de adjacência que representam esse grafo
estão ordenadas em ordem alfabética de acordo com os rótulos dos vértices:
A
D
B
E
C
F
G H
I J
6
9
3
3 2
2
4
4
6
1
8
7
6
2
2
3
1
4
(a) Escreva as listas de adjacência que representam esse grafo.
(b) Aplique o algoritmo de busca em largura nesse grafo tomando o vértice A como origem
e apresente as distâncias d até cada vértice e a árvore de busca em largura π.
(c) Aplique o algoritmo de busca em profundidade nesse grafo iniciando no vértice A e
apresente os instantes de d e f de cada vértice e a floresta de busca em profundidade π.
(d) Aplique o algoritmo de Dijsktra nesse grafo tomando o vértice A como origem e apresente
a sequência dos vértices processados S, a estimativa do custo d de cada vértice e a árvore
de caminhos mı́nimos π.
12. A esquadra da PSP de Cedofeita (Porto) recebeu um pedido muito urgente para intervir
numa tentativa de assalto numa ourivesaria localizada numa rua próxima. O Comando Ope-
racional deseja conhecer qual será o melhor trajeto a tomar, de forma a minimizar o tempo
de viagem até o objetivo desejado. Usando um mapa daquela zona da cidade, representado
esquematicamente na figura abaixo, e conhecido os tempos médios (em segundos) necessários
para percorrer cada um dos trechos desse mapa, eles utilizaram o algoritmo de Dijsktra para
determinar esse caminho mais curto. Coloque-se no lugar do Comando e, partindo do mapa
apresentado, encontre esse caminho mı́nimo.
13. Considere um tabuleiro com 3 × 4 posições. Cada posição contém um número:
0 4 3 6
7 8 6 8
2 3 1 8
O objetivo do jogo consiste em deslocar um peão desde o canto superior esquerdo até o canto
inferior direito a partir de uma sequência de movimentos para a direita ou para baixo, de
forma a minimizar o somatório dos pontos correspondentes às posições por onde se passou.
Represente esse problema por meio de um grafo orientado e resolva-o utilizando uma das
técnicas estudadas em aula.
14. O Sr. Ven de Dor, técnico de vendas, vai comprar um carro novo. Dadas as caracteŕısticas do
Sr. Ven de Dor, o véıculo sofrerá uma utilização muito grande, o que implica que, apesar dele
ser enviado para uma revisão daqui a 3 anos, possa ser economicamente mais favorável trocar
de carro após 1 ou 2 anos, em vez de mantê-lo durante os 3 anos. Isso sobretudo porque
os custos de utilização e manutenção crescem muito rapidamente com o envelhecimento dos
véıculos. O Sr. Ven de Dor sentou-se em seu escritório e calculou o custo total, isto é, o preço
de um carro novo menos o valor que ele pode adquirir com a venda de seu véıculo usado, mais
os custos de utilização e manutenção, levando em conta a possibilidade de comprar um carro
novo no ano i e trocá-lo no ano j (o ano 0 é o atual). Na tabela abaixo, são apresentados os
custos em reais calculados pelo Sr. Ven de Dor:
i
0 1 2
1 8000
j 2 18000 10000
3 31000 21000 12000
Assim, por exemplo, trocar o carro comprado agora (ano 0) no ano 1 e depois manter o carro
comprado até o ano 3, corresponde a um custo de 8000 + 21000 = 29000. O Sr. Ven de Dor
tem que decidir quantas vezes deve trocar de véıculo, caso seja viável, de forma a minimizar
a sua despesa total com carros durante esses 3 anos. Represente esse problema por meio de
um grafo orientado e resolva-o utilizando uma das técnicas estudadas em aula.
15. O matemático húngaro Paul Erdös (1913-1996), um dos mais brilhantes do século XX, é consi-
derado o mais proĺıfico da história. Erdös publicou mais de 1.500 artigos, em colaboração com
cerca de outros 450 matemáticos. Em sua homenagem, os matemáticos criaram o “número
de Erdös”. Todo matemático que publicou um artigo com Erdös tem número de Erdös 1.
Os que não possuem número 1, mas escreveram um artigo com alguém que possuinúmero
1, possuem número 2, e assim por diante. Quando nenhuma ligação pode ser estabelecida
entre Erdös e um matemático, diz-se que este possui número de Erdös infinito. Por exemplo,
o número de Erdos de Albert Einstein é 2; e, talvez surpreendentemente, o número de Erdös
de Bill Gates é 4. Considere um subconjunto de 12 matemáticos distintos identificados por
A, B, ..., K e L. A lista abaixo informa os que têm artigos em comum:
• o autor A tem artigos com D e J;
• o autor B tem artigos com C, D, J e L;
• o autor C tem artigos com H;
• o autor D também tem artigos com E;
• o autor E também tem artigos com I e K.
Erdös tem artigos com os autores A, B, D, G, J e L (e, logicamente, cada um desses autores
tem artigo com Erdös; idem para os demais casos). Considere o problema de determinar o
número de Erdös de um autor. Faça:
(a) Modele a situação dos autores acima por meio de um grafo, indicando o que representam
os vértices e as arestas (desenhe o grafo completo).
(b) Explique qual algoritmo em grafos visto em aula pode ser usado e como ele pode ser
usado para resolver esse problema.
(c) Com base na especificação da questão, no seu modelo no item (a) e em sua argumentação
no item (b), responda: qual o número de Erdös dos matemáticos C e F? Justifique sua
resposta.