Questões sobre Grafos

Prévia do material em texto

Iniciado em domingo, 18 Jun 2023, 15:00
Estado Finalizada
Concluída em domingo, 18 Jun 2023, 15:13
Tempo
empregado
13 minutos 25 segundos
Avaliar 10,00 de um máximo de 10,00(100%)
Questão 1
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 = 9, m = 22
b. n = 5, m = 10
c. n = 8, m = 12
d. n = 6, m = 15
e. n = 7, m = 21
Questão 2
Completo
Atingiu 1,00 de 1,00
Considere o grafo abaixo.
A respeito do grafo, pode-se afirmar que:
Escolha uma opção:
a. Trata-se de um grafo par-ímpar.
b. O grafo é não planar.
c. É completo e denomina-se K .
d. Apresenta 3 nós pares e 2 nós ímpares.
e. É bipartido completo e denomina-se K .
Questão 3
5
5

Questão 3
Completo
Atingiu 1,00 de 1,00
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:
Escolha uma opção:
a. Apenas II e III.
b. Apenas I e II.
c. Apenas III.
d. Apenas II.
e. I, II, III.
Questão 4
Completo
Atingiu 1,00 de 1,00
(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.
Escolha uma opção:
a. I-C; II-B; III-A.
b. I-B; II-A; III-C.
c. I-B; II-C; III-A.
d. I-A; II-B; III-C.
e. I-A; II-C; II-B.
Questão 5
Completo
Atingiu 1,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: 6 C: 8 D: 0 E: 3 F: 1 G: 2
b. A: 5 B: 9 C: -1 D: 0 E: 5 F: 1 G: -1
c. A: 5 B: 9 C: -1 D: 0 E: 4 F: 1 G: 2
d. A: 5 B: 7 C: 8 D: 0 E: 4 F: 1 G: 2
e. A: 5 B: 6 C: 10 D: 0 E: 4 F: 1 G: -1
Questão 6
Completo
Atingiu 1,00 de 1,00
Considere as seguintes asserções:
I – Em muitas áreas da computação, é conveniente modelar um algoritmo ou um programa usando um grafo.
II – Instalações de fornecimento de luz, água e esgoto em uma instalação podem ser representadas por um grafo.
III – Uma rede de radares instalada sobre uma determinada rede de avenidas ou ruas pode ser representada por um grafo.
São corretas as afirmações:
Escolha uma opção:
a. I, II e III.
b. Apenas I.
c. Apenas I e III.
d. Apenas II.
e. Apenas III.
Questão 7
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.
3,2

São corretas as asserções:
Escolha uma opção:
a. Apenas III.
b. Apenas II.
c. Apenas I e II.
d. Apenas I.
e. I, II e III.
Questão 8
Completo
Atingiu 1,00 de 1,00
Considere as seguintes afirmações:
I – Dois grafos não são isomorfos se um tem mais nohs que o outro.
II – Dois grafos não são isomorfos se um tem mais arcos que o outro.
III – Dois grafos não são isomorfos se um tem um ciclo e o outro não.
São corretas as afirmações:
Escolha uma opção:
a. Apenas I e II.
b. Apenas II e III.
c. I, II e III.
d. Apenas I e III.
e. Apenas III.
Questão 9
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 II;
b. Apenas III;
c. Apenas I e III.
d. Apenas I;
e. I, II e III.
Questão 10
Completo

p
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 duas vezes
b. É um caminho que não usa arco
c. É um caminho que usa cada arco uma única vez
d. Nenhuma das alternativas
e. É um caminho que usa cada arco tres vezes
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