PROVA N2 GRA0808 INTRODUÇÃO A TEORIA DOS GRAFOS UAM 15 ABR 2022 A5

Prévia do material em texto

Prova N2 
GRA0808 INTRODUÇÃO A TEORIA DOS GRAFOS 
UAM 1º semestre 2022 
15 ABR 22 
A5 
Observações: 
• Não há ainda o gabarito. A UAM só vai liberar as respostas depois do período de 
provas (dia 20 ABR 22). 
• Sugiro leitura dos materiais disponíveis pelo curso na plataforma ulife (da Aula 1 à 4). 
• Das 10 questões, 6 são inéditas (não estavam nas Atividades 2 e 4, realizadas ao longo 
do bloco). Logo, sugiro que estudem as apostilas do próprio curso. 
 
A seguir, estão as respostas realizadas por este estudante. 
Deixem nos comentários, opiniões e respostas, caso identifiquem opções incorretas, 
para abertura de uma janela de oportunidade aos futuros estudantes. 
Boa prova. 
 
 
Questões: 
 
1. Algumas áreas ligadas a transporte muitas vezes utilizam os 
conhecimentos acerca do Circuito de Hamilton, sem sequer saberem que 
estão utilizando uma das maiores contribuições propostas na Teoria dos 
Grafos. Isso demonstra o quão eficiente é a técnica para solucionar alguns 
problemas ligados a transporte e deslocamento. 
 
 
 
 
 
 
Figura - Planejamento de trajeto 
 
 
 
 
Fonte: Elaborada pelo autor. 
 
 
Considerando cada um dos vértices como sendo uma cidade e as arestas uma 
estrada que as ligam, analise as afirmativas a seguir e assinale V para a(s) 
verdadeira(s) e F para a(s) falsa(s). 
 
I. ( ) É possível iniciar e finalizar o trajeto na mesma cidade. 
II. ( ) É possível fazer o trajeto sem repetir nenhuma cidade. 
III. ( ) Sem um laço, não é possível fazer o circuito completo. 
IV. ( ) São necessárias 21 arestas para passar em todos os vértices. 
Assinale a alternativa que apresenta a sequência correta. 
 
2. 
Quando Euller propôs uma discussão que deu início aos fundamentos e aplicações 
da teoria dos grafos, nascia ali um conhecimento que, após anos de evolução, 
pôde contribuir para diversas áreas de conhecimento, com o intuito de otimizar 
alguns processos. 
 
Quanto às contribuições na pesquisa operacional, observe as afirmativas a seguir: 
 
I. Conhecida como teoria das rotas otimizadas, foi proposta por Ford e Euller. 
II. A teoria dos fluxos em redes propôs a otimização de rotas, para economia de 
recursos. 
III. Os conhecimentos produzidos para a pesquisa operacional são recentes. As 
conclusões desses estudos foram finalizadas e publicadas na década de 1990. 
IV. As arestas não podem ser expressas nos problemas de pesquisa operacional. 
 
 
Está correto o que se afirma em: 
 
3 
O problema de coloração adiciona aos problemas relacionados à teoria dos grafos 
mais uma variável, em que é possível planejar o relacionamento feito pelas arestas 
por meio das cores encontradas nos vértices do grafo. Essa técnica se torna 
interessante à medida que se tenha a necessidade de efetuar uma análise mais 
detalhada de determinado sistema. 
 
A partir do apresentado, analise as asserções e a relação proposta entre elas. 
 
I. No problema da coloração, os vértices possuem restrições de relacionamento. 
Pois: 
II. O objetivo é relacionar apenas os vértices de mesma cor. 
 
A seguir, assinale a alternativa correta. 
 
4 
O problema do caixeiro viajante, também conhecido como PVC, é considerado um 
grafo hamiltoniano, uma vez que possui características idênticas às do Circuito de 
Hamilton. Porém, no PVC a utilização do custo é a variável que difere esses dois 
tipos de grafos. 
Considerando o excerto apresentado, sobre o circuito de Hamilton, analise as 
afirmativas a seguir. 
 
I. Nos grafos de Hamilton, há um circuito; já no PVC, não é necessário. 
II. No PVC o trajeto deve garantir que se visite apenas uma única vez cada vértice 
do grafo. 
III. A ordem que os vértices serão visitados não é o mais importante, mas, sim, o 
custo. 
IV. No PVC o trajeto pode ser somente assimétrico. 
 
Está correto o que se afirma em: 
 
5 
O grafo em árvore contém em seu diagrama uma figura com características de 
hierarquias encontradas em carreira de empresas privadas ou públicas. Na Teoria 
dos Grafos, esse tipo de grafo possui algumas peculiaridades que lembram as de 
uma raiz. 
 
A partir do apresentado, analise as asserções a seguir e a relação proposta entre 
elas. 
 
I. O vértice ao centro do grafo é chamado de raiz. 
Pois: 
II. Os vértices que são ligados a esse principal são chamados de secundários. 
 
A seguir, assinale a alternativa correta. 
 
6 
Os grafos podem representar diversos tipos de sistemas, mostrando-se uma 
ferramenta matemática de grande aplicabilidade. Considere que cada vértice 
representado no grafo seja uma cidade e as arestas sejam estradas que levam o 
motorista de um ponto ao outro do estado, conforme pode ser observado a seguir. 
 
Figura 3 - Grafo não orientado de uma matriz adjacente 
Fonte: Elaborada pelo autor. 
A respeito do vetor que gerou o grafo apresentado, analise as afirmativas a seguir 
e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
( ) A linha do vetor que representa o vértice “A” tem os valores: C e F. 
( ) A linha do vetor que representa o vértice “B” tem os valores: C e E. 
( ) A linha do vetor que representa o vértice “C” tem os valores: A e D. 
( ) A linha do vetor que representa o vértice “D” tem os valores: E e F. 
( ) A linha do vetor que representa o vértice “E” tem os valores: B e D. 
 
Assinale a alternativa que apresenta a sequência correta: 
 
7. 
Leia o excerto a seguir: 
“O diretor deve manter contato direto com os gerentes financeiro, operacional e 
contábil. Já o gerente administrativo se reporta ao CEO, assim como o diretor”. 
Esse texto deve servir de orientação para que os colaboradores da empresa 
possam compreender a política hierárquica da empresa e o fluxo da comunicação 
interna. 
 
 
 
Considerando o excerto apresentado, sobre as matrizes, analise as afirmativas a 
seguir. 
 
I. Para construir um grafo a partir do texto apresentado, são necessários três laços, 
um para cada gerente que se reporta ao diretor. 
II. Para construir um grafo a partir do texto apresentado, são necessários três laços 
e seis arestas. 
III. Para construir um grafo a partir do texto apresentado, são necessárias cinco 
arestas. 
IV. Não é possível transformar o texto apresentado em um grafo. 
 
Está correto o que se afirma em: 
 
8 
Os cargos e as posições hierárquicas dentro das empresas são uma forma de 
organizar responsabilidades e atribuições, a fim de se obter os melhores 
resultados. O vetor a seguir demonstra os relacionamentos de cargos dentro de 
uma empresa. Esses cargos são expressos por códigos de uso interno e 
determinam a posição hierárquica desse colaborador na empresa. 
Para tanto, observe o vetor a seguir. 
 
D1 D1 D2 H1
D2 D1 D2 H1
G4 D2 M55 
M55 G4 
H1 D1 D2 H10
H10 H1 H10 
 
 
Fonte: Elaborado pelo autor. 
Nesse sentido, assinale a alternativa com o grafo relacionado ao vetor. 
 
Considerando o vetor apresentado, analise as afirmativas com os grafos a seguir. 
1. 
2. 
3. 
4. 
 
Está correto o que se afirma em: 
 
9 
As matrizes incidência podem representar um conjunto de dados extraídos de 
diversas fontes, sendo possível representar, por meio dos valores encontrados nas 
linhas, a presença ou ausência de relacionamento entre os vértices. Para tanto, 
são utilizadas as representações binárias, com os valores 0 e 1. 
Um exemplo pode ser observado a seguir. 
 
 a1 a2 a3 
A 0 0 1 
B 1 1 0 
C 0 1 0 
D 1 0 1 
 
 
Fonte: Elaborado pelo autor. 
Considerando a matriz apresentada, analise os grafos a seguir. 
1. 
2. 
3. 
4. 
5. 
 
Está correto o que se afirma em: 
 
10. 
As matrizes são propriedades encontradas na matemática que, além de agrupar e 
organizar diversos valores, permitem que se efetuem operações entre as matrizes, 
possibilitando a realização de soma, subtração, multiplicação, entre outras 
operações. Essa ferramenta é tão poderosa e flexível que, por meio de suas 
técnicas, é possível representar os grafos, conforme pode ser observado a seguir. 
 
Figura1: Grafo não orientado 
Fonte: Elaborada pelo autor. 
 
A respeito da matriz adjacente que gerou o grafo apresentado, analise as 
afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). 
 
( ) A linha da matriz que representa o vértice “A” tem os valores 0, 0, 0, 1, 0. 
( ) A linha da matriz que representa o vértice “B” tem os valores 0, 1, 1, 0, 1. 
( ) A linha da matriz que representa o vértice “C” tem os valores 0, 1, 0, 1, 1. 
( ) A linha da matriz que representa o vértice “D” tem os valores 0, 0, 1, 0, 0. 
( ) A linha da matriz que representa o vértice “E” tem os valores 0, 0, 1, 1, 0. 
 
Assinale a alternativa que apresenta a sequência correta.