TEORIA DOS GRAFOS - Q2

Prévia do material em texto

UNIP CONTEÚDOS ACADÊMICOS BIBLIOTECAS MURAL DO ALUNO TEORIA DOS GRAFOS D66B_13701_R_20251 CONTEÚDO Revisar envio do teste: QUESTIONÁRIO UNIDADE Usuário FERNANDA MARTINS FERREIRA Curso TEORIA DOS GRAFOS Teste QUESTIONÁRIO UNIDADE Iniciado 28/03/25 23:35 Enviado 28/03/25 23:35 Status Completada Resultado da tentativa 5 em 5 pontos Tempo decorrido 0 minuto Resultados exibidos Respostas enviadas, Perguntas respondidas incorretamente Pergunta 1 0,5 em 0,5 pontos Considere as seguintes asserções sobre algoritmo de Kruskal: - - Todas as arestas são ordenadas por peso. Verifica-se cada aresta da sequência ordenada para ver se pode ser considerada parte da árvore em construção. III Uma aresta é adicionada à arvore se não aparece nenhum ciclo depois de sua inclusão. São asserções verdadeiras: Resposta Selecionada: a. I, e III. Pergunta 2 0,5 em 0,5 pontos algoritmo que calcula caminho mínimo de um nó particular a qualquer outro nó: Resposta Selecionada: e. Bellman-Ford.Pergunta 3 0,5 em 0,5 pontos Considere as seguintes asserções: I - As arestas de um grafo podem estar associadas a certos pesos que representam, por exemplo, distâncias entre cidades. As arestas de um grafo podem estar associadas a certos pesos que representam, por exemplo, tempos que separam a execução de certas tarefas. III As arestas de um grafo podem estar associadas a certos pesos que representam, por exemplo, custos de se transmitir informação entre localidades. São corretas as afirmações: Resposta Selecionada: d. I, e III. Pergunta 4 0,5 em 0,5 pontos A respeito do algoritmo concebido por Stephen Warshal e implementado por Robert Floyd, é incorreto afirmar: Resposta d. Selecionada: Seu desempenho em consumo de memória é combinatório. Pergunta 5 0,5 em 0,5 pontos Considere seguinte grafo e a matriz de adjacência modificada. Deseja-se caminho mínimo entre os nós A e F, empregando-se algoritmo de Dijkstra. 4 D 2 2 1 2 3 A F 4 2 3 E Em uma etapa inicial, 0 algoritmo inicializa conjunto de nós IN com:Resposta Selecionada: a. nó A. Pergunta 6 0,5 em 0,5 pontos Na etapa inicial do algoritmo de Dijkstra, mencionado na questão 5, os vetores distância d e nó anterior S, podem ser representados pela tabela: Resposta a. Selecionada: A D E F di 0 2 4 8 8 8 S A A A A A A Pergunta 7 0,5 em 0,5 pontos Na segunda iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F, nó selecionado para conjunto IN é porque: Resposta Selecionada: d. É de menor distância. Pergunta 8 0,5 em 0,5 pontos Na terceira iteração do algoritmo de Dijkstra para caminho mínimo entre os nós A e F: nó Cé selecionado. PORQUE Comparam-se as distâncias entre o nó A e os demais C, D, E e F, passando-se por B, ou não. Os valores do vetor de vetor S podem ser reescritos segundo menor valor resultante da comparação. Ao final obtém-se nó como aquele que apresenta menor valor no vetor d. Pode-se afirmar que:Resposta Selecionada: a. le são verdadeiras e justifica I. Pergunta 9 0,5 em 0,5 pontos Na quarta iteração do algoritmo de Dijkstra para caminho mínimo entre os nós A e F: I - São realizados os seguintes cálculos. d[D]= min(6, 3 +A[C, D]) =min(6,3+4)=6 d[E]= min(4, 3 +A[C, E]) =min(4,3+3)=4. d[F]= 3 +A[C, F]) - Os vetores e S são reescritos. III 0 nó E é selecionado. São corretas as afirmações: Resposta Selecionada: I, e III. e. Pergunta 10 0,5 em 0,5 pontos Na quinta iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F, nó F é selecionado. caminho mínimo obtido é: Resposta Selecionada: d. B, F. Sexta-feira, 28 de Março de 2025 23h35min57s GMT-03:00 OK