Grafos: Conceitos e Algoritmos

Prévia do material em texto

18/06/2023, 17:24 Questionário Online: Revisão da tentativa
www.unipvirtual.com.br/avaunip/mod/quiz/review.php?attempt=1496985&cmid=143951 1/6
- Minhas disciplinas - - -
   Bibliotecas Virtuais
Página inicial PS-B0599 Geral Questionário Online

http://www.unipvirtual.com.br/avaunip
http://www.unipvirtual.com.br/avaunip/
http://www.unipvirtual.com.br/avaunip/course/view.php?id=5371
http://www.unipvirtual.com.br/avaunip/course/view.php?id=5371#section-0
http://www.unipvirtual.com.br/avaunip/mod/quiz/view.php?id=143951
18/06/2023, 17:24 Questionário Online: Revisão da tentativa
www.unipvirtual.com.br/avaunip/mod/quiz/review.php?attempt=1496985&cmid=143951 2/6
Iniciado em domingo, 18 Jun 2023, 17:12
Estado Finalizada
Concluída em domingo, 18 Jun 2023, 17:23
Tempo
empregado
10 minutos 39 segundos
Avaliar 9,00 de um máximo de 10,00(90%)
Questão 1
Completo
Atingiu 1,00 de 1,00
(POSCOMP 2013, questão 37) Seja G o grafo representado pela figura a seguir.
Assinale a alternativa que apresenta, corretamente, o número cromático associado ao grafo.
Escolha uma opção:
a. 4
b. 5
c. 6
d. 7
e. 3
Questão 2
Completo
Atingiu 1,00 de 1,00
Considere as seguintes afirmações:
I. Um grafo com quatro nós ímpares, ainda, pode ser conexo;
II. Existe um Caminho de Euler em qualquer grafo com um número par de nós impares;
III. Existe um algoritmo com desempenho polinomial quadrático que testa a existência de um Caminho de Euler em um grafo com n nós. São
corretas as afirmações:
Escolha uma opção:
a. Apenas III;
b. Nenhuma das alternativas
c. Apenas II; 
18/06/2023, 17:24 Questionário Online: Revisão da tentativa
www.unipvirtual.com.br/avaunip/mod/quiz/review.php?attempt=1496985&cmid=143951 3/6
d. Apenas I e III.
e. Apenas I;
Questão 3
Completo
Atingiu 1,00 de 1,00
(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.
Escolha uma opção:
a. Floyd-Warshall.
b. Bellman-Ford.
c. Kruskal.
d. Prim.
e. Dijkstra.
Questão 4
Completo
Atingiu 1,00 de 1,00
(POSCOMP 2014 questão 36). Considerando que um grafo possui n vértices e m arestas, assinale a alternativa que apresenta, corretamente, um
grafo planar.
Escolha uma opção:
a. n = 5, m = 10
b. n = 6, m = 15
c. n = 8, m = 12
d. n = 9, m = 22
e. n = 7, m = 21
Questão 5
Completo
Atingiu 1,00 de 1,00
Qual afirmação sobre grafos está INCORRETA
Escolha uma opção:
a. Nenhuma das alternativas
b. O grafo pode ser expresso como tripla ordenada (N,A,g)
c. Um grafo possui um conjunto de arcos
d. Um grafo é um conjunto não vazio de nós
e. O número de nós e arestas é sempre infinito
Questão 6

18/06/2023, 17:24 Questionário Online: Revisão da tentativa
www.unipvirtual.com.br/avaunip/mod/quiz/review.php?attempt=1496985&cmid=143951 4/6
Completo
Atingiu 1,00 de 1,00
O que podemos definir como um caminho de Euler
Escolha uma opção:
a. É um caminho que usa cada arco tres vezes
b. Nenhuma das alternativas
c. É um caminho que usa cada arco duas vezes
d. É um caminho que usa cada arco uma única vez
e. É um caminho que não usa arco
Questão 7
Completo
Atingiu 0,00 de 1,00
(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.
Figura 2. Fonte: INEP – Enade 2021
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.
Escolha uma opção:
a. A: 5 B: 7 C: 8 D: 0 E: 4 F: 1 G: 2
b. A: 5 B: 9 C: -1 D: 0 E: 5 F: 1 G: -1
c. A: 5 B: 6 C: 8 D: 0 E: 3 F: 1 G: 2
d. A: 5 B: 6 C: 10 D: 0 E: 4 F: 1 G: -1
e. A: 5 B: 9 C: -1 D: 0 E: 4 F: 1 G: 2
Questão 8
Completo
Atingiu 1,00 de 1,00
Considere as seguintes afirmações:
I. Em um grafo de n vértices e m arestas, a matriz de adjacência modificada apresenta n linhas e m colunas;
II C id i it di it l t ló i d 2 t d I i d j t t há i t li õ bl t i

18/06/2023, 17:24 Questionário Online: Revisão da tentativa
www.unipvirtual.com.br/avaunip/mod/quiz/review.php?attempt=1496985&cmid=143951 5/6
II. Considere um circuito digital com n portas lógicas de 2 entradas. Imagine-se que se deseja testar se há interligações com problemas, tais
como curto-circuito ou interconexões com trilhas em aberto. Se considerarmos cada porta como nós de grafos e as interligações entre as
portas como arestas é possível afirmar, em tempo polinomial, se existe um caminho que passa por todos os nós uma única vez;
III. O Algoritmo de Prim permite encontrar a árvore geradora mínima em um grafo simples e conexo.
Escolha uma opção:
a. Apenas II e III.
b. Nenhuma das alternativas
c. Apenas I e II
d. Apenas I e III.
e. I, II e III.
Questão 9
Completo
Atingiu 1,00 de 1,00
Considere as seguintes afirmações:
I. Em um grafo de n vértices e m arestas, a matriz de adjacência modificada apresenta n linhas e m colunas;
II. Considere um circuito digital com n portas lógicas de 2 entradas. Imagine-se que se deseja testar se há interligações com problemas, tais
como curto-circuito ou interconexões com trilhas em aberto. Se considerarmos cada porta como nós de grafos e as interligações entre as
portas como arestas é possível afirmar, em tempo polinomial, se existe um caminho que passa por todos os nós uma única vez;
III. O Algoritmo de Prim permite encontrar a árvore geradora mínima em um grafo simples e conexo.
São corretas as afirmações:
Escolha uma opção:
a. I, II e III.
b. Apenas I.
c. Apenas I e II.
d. Apenas II e III.
e. Apenas I e III.
Questão 10
Completo
Atingiu 1,00 de 1,00
A respeito do grafo K , pode-se afirmar que:
I – Trata-se de um grafo planar.
II – Trata-se de um grafo simples.
III – Trata-se de um grafo conexo.
São corretas as asserções:
Escolha uma opção:
a. Apenas II.
b. Apenas I e II.
c. I, II e III.
d. Apenas III.
e. Apenas I.
3,2

18/06/2023, 17:24 Questionário Online: Revisão da tentativa
www.unipvirtual.com.br/avaunip/mod/quiz/review.php?attempt=1496985&cmid=143951 6/6
Terminar revisão
Plano de Ensino Seguir para... Slides de Aula 

http://www.unipvirtual.com.br/avaunip/mod/quiz/view.php?id=143951
http://www.unipvirtual.com.br/avaunip/mod/page/view.php?id=143950&forceview=1
http://www.unipvirtual.com.br/avaunip/mod/url/view.php?id=143953&forceview=1