Buscar

p1 CR UFABC

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Primeira Prova de BCM0506 - 17/3/2017
Nome e RA do aluno: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
• Não é permitido ausentar-se da sala durante a prova (sair e voltar).
• Não é permitido usar dispositivos eletrônicos (fones de ouvido, celular, etc.)
• Justifique suas respostas dando os passos da solução, mesmo que diretamente no desenho da
folha de questões. Não basta escrever só o resultado final!
• A prova tem 3 questões com 10 ı́tens ao todo, cada um valendo 1 ponto. Duração: 110
minutos (1h50min),
1. Para o grafo G da Figura 1 obtenha: (a) sua árvore de Prim; (b) o caminho do Caixeiro-Viajante,
considerando que ele tem que retornar ao ponto de partida; (c) a média µ de arestas por vértice e
probabilidade p de conexão entre os vértices.
Figura 1
2. Para o grafo da Figura 2, obtenha:
a) a Busca em Largura do vértice 2 a todos os
outros vértices;
b) O mesmo para Busca em Profundidade;
c) O in-degree e out-degree de todos os
vértices;
d) Seu histograma de graus e de distribuição
acumulada (probabilidades de grau).
3. Considere o grafo da Figura 3.
(a) Obtenha sua Matriz de Adjacência;
(b) Encontre os caminhos de Dijkstra, de A para
todos os outros vértices;
(c) Descubra se ele é planar ou não.
Figura 2 Figura 3
****** BOA PROVA ******

Outros materiais