TEORIA DOS GRAFOS (QUESTIONÁRIO UNIDADE I)

Prévia do material em texto

Revisar envio do teste: QUESTIONÁRIO UNIDADE I
TEORIA DOS GRAFOS D66B_14201_R_20251 CONTEÚDO
Usuário PEDRO GUSTAVO FIGUEIRA BEZERRA
Curso TEORIA DOS GRAFOS
Teste QUESTIONÁRIO UNIDADE I
Iniciado 12/03/25 13:02
Enviado 12/03/25 13:14
Status Completada
Resultado da tentativa 5 em 5 pontos  
Tempo decorrido 11 minutos
Resultados exibidos Respostas enviadas, Perguntas respondidas incorretamente
Pergunta 1
Resposta Selecionada: d. 
Considere as seguintes asserções sobre o grafo representado graficamente abaixo.
                                                                                                                                                        F
onte: autoria própria.
 
I. Trata-se do grafo K32.
II. O grafo é planar.
III. Existe um caminho que passa por todas as arestas uma única vez.
São corretas as afirmações:
I, II e III.
Pergunta 2
UNIP BIBLIOTECAS MURAL DO ALUNOCONTEÚDOS ACADÊMICOS
0,5 em 0,5 pontos
0,5 em 0,5 pontos
12/03/2025, 13:14 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_111199688_1&course_id=_390733_1&content_id=_4390988_1&retu… 1/5
Resposta
Selecionada:
c.
Assinale a alternativa correta:
A busca em largura é geralmente implementada utilizando uma
estrutura de dados fila, que armazena os vértices que ainda não
foram visitados em ordem de descoberta. Quando um vértice é
descoberto, ele é adicionado à fila e quando é visitado, é removido
da fila.
Pergunta 3
Resposta Selecionada: a. 
O grafo K33 é representado graficamente como se segue:
 
                                                                                                                                                       
           Fonte: autoria própria.
 
Assinale a alternativa que apresenta uma afirmação incorreta.
Trata-se de um grafo planar.
Pergunta 4
Assinale a alternativa que apresenta o número de regiões que o seguinte grafo
divide o plano.
 
 
0,5 em 0,5 pontos
0,5 em 0,5 pontos
12/03/2025, 13:14 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_111199688_1&course_id=_390733_1&content_id=_4390988_1&retu… 2/5
Resposta Selecionada: c. 
                                                                                                                                  Fonte:
autoria própria.
7
Pergunta 5
Resposta
Selecionada:
b.
Assinale a alternativa correta.
Para um grafo planar simples e conexo, com n nós e a arestas,
se a representação planar divide o plano em r regiões, então: n-
a+r=2.
Pergunta 6
Resposta Selecionada:
c. 
Considere o grafo apresentado na figura que se segue:
 
 
                                                                Fonte: autoria própria.
 
Se se acrescentar ao grafo, uma aresta A6, tal que g(A6)=(2,4), pode se afirmar que a
matriz adjacência para o dígrafo é:
Pergunta 7
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
12/03/2025, 13:14 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_111199688_1&course_id=_390733_1&content_id=_4390988_1&retu… 3/5
Resposta Selecionada: a. 
Para a árvore representada na figura seguinte, assinale a alternativa correta.
 
 
 
                                                                 Fonte: autoria própria.
A altura da árvore é 2.
Pergunta 8
Resposta Selecionada: a. 
Considere o grafo representado na figura seguinte. Assinale a alternativa que
representa o percurso em nível no mesmo.
 
 
                                                               Fonte: autoria própria.
a, b, h, d, g, c, e, f
Pergunta 9
Considere as seguintes asserções e seguidamente assinale a alternativa correta.
 
I. O problema do Circuito Hamiltoniano corresponde a verificar se existe um circuito
que percorre por todos os nós de um grafo uma única vez.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
12/03/2025, 13:14 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_111199688_1&course_id=_390733_1&content_id=_4390988_1&retu… 4/5
Quarta-feira, 12 de Março de 2025 13h14min36s BRT
Resposta Selecionada: e. 
II. Encontrar um caminho Hamiltoniano em um grafo é um problema NP-completo, o
que significa que não há um algoritmo conhecido que possa resolver o problema de
forma eficiente para todos os casos.
III. O algoritmo conhecido para resolver o problema do circuito Hamiltoniano é O(n!).
São corretas as afirmações:
I, II e III.
Pergunta 10
Resposta
Selecionada:
a.
Assinale a alternativa correta.
Uma ordenação topológica é uma ordenação linear dos vértices
do grafo que respeita a direção das arestas. Em outras palavras, se
existe uma aresta direcionada do vértice u para o vértice v, então
u aparece antes de v na ordenação.
← OK
0,5 em 0,5 pontos
12/03/2025, 13:14 Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_111199688_1&course_id=_390733_1&content_id=_4390988_1&retu… 5/5