Baixe o app para aproveitar ainda mais
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 ******
Compartilhar