Modelagem e Problemas com Grafos

Prévia do material em texto

Minhas Disciplinas / Meus cursos / 422467 / Unidade 2 - Modelagem e problemas com grafos
/ UN 2 - Avaliação Objetiva
Pesquisa Operacional II
Iniciado em sexta, 5 mai 2023, 19:17
Estado Finalizada
Concluída em sexta, 5 mai 2023, 19:49
Tempo
empregado
31 minutos 59 segundos
Avaliar 1,36 de um máximo de 1,70(80%)




















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=3
https://avap.multivix.edu.br/mod/quiz/view.php?id=1307419
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 grafo G representado na �gura a seguir, ilustra o esquema de distribuição de tarefas de uma equipe de
estudantes durante um acampamento, em que cada vértice corresponde aos estudantes e as arestas são as
tarefas. Assim, dois estudantes que estão ligados por uma aresta denotam que há uma tarefa em comum.
Figura 1: Grafo planar
Fonte [DT1]  : Elaborada pela autora (2021).
#PraCegoVer: A �gura representa um grafo planar com sete vértices rotulados como “ a, b, c, d, e, f, g”. O vértice
“a” se conecta aos vértices “b” e “c”. O vértice “b” se conecta aos vértices “e” “d” e “c”. O vértice “c” se conecta aos
vértices “d” e “f”. O vértice “d” se conecta aos vértices “e” e “f”.  O vértice “c” se conecta ao vértice “f”. O vértice “e”
se conecta ao vértice “g”. O vértice “f” se conecta ao vértice “g”.
O número cromático é a quantidade máxima de cores que um grafo pode ter. Nesse caso, G tem número
cromático igual a:
a. 3. 
b. 1.
c. 2.
d. 5.
e. 4.
1
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/
Questão 2
Correto
Atingiu 0,34 de 0,34
Uma cooperativa de produtores de soja dispõe de galpões como depósitos de grãos, os quais são rotulados como
A, B e C. Dispondo respectivamente de 20, 10 e 35 toneladas de soja, é preciso entregar a três destinos, D, E e F,
respectivamente 25, 20 e 20 toneladas de soja. A cooperativa tem as disponibilidades de transporte em caminhão
entre os diferentes destinos. O grafo apresentado na �gura a seguir representa o modelo de distribuição dos
grãos.
Figura 3: Grafo modelo de distribuição de grãos
Fonte [DT1]  : Elaborada pela autora (2021).
#PraCegoVer: A �gura representa grafo de �uxo máximo com oito vértices. Tem início no vértice “I” e �m no
vértice “O”. Os demais vértices são rotulados como “A, B, C, D, E, F”. Do vértice “I’ parte arestas valoradas na
direção dos vértices “A”, “B” e “C” cujo valores são “20”, “10” e “35” respectivamente. Do vértice “A” parte arestas
valoradas na direção dos vértices “D” e “E” cujo valores são “15”e “10” respectivamente. Do vértice “B” parte arestas
valoradas na direção dos vértices “D” e “F” cujo valores são “5”e “10” respectivamente. Do vértice “C” parte arestas
valoradas na direção dos vértices “D”, “E” e “F” cujo valores são “5”, “10” e “5” respectivamente. Do vértice “D” parte
aresta valorada na direção do vértice “O” de valor “25”. Do vértice “E” parte aresta valorada na direção do vértice
“O” de valor “20”. Do vértice “F” parte aresta valorada na direção do vértice “O” de valor “20”.
Considerando o problema de �uxo máximo com aplicação do algoritmo de Ford-Fulkerson, o �uxo máximo em
toneladas é igual a:
a. 10.
b. 50. 
c. 30.
d. 20
e. 25.




















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/calendar/view.php/
https://avap.multivix.edu.br/
Questão 3
Correto
Atingiu 0,34 de 0,34
Todo início de semestre letivo, o maior desa�o dos diretores e coordenadores é fechar o horário de aulas de
acordo com a grade curricular dos cursos e das disciplinas que estão sendo ofertadas. Até alguns anos atrás, isso
era feito de forma manual por todas as instituições de ensino. Entretanto, atualmente, muitas já estão utilizando
programas computacionais que realizam todo processo de forma automatizada. Mesmo que isso tenha tornado
a vida dos diretores e coordenadores mais fácil, a tecnologia por trás destes softwares tem uma modelagem feita
por grafos. A �gura a seguir ilustra uma situação hipotética de quadro de horário de disciplinas em forma de um
grafo.
Figura 4: Modelo de grafo para grade de horário de aulas
Fonte [DT1]  : Elaborada pela autora (2021).
#PraCegoVer: A �gura representa grafo com oito vértices. Os vértices são rotulados com os textos: “Estatística”,
“Geometria”, “Libras”, “Psicologia”, “Didática”, “Física”, “Química” e “Cálculo II”. O vértice “Estatística”, se conectaaos vértices “Geometria”, “Libras”, “Física” e “Química”. O vértice “Geometria”, se conecta aos vértices “Estatística”,
“Psicologia”, “Didática” e “Cálculo II”. O vértice “Psicologia”, se conecta aos vértices “Física” e “Química”. O vértice
“Didática”, se conecta ao vértice “Química”. O vértice “Física”, se conecta ao vértice “Cálculo II”. O vértice
“Química”, se conecta ao vértice “Cálculo II”.
Considerando no número mínimo de cores para coloração de um grafo, é possível utilizar o mínimo de:
a. 4 cores para colorir o grafo de horários.
b. 6 cores para colorir o grafo de horários.
c. 5 cores para colorir o grafo de horários.
d. 3 cores para colorir o grafo de horários.
e. 2 cores para colorir o grafo de horários. 




















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
Incorreto
Atingiu 0,00 de 0,34
Questão 5
Correto
Atingiu 0,34 de 0,34
Os grafos planares são aplicados em circuitos integrados, em placas de circuito impresso, nas quais
componentes eletrônicos são montados em rodovias ligando cidades, em linhas de transmissão de energia
elétrica e linha de produção em uma indústria, entre outros usos. Suponha um grafo G(V,E) simples conexo e
planar 12 nós, cada um com grau 4. É possível dividir uma representação planar desse grafo em um número de
regiões igual a:
a. 24.
b. 14.
c. 7.
d. 12. 
e. 6.
Uma rede de Petri é uma ferramenta de modelagem matemática utilizada na análise e simulação de sistemas
concorrentes em ciência da computação. Nesse caso, o sistema é modelado como um grafo bipartido dirigido
com dois conjuntos de vértices: um conjunto de vértices que contêm recursos, e um conjunto de vértices que
geram e/ou consomem recursos. As redes de Petri utilizam as propriedades de grafos bipartidos dirigidos e
outras propriedades para permitir demonstrações matemáticas do desempenho dos sistemas, ao passo que
permite a fácil implementação de simulações do sistema. Em relação às propriedades dos grafos bipartidos, é
correto o que se a�rma em:
a. Um grafo é bipartido se e somente se seu número cromático é igual a 2.
b. O tamanho da cobertura de vértices máxima é igual ao tamanho do clique máximo.
c. Um grafo é bipartido se e somente se ele não contém um ciclo par.
d. O tamanho do conjunto independente máximo é igual ao número de vértices.
e. Todo grafo bipartido é um grafo perfeito. 
◄ Conteúdo online 
Seguir para...
Conteúdo online  ►




















https://avap.multivix.edu.br/mod/scorm/view.php?id=1307410&forceview=1
https://avap.multivix.edu.br/mod/scorm/view.php?id=1307420&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/