Unidade 1 - Introdução à teoria dos grafos

Prévia do material em texto

31/10/2022 22:09 UN 1 - Avaliação Objetiva: Revisão da tentativa
https://avap.multivix.edu.br/mod/quiz/review.php?attempt=2173279&cmid=1256062 1/6
Minhas Disciplinas / Meus cursos / 422467 / Unidade 1 - Introdução à teoria dos grafos
/ UN 1 - Avaliação Objetiva
Pesquisa Operacional II
Iniciado em segunda, 31 out 2022, 22:05
Estado Finalizada
Concluída em segunda, 31 out 2022, 22:09
Tempo
empregado
3 minutos 52 segundos
Avaliar 0,75 de um máximo de 0,75(100%)




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=19319
https://avap.multivix.edu.br/course/view.php?id=19319&section=2
https://avap.multivix.edu.br/mod/quiz/view.php?id=1256062
https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=19319
https://avap.multivix.edu.br/user/index.php?id=19319
https://avap.multivix.edu.br/course/view.php?id=19319&section=1
https://avap.multivix.edu.br/course/view.php?id=19319&section=2
https://avap.multivix.edu.br/course/view.php?id=19319&section=3
https://avap.multivix.edu.br/course/view.php?id=19319&section=4
https://avap.multivix.edu.br/course/view.php?id=19319&section=5
https://avap.multivix.edu.br/course/view.php?id=19319&section=6
https://avap.multivix.edu.br/course/view.php?id=19319&section=7
https://avap.multivix.edu.br/course/view.php?id=19319&section=8
https://avap.multivix.edu.br/course/view.php?id=19319&section=9
https://avap.multivix.edu.br/course/view.php?id=19319&section=10
https://avap.multivix.edu.br/course/view.php?id=19319&section=11
https://avap.multivix.edu.br/course/view.php?id=19319&section=12
https://avap.multivix.edu.br/course/view.php?id=19319&section=13
https://avap.multivix.edu.br/hooks/portal/
https://avap.multivix.edu.br/mod/page/view.php?id=1252%2F%22%20target%3D%22_blank
https://avap.multivix.edu.br/calendar/view.php/
https://avap.multivix.edu.br/
31/10/2022 22:09 UN 1 - Avaliação Objetiva: Revisão da tentativa
https://avap.multivix.edu.br/mod/quiz/review.php?attempt=2173279&cmid=1256062 2/6
Questão 1
Correto
Atingiu 0,15 de 0,15
Melodias, quando traçadas como funções de tempo em um grá�co, nos permitem a visualização de suas
características lineares, o que chamamos de curva ou per�l melódico. Porém, suas características (reservadas) e
singulares somente são reveladas quando a analisamos sob a perspectiva da categoria temporal. Pela natureza
de seus encadeamentos, uma melodia pode ser representada através de um grafo direcional. Como exemplo,
vejamos a �gura a seguir que mostra o “movimento” e o “grafo” do primeiro movimento da Sexta Sinfonia de
Ludwig van Beethoven.
Figura: Beethoven, Sinfonia nº 6, Op. 68, Grafo do Tema do 1º Movimento
Fonte: Athayde (2020).
#PraCegoVer: A �gura representa uma linha de partitura musical com algumas notas, com correspondente grafo
que modela a natureza de seus encadeamentos. Os vértices A4, B3, G4, C5, D5, C4, e F4 correspondem às alturas
das notas musicais, e as arestas correspondem aos encadeamentos entre os vértices. O grafo é direcionado. O
vértice G4 possui duas arestas de saída, sendo uma aresta com peso 7 que o conecta ao C4 e outra com peso 10
ligando ao A4. Ainda do G4 chegam duas arestas, uma de F4 com peso 9, outra de A4 com extensão de 6 a 13. Do
vértice C4 parte uma aresta de peso 8 em direção a F4. De A4 parte uma aresta de extensão 1-11 para B4 e chega
de B4 para A4 uma de extensão 5-12. De B4 parte uma aresta de peso 2 para D5, de D5 uma aresta de peso 3 para
C5, de C5 uma aresta de peso 4 para B4.
ATHAYDE, E. M. Teoria dos grafos aplicada à análise musical. 2020. Dissertação (Mestrado em Música) –
Universidade Federal de Minas Gerais, Belo Horizonte, 2020. Disponível em:
https://repositorio.ufmg.br/bitstream/1843/36407/4/ATHAYDE%2C%20Eduardo%20de%20Markus_Teoria%20dos%20Grafo
Acesso em: 18 nov. 2021.
O grafo do tema pertence a uma categoria particular de grafos denominada kayak paddle graph. Um grafo kayak
paddle KP(k, m, l) é o grafo obtido unindo os circuitos C e C por meio de um caminho de comprimento l[...].  Os
dois circuitos são caminhos obrigatórios, visto que se trata de um grafo direcional. Os dois circuitos são
conectados pelo vértice correspondente à nota Lá, nota inicial do tema.
A respeito de conceitos de grafos e caminhos, é correto a�rmar que:
a. Um percurso é considerado trivial se não possui arestas paralelas e pelo menos um laço.
b. Um caminho que começa e termina no mesmo vértice é chamado caminho fechado ou ciclo. Um
caminho que não é fechado é chamado caminho aberto.

c. Se duas (ou mais) arestas de G têm os mesmos vértices-extremidade, essas arestas são chamadas de
arestas laços.
d. Um vértice de um grafo é um vértice par ou ímpar se o seu grau for um número ímpar ou par,
respectivamente.
e. Um caminho é um passeio no qual qualquer vértice é repetido. Consequentemente, em um caminho, as
k m




















https://repositorio.ufmg.br/bitstream/1843/36407/4/ATHAYDE%2C%20Eduardo%20de%20Markus_Teoria%20dos%20Grafos%20aplicada%20%C3%A0%20an%C3%A1lise%20musical_%28Belo%20Horizonte%2C%202020%29.pdf
https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=19319
https://avap.multivix.edu.br/user/index.php?id=19319
https://avap.multivix.edu.br/course/view.php?id=19319&section=1
https://avap.multivix.edu.br/course/view.php?id=19319&section=2
https://avap.multivix.edu.br/course/view.php?id=19319&section=3
https://avap.multivix.edu.br/course/view.php?id=19319&section=4
https://avap.multivix.edu.br/course/view.php?id=19319&section=5
https://avap.multivix.edu.br/course/view.php?id=19319&section=6
https://avap.multivix.edu.br/course/view.php?id=19319&section=7
https://avap.multivix.edu.br/course/view.php?id=19319&section=8
https://avap.multivix.edu.br/course/view.php?id=19319&section=9
https://avap.multivix.edu.br/course/view.php?id=19319&section=10
https://avap.multivix.edu.br/course/view.php?id=19319&section=11
https://avap.multivix.edu.br/course/view.php?id=19319&section=12
https://avap.multivix.edu.br/course/view.php?id=19319&section=13
https://avap.multivix.edu.br/hooks/portal/
https://avap.multivix.edu.br/mod/page/view.php?id=1252%2F%22%20target%3D%22_blank
https://avap.multivix.edu.br/calendar/view.php/
https://avap.multivix.edu.br/
31/10/2022 22:09 UN 1 - Avaliação Objetiva: Revisão da tentativa
https://avap.multivix.edu.br/mod/quiz/review.php?attempt=2173279&cmid=1256062 3/6
Questão 2
Correto
Atingiu 0,15 de 0,15
aresta podem ser repetidas, o que garante que todo caminho é uma trilha.
Sua resposta está correta.
Um algoritmo pode ser usado para caminhar pela estrutura e retornar informações úteis para a resolução do
problema. Uma estrutura de links do tipo “Wikis” é um modelo que pode ser representado por essa categoria de
algoritmo, ou seja, os arcos são os artigos e “existe um arco do artigo A para o artigo B se e somente se A contém
um link para B”. Esse modelo de algoritmo concebe o espaço geográ�co como um conjunto de vértices,
conectados por arestas, em que ambos possuem atributos. Um dos atrativos do modelo de redes é o suporte
matemático da Teoria dos Grafos. A respeito de conceitos dessa teoria, julgue os itens que seguem.
I - Em um grafo direcionado, cada aresta geralmente é referenciada como arco, tem uma direção associada a ela.
II - Todo grafo tem um número in�nito de arestas e vértices associados a ele.
III - Para qualquer grafo G, um pseudografo completo de G é chamado de clique de G.
IV - Um grafo é chamado simples se não tem loops e não tem arestas paralelas.
É correto apenas o que se a�rma em:
a. I.
b. I e IV. 
c. III.
d. II e III.
e. IV e III.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=19319
https://avap.multivix.edu.br/user/index.php?id=19319
https://avap.multivix.edu.br/course/view.php?id=19319&section=1
https://avap.multivix.edu.br/course/view.php?id=19319&section=2https://avap.multivix.edu.br/course/view.php?id=19319&section=3
https://avap.multivix.edu.br/course/view.php?id=19319&section=4
https://avap.multivix.edu.br/course/view.php?id=19319&section=5
https://avap.multivix.edu.br/course/view.php?id=19319&section=6
https://avap.multivix.edu.br/course/view.php?id=19319&section=7
https://avap.multivix.edu.br/course/view.php?id=19319&section=8
https://avap.multivix.edu.br/course/view.php?id=19319&section=9
https://avap.multivix.edu.br/course/view.php?id=19319&section=10
https://avap.multivix.edu.br/course/view.php?id=19319&section=11
https://avap.multivix.edu.br/course/view.php?id=19319&section=12
https://avap.multivix.edu.br/course/view.php?id=19319&section=13
https://avap.multivix.edu.br/hooks/portal/
https://avap.multivix.edu.br/mod/page/view.php?id=1252%2F%22%20target%3D%22_blank
https://avap.multivix.edu.br/calendar/view.php/
https://avap.multivix.edu.br/
31/10/2022 22:09 UN 1 - Avaliação Objetiva: Revisão da tentativa
https://avap.multivix.edu.br/mod/quiz/review.php?attempt=2173279&cmid=1256062 4/6
Questão 3
Correto
Atingiu 0,15 de 0,15
Um caso clássico na Teoria dos Grafos é o problema da raposa, da galinha e do milho. O problema consiste em:
um fazendeiro precisa levar uma galinha, uma raposa e um saco de milho de uma margem de um rio para a
outra. Ele dispõe de um pequeno barco, que só o permite levar consigo um item de cada vez. Mas ele deve
providenciar, durante todo o processo, que a raposa jamais �que a sós com a galinha, tampouco a galinha com o
saco de milho (por razões óbvias). O grafo que representa esse caso é:
a. Direcionado. 
b. Vazio.
c. Ponderado.
d. Desconexo.
e. Bipartido.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=19319
https://avap.multivix.edu.br/user/index.php?id=19319
https://avap.multivix.edu.br/course/view.php?id=19319&section=1
https://avap.multivix.edu.br/course/view.php?id=19319&section=2
https://avap.multivix.edu.br/course/view.php?id=19319&section=3
https://avap.multivix.edu.br/course/view.php?id=19319&section=4
https://avap.multivix.edu.br/course/view.php?id=19319&section=5
https://avap.multivix.edu.br/course/view.php?id=19319&section=6
https://avap.multivix.edu.br/course/view.php?id=19319&section=7
https://avap.multivix.edu.br/course/view.php?id=19319&section=8
https://avap.multivix.edu.br/course/view.php?id=19319&section=9
https://avap.multivix.edu.br/course/view.php?id=19319&section=10
https://avap.multivix.edu.br/course/view.php?id=19319&section=11
https://avap.multivix.edu.br/course/view.php?id=19319&section=12
https://avap.multivix.edu.br/course/view.php?id=19319&section=13
https://avap.multivix.edu.br/hooks/portal/
https://avap.multivix.edu.br/mod/page/view.php?id=1252%2F%22%20target%3D%22_blank
https://avap.multivix.edu.br/calendar/view.php/
https://avap.multivix.edu.br/
31/10/2022 22:09 UN 1 - Avaliação Objetiva: Revisão da tentativa
https://avap.multivix.edu.br/mod/quiz/review.php?attempt=2173279&cmid=1256062 5/6
Questão 4
Correto
Atingiu 0,15 de 0,15
Um grafo G (V, E) é determinado por um conjunto não vazio de vértices (V) e um subconjunto de pares de
vértices não ordenados, chamados arestas (E).
A �gura a seguir representa a possibilidade de voos de uma companhia aérea tal que V = {Viracopos, Bahia,
Con�ns, Galeão e Brasília} representa o conjunto de aeroportos (vértices), e E = {{Viracopos, Bahia}, {Bahia,
Con�ns}, {Con�ns, Galeão}, {Viracopos, Galeão}, {Con�ns, Brasília}} representa essas possíveis conexões (arestas)
entre os aeroportos.
Figura: Representação geométrica do grafo de conexões em aeroportos
Fonte: Elaborada pela autora (2021).
#PraCegoVer: A �gura representa um grafo de conexões entre os aeroportos de Brasília, Viracopos, Galeão,
Con�ns e Bahia. Os aeroportos fazem conexões de voo que são representadas pelas arestas. As seguintes
conexões são dadas. O aeroporto de Brasília faz conexão com o aeroporto de Con�ns, que por sua vez tem
conexão com os aeroportos Galeão e Bahia, e o aeroporto de Viracopos faz conexão com aeroportos Galeão e
Bahia. Nenhuma das arestas se cruzam.
Com base nas informações apresentadas, avalie as a�rmações a seguir:
I. Con�ns é adjacente a Viracopos.
II. Viracopos possui valência igual a 2.
III. Galeão é incidente em Con�ns e Viracopos.
IV. Bahia possui comprimento igual a 2.
É correto apenas o que se a�rma em:
a. I e II.
b. II e III. 
c. I e IV.
d. I, II e IV.
e. II, III e IV.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=19319
https://avap.multivix.edu.br/user/index.php?id=19319
https://avap.multivix.edu.br/course/view.php?id=19319&section=1
https://avap.multivix.edu.br/course/view.php?id=19319&section=2
https://avap.multivix.edu.br/course/view.php?id=19319&section=3
https://avap.multivix.edu.br/course/view.php?id=19319&section=4
https://avap.multivix.edu.br/course/view.php?id=19319&section=5
https://avap.multivix.edu.br/course/view.php?id=19319&section=6
https://avap.multivix.edu.br/course/view.php?id=19319&section=7
https://avap.multivix.edu.br/course/view.php?id=19319&section=8
https://avap.multivix.edu.br/course/view.php?id=19319&section=9
https://avap.multivix.edu.br/course/view.php?id=19319&section=10
https://avap.multivix.edu.br/course/view.php?id=19319&section=11
https://avap.multivix.edu.br/course/view.php?id=19319&section=12
https://avap.multivix.edu.br/course/view.php?id=19319&section=13
https://avap.multivix.edu.br/hooks/portal/
https://avap.multivix.edu.br/mod/page/view.php?id=1252%2F%22%20target%3D%22_blank
https://avap.multivix.edu.br/calendar/view.php/
https://avap.multivix.edu.br/
31/10/2022 22:09 UN 1 - Avaliação Objetiva: Revisão da tentativa
https://avap.multivix.edu.br/mod/quiz/review.php?attempt=2173279&cmid=1256062 6/6
Questão 5
Correto
Atingiu 0,15 de 0,15
A pesquisa sobre artigos cientí�cos é a base para a�rmações e novas pesquisas cientí�cas, por isso é uma prática
comum entre os pesquisadores e estudantes a consulta a bases de dados. Um algoritmo pode ser usado para
caminhar pela estrutura e retornar informações úteis para a resolução do problema. Uma estrutura de links do
tipo “Periódicos Capes” é um modelo que pode ser representado por essa categoria de algoritmo, ou seja, os
vértices são os artigos e “existe uma aresta do artigo X para o artigo Y se e somente se X contém um link para Y”.
As características relacionadas representam um algoritmo:
a. Genético.
b. Divisão e conquista.
c. Exploração de grafo. 
d. Programação dinâmica.
e. Reconhecimento de padrões.
Sua resposta está correta.
◄ Conteúdo online
Seguir para...
Conteúdo online ►




















https://avap.multivix.edu.br/mod/scorm/view.php?id=1256061&forceview=1
https://avap.multivix.edu.br/mod/scorm/view.php?id=1256063&forceview=1
https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=19319
https://avap.multivix.edu.br/user/index.php?id=19319
https://avap.multivix.edu.br/course/view.php?id=19319&section=1
https://avap.multivix.edu.br/course/view.php?id=19319&section=2
https://avap.multivix.edu.br/course/view.php?id=19319&section=3
https://avap.multivix.edu.br/course/view.php?id=19319&section=4
https://avap.multivix.edu.br/course/view.php?id=19319&section=5
https://avap.multivix.edu.br/course/view.php?id=19319&section=6
https://avap.multivix.edu.br/course/view.php?id=19319&section=7
https://avap.multivix.edu.br/course/view.php?id=19319&section=8
https://avap.multivix.edu.br/course/view.php?id=19319&section=9
https://avap.multivix.edu.br/course/view.php?id=19319&section=10
https://avap.multivix.edu.br/course/view.php?id=19319&section=11
https://avap.multivix.edu.br/course/view.php?id=19319&section=12
https://avap.multivix.edu.br/course/view.php?id=19319&section=13
https://avap.multivix.edu.br/hooks/portal/https://avap.multivix.edu.br/mod/page/view.php?id=1252%2F%22%20target%3D%22_blank
https://avap.multivix.edu.br/calendar/view.php/
https://avap.multivix.edu.br/