QUESTIONÁRIO UNIDADE 1 - Teoria dos Grafos

Prévia do material em texto

5/30/23, 6:36 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95031753_1&course_id=_290757_1&content_id=_… 1/5
 Revisar envio do teste: QUESTIONÁRIO UNIDADE ITEORIA DOS GRAFOS 7939-30_43701_R_E1_20231 CONTEÚDO
Usuário
Curso TEORIA DOS GRAFOS
Teste QUESTIONÁRIO UNIDADE I
Iniciado 30/05/23 18:09
Enviado 30/05/23 18:35
Status Completada
Resultado da tentativa 5 em 5 pontos  
Tempo decorrido 26 minutos
Resultados exibidos Todas as respostas, Respostas enviadas, Respostas corretas, Comentários, Perguntas respondidas incorretamente
Pergunta 1
Resposta Selecionada: d. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere as seguintes asserções sobre o grafo representado gra�camente abaixo.
Fonte: 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 a�rmações:
I, II e III.
Apenas I e II.
Apenas I e III.
Apenas II e III.
I, II e III.
Apenas II.
Resposta: D.
Comentário: o grafo K32 é planar, pois é isomorfo ao seguinte grafo. Uma vez que apresenta dois nos ímpares, segundo
o Teorema de Euler, apresenta um caminho que passa por todas as arestas uma única vez.
Fonte: autoria própria.
Pergunta 2
Resposta
Selecionada:
c.
Respostas: a. 
b. 
Assinale a alternativa correta:
A busca em largura é geralmente implementada utilizando uma estrutura de dados �la, que armazena os vértices que
ainda não foram visitados em ordem de descoberta. Quando um vértice é descoberto, ele é adicionado à �la e quando é
visitado, é removido da �la.
O grafo K5 é planar.
Para investigar se um grafo apresenta caminho Hamiltoniano, emprega-se um algoritmo de desempenho O(n2).
UNIP EAD BIBLIOTECAS MURAL DO ALUNO TUTORIAISCONTEÚDOS ACADÊMICOS
0,5 em 0,5 pontos
0,5 em 0,5 pontos
http://company.blackboard.com/
https://ava.ead.unip.br/webapps/blackboard/execute/courseMain?course_id=_290757_1
https://ava.ead.unip.br/webapps/blackboard/content/listContent.jsp?course_id=_290757_1&content_id=_3419860_1&mode=reset
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_10_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_27_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_47_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_29_1
https://ava.ead.unip.br/webapps/portal/execute/tabs/tabAction?tab_tab_group_id=_25_1
https://ava.ead.unip.br/webapps/login/?action=logout
5/30/23, 6:36 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95031753_1&course_id=_290757_1&content_id=_… 2/5
c.
d. 
e. 
Comentário da resposta:
A busca em largura é geralmente implementada utilizando uma estrutura de dados �la, que armazena os vértices que
ainda não foram visitados em ordem de descoberta. Quando um vértice é descoberto, ele é adicionado à �la e quando é
visitado, é removido da �la.
Um grafo é Euleriano se apresentar número par de nós ímpares.
Todo grafo planar é Hamiltoniano.
Resposta: C.
Comentário: trata-se de característica da busca em largura.
Pergunta 3
Resposta Selecionada: a. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
O grafo K33 é representado gra�camente como se segue:
Fonte: autoria própria.
 
Assinale a alternativa que apresenta uma a�rmação incorreta.
Trata-se de um grafo planar.
Trata-se de um grafo planar.
Trata-se de um grafo conexo.
Todos os nós apresentam grau 3.
Não existe um caminho que passa por todas as arestas uma única vez.
Apresenta o caminho: 1-4-2-5-3-6-1. Dessa forma, apresenta um caminho Hamiltoniano.
Resposta: A.
Comentário: o grafo K33 não é planar, pois não é possível representá-lo gra�camente em um plano de tal forma
queque as arestas se interceptem apenas nos vértices.
Pergunta 4
Resposta Selecionada: c. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Assinale a alternativa que apresenta o número de regiões que o seguinte grafo divide o plano.
Fonte: autoria própria.
7
8
13
7
9
6
Resposta: C.
Comentário: trata-se de um grafo planar com 8 nohs e 13 arestas. Por se tratar de um grafo planar, vale a relação: n-
a+r=2.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
5/30/23, 6:36 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95031753_1&course_id=_290757_1&content_id=_… 3/5
Pergunta 5
Resposta
Selecionada:
b.
Respostas: a.
b.
c. 
d.
e.
Comentário da resposta:
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.
Para um grafo planar conexo e simples com n nós e a arestas e se n < 3 e se não existem ciclos de comprimento 3,
então; a > 2n – 4.
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.
Para um grafo planar simples e conexo, se o número de nós é n, tal que n ≥ 3 então a > 3n – 6.
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.
Não existe nenhuma relação entre o número de nós, arestas e regiões que um grafo planar, simples e conexo divide o
plano.
Resposta: B.
Comentário: trata-se de um teorema e, portanto, passível de ser provado como verdadeiro.
Pergunta 6
Resposta Selecionada:
c. 
Respostas:
a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere o grafo apresentado na �gura que se segue:
Fonte: autoria própria.
 
Se se acrescentar ao grafo, uma aresta A6, tal que g(A6)=(2,4), pode se a�rmar que a matriz adjacência para o dígrafo é:
M = 
M = 
M = 
M = 
M = 
M = 
Resposta: C.
Comentário: para o dígrafo resultante da adição da aresta A6, vale a função g, tal que: g(A1)=(1,2), g(A2)=(2,3), g(A3)=
(3,4) (A5)=(4,3), g(A4)=(3,1) e g(A6)=(2,4).
Pergunta 7
0,5 em 0,5 pontos
0,5 em 0,5 pontos
0,5 em 0,5 pontos
5/30/23, 6:36 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95031753_1&course_id=_290757_1&content_id=_… 4/5
Resposta
Selecionada:
a. 
Respostas: a. 
b. 
c. 
d. 
e.
Comentário da
resposta:
Para a árvore representada na �gura seguinte, assinale a alternativa correta.
Fonte: autoria própria.
A altura da árvore é 2.
A altura da árvore é 2.
O percurso pós-ordem: +–73*y2 resulta na notação polonesa.
Percurso pré-ordem: 7–3+y*2 resulta na notação in�xa.
Percurso ordem simétrica: 73–y2*+ resulta na notação polonesa reversa.
No percurso em pós-ordem, a raiz é a primeira a ser visitada a partir de todas as subárvores da esquerda para a
direita.
Resposta: A.
Comentário: a profundidade de um nó em uma árvore é o comprimento do caminho da raiz ao nó; a raiz tem
profundidade 0.A profundidade (altura) de uma árvore é a maior profundidade dos nós na árvore.
Pergunta 8
Resposta Selecionada: a. 
Respostas: a. 
b. 
c. 
d. 
e. 
Comentário da
resposta:
Considere o grafo representado na �gura 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
a, b, h, d, g, c, e, f
a, h, b, d, g, c, f, e
b, a, c, h, e, d, e, f, f
a, b, c, d, e, f, g, h
h, g, f, e, c, d, b, a
Resposta: A.
Comentário: a busca em nível começa em um nó arbitrário, anota todos os seus nós adjacentes e seguidamente os nós
adjacentes àqueles anteriormente encontrados, e assim por diante.
Pergunta 9
Resposta Selecionada: e. 
Respostas: a. 
b. 
c. 
Considere as seguintes asserções e seguidamente assinale a alternativa correta.
 
I. O problema do Circuito Hamiltoniano corresponde a veri�car se existe um circuito que percorre por todos os nós de um grafo uma única vez.
II. Encontrar um caminhoHamiltoniano em um grafo é um problema NP-completo, o que signi�ca que não há um algoritmo conhecido que
possa resolver o problema de forma e�ciente para todos os casos.
III. O algoritmo conhecido para resolver o problema do circuito Hamiltoniano é O(n!).
São corretas as a�rmações:
I, II e III.
Apenas I.
Apenas I e II.
Apenas I e III.
0,5 em 0,5 pontos
0,5 em 0,5 pontos
5/30/23, 6:36 PM Revisar envio do teste: QUESTIONÁRIO UNIDADE I – TEORIA ...
https://ava.ead.unip.br/webapps/assessment/review/review.jsp?attempt_id=_95031753_1&course_id=_290757_1&content_id=_… 5/5
Terça-feira, 30 de Maio de 2023 18h35min55s GMT-03:00
d. 
e. 
Comentário da
resposta:
Apenas II e III.
I, II e III.
Resposta E.
Comentário: o algoritmo conhecido para resolver o problema do circuito Hamiltoniano consiste em veri�car se cada uma das
permutações dos nós do grafo, constituem o caminho hamiltoniano. Assim na situação de pior caso é O(n!) e, portanto, não é
e�ciente. De fato, para um grafo de 10 nós, seriam necessárias na situação de pior caso mais de 3.000.000 de cálculos. Logo,
não é e�ciente. O desempenho é, pois, NP-Completo, ou seja, a solução e�ciente, polinomial, não é conhecida.
Pergunta 10
Resposta
Selecionada:
a.
Respostas: a.
b. 
c. 
d. 
e. 
Comentário da resposta:
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.
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.
O grafo K32 não é simples.
Não existe solução para o problema do �uxo máximo.
O problema do caminho Euleriano é, assim como o problema do circuito Hamiltoniano de desempenho polinomial.
Dois grafos isomorfos podem apresentar números de nós distintos.
Resposta: A.
Comentário: trata-se da característica da ordenação topológica.
← OK
0,5 em 0,5 pontos