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 quinta, 4 mai 2023, 22:21
Estado Finalizada
Concluída em quinta, 4 mai 2023, 22:56
Tempo
empregado
35 minutos 32 segundos
Avaliar 1,70 de um máximo de 1,70(100%)




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=20374
https://avap.multivix.edu.br/course/view.php?id=20374&section=2
https://avap.multivix.edu.br/mod/quiz/view.php?id=1307409
https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=20374
https://avap.multivix.edu.br/user/index.php?id=20374
https://avap.multivix.edu.br/course/view.php?id=20374&section=1
https://avap.multivix.edu.br/course/view.php?id=20374&section=2
https://avap.multivix.edu.br/course/view.php?id=20374&section=3
https://avap.multivix.edu.br/course/view.php?id=20374&section=4
https://avap.multivix.edu.br/course/view.php?id=20374&section=5
https://avap.multivix.edu.br/course/view.php?id=20374&section=6
https://avap.multivix.edu.br/course/view.php?id=20374&section=7
https://avap.multivix.edu.br/course/view.php?id=20374&section=8
https://avap.multivix.edu.br/course/view.php?id=20374&section=9
https://avap.multivix.edu.br/course/view.php?id=20374&section=10
https://avap.multivix.edu.br/course/view.php?id=20374&section=11
https://avap.multivix.edu.br/course/view.php?id=20374&section=12
https://avap.multivix.edu.br/course/view.php?id=20374&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/
Questão 1
Correto
Atingiu 0,34 de 0,34
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.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=20374
https://avap.multivix.edu.br/user/index.php?id=20374
https://avap.multivix.edu.br/course/view.php?id=20374&section=1
https://avap.multivix.edu.br/course/view.php?id=20374&section=2
https://avap.multivix.edu.br/course/view.php?id=20374&section=3
https://avap.multivix.edu.br/course/view.php?id=20374&section=4
https://avap.multivix.edu.br/course/view.php?id=20374&section=5
https://avap.multivix.edu.br/course/view.php?id=20374&section=6
https://avap.multivix.edu.br/course/view.php?id=20374&section=7
https://avap.multivix.edu.br/course/view.php?id=20374&section=8
https://avap.multivix.edu.br/course/view.php?id=20374&section=9
https://avap.multivix.edu.br/course/view.php?id=20374&section=10
https://avap.multivix.edu.br/course/view.php?id=20374&section=11
https://avap.multivix.edu.br/course/view.php?id=20374&section=12
https://avap.multivix.edu.br/course/view.php?id=20374&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/
Questão 2
Correto
Atingiu 0,34 de 0,34
Questão 3
Correto
Atingiu 0,34 de 0,34
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. III.
b. I.
c. II e III.
d. IV e III.
e. I e IV. 
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. Desconexo.
b. Vazio.
c. Ponderado.
d. Direcionado. 
e. Bipartido.




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=20374
https://avap.multivix.edu.br/user/index.php?id=20374
https://avap.multivix.edu.br/course/view.php?id=20374&section=1
https://avap.multivix.edu.br/course/view.php?id=20374&section=2
https://avap.multivix.edu.br/course/view.php?id=20374&section=3
https://avap.multivix.edu.br/course/view.php?id=20374&section=4
https://avap.multivix.edu.br/course/view.php?id=20374&section=5
https://avap.multivix.edu.br/course/view.php?id=20374&section=6
https://avap.multivix.edu.br/course/view.php?id=20374&section=7
https://avap.multivix.edu.br/course/view.php?id=20374&section=8
https://avap.multivix.edu.br/course/view.php?id=20374&section=9
https://avap.multivix.edu.br/course/view.php?id=20374&section=10
https://avap.multivix.edu.br/course/view.php?id=20374&section=11
https://avap.multivix.edu.br/course/view.php?id=20374&section=12
https://avap.multivix.edu.br/course/view.php?id=20374&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/
Questão 4
Correto
Atingiu 0,34 de 0,34
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} representao 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 IV.
b. I e II.
c. II, III e IV.
d. I, II e IV.
e. II e III. 




















https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=20374
https://avap.multivix.edu.br/user/index.php?id=20374
https://avap.multivix.edu.br/course/view.php?id=20374&section=1
https://avap.multivix.edu.br/course/view.php?id=20374&section=2
https://avap.multivix.edu.br/course/view.php?id=20374&section=3
https://avap.multivix.edu.br/course/view.php?id=20374&section=4
https://avap.multivix.edu.br/course/view.php?id=20374&section=5
https://avap.multivix.edu.br/course/view.php?id=20374&section=6
https://avap.multivix.edu.br/course/view.php?id=20374&section=7
https://avap.multivix.edu.br/course/view.php?id=20374&section=8
https://avap.multivix.edu.br/course/view.php?id=20374&section=9
https://avap.multivix.edu.br/course/view.php?id=20374&section=10
https://avap.multivix.edu.br/course/view.php?id=20374&section=11
https://avap.multivix.edu.br/course/view.php?id=20374&section=12
https://avap.multivix.edu.br/course/view.php?id=20374&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/
Questão 5
Correto
Atingiu 0,34 de 0,34
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. Exploração de grafo. 
b. Reconhecimento de padrões.
c. Genético.
d. Programação dinâmica.
e. Divisão e conquista.
◄ Conteúdo online 
Seguir para...
Conteúdo online ►




















https://avap.multivix.edu.br/mod/scorm/view.php?id=1307399&forceview=1
https://avap.multivix.edu.br/mod/scorm/view.php?id=1307410&forceview=1
https://avap.multivix.edu.br/my/
https://avap.multivix.edu.br/course/view.php?id=20374
https://avap.multivix.edu.br/user/index.php?id=20374
https://avap.multivix.edu.br/course/view.php?id=20374&section=1
https://avap.multivix.edu.br/course/view.php?id=20374&section=2
https://avap.multivix.edu.br/course/view.php?id=20374&section=3
https://avap.multivix.edu.br/course/view.php?id=20374&section=4
https://avap.multivix.edu.br/course/view.php?id=20374&section=5
https://avap.multivix.edu.br/course/view.php?id=20374&section=6
https://avap.multivix.edu.br/course/view.php?id=20374&section=7
https://avap.multivix.edu.br/course/view.php?id=20374&section=8
https://avap.multivix.edu.br/course/view.php?id=20374&section=9
https://avap.multivix.edu.br/course/view.php?id=20374&section=10
https://avap.multivix.edu.br/course/view.php?id=20374&section=11
https://avap.multivix.edu.br/course/view.php?id=20374&section=12
https://avap.multivix.edu.br/course/view.php?id=20374&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/