Teoria dos grafos Questionário 1 AVA

Prévia do material em texto

• Pergunta 1 
0,5 em 0,5 pontos 
 
Veja a figura 1. 
 
 
 
 
 
 
Considere as asserções: 
I – O grafo apresenta um caminho de Euler 
PORQUE 
II – O grafo é conexo e apresenta 2 nós ímpares. 
 
Resposta Selecionada: a. 
I e II são verdadeiras e II justifica I. 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
Considere as seguintes afirmações: 
 
I – O número de nós ímpares em qualquer grafo é par. 
II – Existe um critério simples para determinar se existem caminhos de Euler em um grafo. 
III – Existe um caminho de Euler em qualquer grafo com um número par de nós ímpares. 
 
São corretas as asserções: 
 
Resposta Selecionada: c. 
Apenas I e II. 
 
 
• Pergunta 3 
0,5 em 0,5 pontos 
 
(Enade 2021, questão 34). O algoritmo de Dijkstra para o problema do caminho mínimo em dígrafos com 
pesos utiliza uma fila de prioridades de vértices, na qual as prioridades são uma estimativa do custo final. A 
cada iteração, um vértice é retirado da fila e os arcos que começam nesse vértice são analisados. Considere o 
seguinte grafo, no qual deseja-se conhecer o custo de um caminho mínimo para cada vértice, a partir do 
vértice D. Considere que -1 representa um custo “infinito”, ou seja, nenhum caminho até o vértice foi até o 
momento descoberto. 
 
 
 
 
 
 
Com base nas informações e no grafo apresentados, assinale a alternativa que representa a estimativa de 
custo após duas iterações do algoritmo. 
Resposta Selecionada: c. 
A: 5 B: 9 C: -1 D: 0 E: 4 F: 1 G: 2 
 
 
• Pergunta 4 
0,5 em 0,5 pontos 
 
(Fundamentada na questão 35 POSCOMP 2012). Concernente aos algoritmos em grafos, relacione a coluna 1 
com a coluna 2. 
 
Coluna 1: 
I – Árvore Geradora Mínima (Prim) 
II – Caminho Mais Curto (Dijkstra) 
III – Árvore Geradora Mínima (Kruskal) 
 
Coluna 2: 
(A)Toma como entrada um grafo não orientado com pesos nas arestas, ordena as arestas por peso e escolhe 
as arestas de forma a não fechar ciclos para resolver o problema. 
(B) Toma como entrada um grafo não orientado com pesos nas arestas, utiliza basicamente busca em 
largura escolhendo arestas de menor peso para resolver o problema. 
(C)Toma como entrada um grafo não orientado com pesos nas arestas, utiliza basicamente busca em largura 
escolhendo distâncias acumuladas de menor peso para resolver o problema. 
 
Resposta Selecionada: a. 
I-B; II-C; III-A. 
 
 
• Pergunta 5 
0,5 em 0,5 pontos 
 
(POSCOMP 2014, questão 37). Assinale a alternativa que apresenta, corretamente, o algoritmo utilizado 
para determinar o caminho mínimo entre todos os pares de vértices de um grafo. 
Resposta Selecionada: b. 
Floyd-Warshall. 
 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
Em 1957, Prim apresenta o algoritmo da árvore geradora mínima em um artigo intitulado “Shortest 
Connections Networks and Some Generalizations”. Para ilustrar a computação do algoritmo faz uso de um 
grafo cuja matriz de adjacência modificada é como se segue: 
 
 
 
 
Considerando que o primeiro nó da árvore geradora mínima selecionado seja o nó 1, assinale a alternativa 
que representa a sequência em que os nós da árvore são selecionados: 
 
Resposta Selecionada: e. 
(1, 4, 3, 6, 2, 5) 
 
 
• Pergunta 7 
0 em 0,5 pontos 
 
Considere o grafo apresentado na figura 3 que se segue: 
 
 
 
 
Ao se aplicar o Algoritmo de Kruskal para encontrar uma árvore geradora de peso mínimo, a soma dos 
pesos vale: 
 
Resposta Selecionada: d. 
17 
 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
(POSCOMP, 2009, questão 30 [FUN]). Considere o algoritmo de busca em largura em grafos. Dado o grafo a 
seguir e o vértice A como ponto de partida, a ordem em que os vértices são descobertos é dada por: 
 
 
 
 
 
Resposta Selecionada: a. 
A B C D E F 
 
 
• Pergunta 9 
0,5 em 0,5 pontos 
O seguinte exercício foi fundamentado em Gersting, J. L. exercício 11, capítulo 7.3, 7. ed). Considere o grafo 
representado na figura 6. Deseja-se usar o algoritmo de Bellman-Ford para encontrar o caminho da origem 
 
 
nó 2 para qualquer outro nó. Assinale a alternativa que apresenta os valores de d (distância) e s (origem) 
após 2 iterações do algoritmo sobre a matriz de adjacência modificada. 
 
 
 
 
 
 
Resposta 
Selecionada: 
c. 
 
 1 2 3 4 5 6 7 8 
d 3 0 2 3 3 4 1 2 
s 2 - 2 3 8 1 2 7 
 
 
 
• Pergunta 10 
0 em 0,5 pontos 
 
Considere as seguintes afirmações: 
 
 
I – O algoritmo de Dijkstra, também denominado Caminho Mínimo, encontra o caminho da distância mínima 
entre dois nós dados: x e y. 
II – O Algoritmo de Floyd calcula caminho mínimo entre todos os pares para encontrar as distâncias 
correspondentes a todos os caminhos mínimos. 
III – O algoritmo de Floyd é de complexidade computacional O(n3). 
 
São corretas as afirmações: 
 
Resposta Selecionada: e. 
Apenas I, II e III.