UN 1 - Avaliação Objetiva_ Revisão da tentativa Bia 2

Prévia do material em texto

Minhas Disciplinas / Meus cursos / 422467 / Unidade 1 - Introdução à teoria dos grafos
/ UN 1 - Avaliação Objetiva
Pesquisa Operacional II
Iniciado em domingo, 29 mai 2022, 22:29
Estado Finalizada
Concluída em domingo, 29 mai 2022, 22:33
Tempo
empregado
3 minutos 28 segundos
Avaliar 0,75 de um máximo de 0,75(100%)
Questão 1
Correto
Atingiu 0,15 de 0,15
O grafo G = (V,E), rotulado conforme a �gura a seguir, representa a distribuição de tarefas em uma linha de
produção de uma cervejaria. Cada vértice indica uma etapa do processo de produção e engarrafamento da
cerveja edição especial de aniversário.
Figura: Grafo G(V,E) rotulado
Fonte: Elaborada pela autora (2021).
#PraCegoVer: A �gura representa o grafo da distribuição de tarefas em uma linha de produção de uma cervejaria,
em que este é rotulado com 6 vértices enumerados de 1 a 6. O vértice 1 se conecta aos vértices 2, 4 e 6. O vértice 2
se conecta apenas ao vértice 3, que, por sua vez, se conecta aos vértices 4 e 5. O vértice 4 conecta-se aos vértices
1, 3 (sendo aqui a mesma aresta que conecta o 3 ao 4) e 5.
Segundo a Teoria dos Grafos, um caminho simples é:
a. Uma sequência de arestas paralelas e com laços.
b. Uma sequência de arestas em que não há repetição de arestas ou vértices. 
c. Qualquer sequência de arestas, desde que seja um ciclo.
d. Uma sequência de arestas que conectam vértices de grau 1.
e. Um ciclo formado por laços e vértices adjacentes de um mesmo grafo.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/mod/quiz/view.php?id=1043651
https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=14438
https://avap.multivix.edu.br/user/index.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=1
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/course/view.php?id=14438&section=3
https://avap.multivix.edu.br/course/view.php?id=14438&section=4
https://avap.multivix.edu.br/course/view.php?id=14438&section=5
https://avap.multivix.edu.br/course/view.php?id=14438&section=6
https://avap.multivix.edu.br/course/view.php?id=14438&section=7
https://avap.multivix.edu.br/course/view.php?id=14438&section=8
https://avap.multivix.edu.br/course/view.php?id=14438&section=9
https://avap.multivix.edu.br/course/view.php?id=14438&section=10
https://avap.multivix.edu.br/course/view.php?id=14438&section=11
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/local/staticpage/view.php?page=biblioteca
https://portalweb.multivix.edu.br/gabaritos/login.aspx
https://multivix.edu.br/office-365/
https://avap.multivix.edu.br/
Questão 2
Correto
Atingiu 0,15 de 0,15
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. IV e III.
b. II e III.
c. III.
d. I e IV. 
e. I e IV.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=14438
https://avap.multivix.edu.br/user/index.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=1
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/course/view.php?id=14438&section=3
https://avap.multivix.edu.br/course/view.php?id=14438&section=4
https://avap.multivix.edu.br/course/view.php?id=14438&section=5
https://avap.multivix.edu.br/course/view.php?id=14438&section=6
https://avap.multivix.edu.br/course/view.php?id=14438&section=7
https://avap.multivix.edu.br/course/view.php?id=14438&section=8
https://avap.multivix.edu.br/course/view.php?id=14438&section=9
https://avap.multivix.edu.br/course/view.php?id=14438&section=10
https://avap.multivix.edu.br/course/view.php?id=14438&section=11
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/local/staticpage/view.php?page=biblioteca
https://portalweb.multivix.edu.br/gabaritos/login.aspx
https://multivix.edu.br/office-365/
https://avap.multivix.edu.br/
Questão 3
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. Divisão e conquista.
b. Exploração de grafo. 
c. Programação dinâmica.
d. Reconhecimento de padrões.
e. Genético.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=14438
https://avap.multivix.edu.br/user/index.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=1
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/course/view.php?id=14438&section=3
https://avap.multivix.edu.br/course/view.php?id=14438&section=4
https://avap.multivix.edu.br/course/view.php?id=14438&section=5
https://avap.multivix.edu.br/course/view.php?id=14438&section=6
https://avap.multivix.edu.br/course/view.php?id=14438&section=7
https://avap.multivix.edu.br/course/view.php?id=14438&section=8
https://avap.multivix.edu.br/course/view.php?id=14438&section=9
https://avap.multivix.edu.br/course/view.php?id=14438&section=10
https://avap.multivix.edu.br/course/view.php?id=14438&section=11
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/local/staticpage/view.php?page=biblioteca
https://portalweb.multivix.edu.br/gabaritos/login.aspx
https://multivix.edu.br/office-365/
https://avap.multivix.edu.br/
Questão 4
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. Um vértice de um grafo é um vértice par ou ímpar se o seu grau for um número ímpar ou par,
respectivamente.
d. Um caminho é um passeio no qual qualquer vértice é repetido. Consequentemente, em um caminho, as
aresta podem ser repetidas, o que garante que todo caminho é uma trilha.
e. Se duas (ou mais) arestas de G têm os mesmos vértices-extremidade, essas arestas são chamadas de
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=14438
https://avap.multivix.edu.br/user/index.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=1
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/course/view.php?id=14438&section=3
https://avap.multivix.edu.br/course/view.php?id=14438&section=4
https://avap.multivix.edu.br/course/view.php?id=14438&section=5
https://avap.multivix.edu.br/course/view.php?id=14438&section=6
https://avap.multivix.edu.br/course/view.php?id=14438&section=7
https://avap.multivix.edu.br/course/view.php?id=14438&section=8
https://avap.multivix.edu.br/course/view.php?id=14438&section=9
https://avap.multivix.edu.br/course/view.php?id=14438&section=10
https://avap.multivix.edu.br/course/view.php?id=14438&section=11
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/local/staticpage/view.php?page=biblioteca
https://portalweb.multivix.edu.br/gabaritos/login.aspx
https://multivix.edu.br/office-365/
https://avap.multivix.edu.br/
arestas laços.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=14438
https://avap.multivix.edu.br/user/index.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=1
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/course/view.php?id=14438&section=3
https://avap.multivix.edu.br/course/view.php?id=14438&section=4
https://avap.multivix.edu.br/course/view.php?id=14438&section=5
https://avap.multivix.edu.br/course/view.php?id=14438&section=6
https://avap.multivix.edu.br/course/view.php?id=14438&section=7
https://avap.multivix.edu.br/course/view.php?id=14438&section=8
https://avap.multivix.edu.br/course/view.php?id=14438&section=9
https://avap.multivix.edu.br/course/view.php?id=14438&section=10
https://avap.multivix.edu.br/course/view.php?id=14438&section=11
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/local/staticpage/view.php?page=biblioteca
https://portalweb.multivix.edu.br/gabaritos/login.aspx
https://multivix.edu.br/office-365/
https://avap.multivix.edu.br/
Questão 5
Correto
Atingiu 0,15 de 0,15
O Google Maps é um recurso muito utilizado pelos internautas para traçar rotas e veri�car caminhos que levam
de uma origem ao destino desejado. O Google Maps vê o mapa como um grafo gigante. Cada cidade é um nó, e
duas cidades estão conectadas por uma aresta (via) se existe uma estrada de ligação entre elas. A �gura a seguir
exibe um grafo que representa um mapa rodoviário de pesquisa realizada no Google Maps. Os pesos indicam o
tempo atual de deslocamento entre dois municípios.
Figura: Grafo que representa um mapa rodoviário de pesquisa realizada no Google Maps
Fonte: Elaborada pela autora (2021).
#PraCegoVer: A �gura representa o grafo de um mapa rodoviário de pesquisa realizada no Google Maps. O grafo
possui 10 vértices, com apenas 4 vértices rotulados. Esses grafos são rotulados como i, w, j e k. As arestas são
ponderadas, e os pesos indicam o tempo de deslocamento entre dois municípios (representados pelos vértices).
O vértice i tem grau 3, e as arestas que o conectam a outros vértices têm pesos 1, 2 e 4. Já o vértice w tem grau 2
com arestas de peso 1 e 2. O vértice j tem grau 4 e arestas de pesos 1, 1, 2, e 1. Por �m, o vértice k tem grau 1 com
aresta de peso 2. Outros 5 vértices têm grau 2 e 1 vértice de grau 3, sendo que estes não são rotulados.
Considerando que os tempos de ida e volta são iguais para qualquer via, avalie as a�rmações a seguir acerca
desse grafo:
I. O grau do vértice de origem i é 3.
II. O grafo possui dois vértices de grau 3 e 1 vértice de grau 1.
III. Os vértices i, w, j e k são vértices direcionados.
É correto o que se a�rma em:
a. I e II. 
b. II e III.
c. II.
d. I, II e III.
e. I.
Sua resposta está correta.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=14438
https://avap.multivix.edu.br/user/index.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=1
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/course/view.php?id=14438&section=3
https://avap.multivix.edu.br/course/view.php?id=14438&section=4
https://avap.multivix.edu.br/course/view.php?id=14438&section=5
https://avap.multivix.edu.br/course/view.php?id=14438&section=6
https://avap.multivix.edu.br/course/view.php?id=14438&section=7
https://avap.multivix.edu.br/course/view.php?id=14438&section=8
https://avap.multivix.edu.br/course/view.php?id=14438&section=9
https://avap.multivix.edu.br/course/view.php?id=14438&section=10
https://avap.multivix.edu.br/course/view.php?id=14438&section=11
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/local/staticpage/view.php?page=biblioteca
https://portalweb.multivix.edu.br/gabaritos/login.aspx
https://multivix.edu.br/office-365/
https://avap.multivix.edu.br/
◄ Conteúdo online
Seguir para...
Conteúdo online ►



















https://avap.multivix.edu.br/mod/scorm/view.php?id=1043650&forceview=1https://avap.multivix.edu.br/mod/scorm/view.php?id=1043652&forceview=1
https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=14438
https://avap.multivix.edu.br/user/index.php?id=14438
https://avap.multivix.edu.br/course/view.php?id=14438&section=1
https://avap.multivix.edu.br/course/view.php?id=14438&section=2
https://avap.multivix.edu.br/course/view.php?id=14438&section=3
https://avap.multivix.edu.br/course/view.php?id=14438&section=4
https://avap.multivix.edu.br/course/view.php?id=14438&section=5
https://avap.multivix.edu.br/course/view.php?id=14438&section=6
https://avap.multivix.edu.br/course/view.php?id=14438&section=7
https://avap.multivix.edu.br/course/view.php?id=14438&section=8
https://avap.multivix.edu.br/course/view.php?id=14438&section=9
https://avap.multivix.edu.br/course/view.php?id=14438&section=10
https://avap.multivix.edu.br/course/view.php?id=14438&section=11
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/local/staticpage/view.php?page=biblioteca
https://portalweb.multivix.edu.br/gabaritos/login.aspx
https://multivix.edu.br/office-365/
https://avap.multivix.edu.br/