AV1 - TEORIA DOS GRAFOS - 2020.1

Prévia do material em texto

N O M E D A D IS C IP L IN A 
 TEORIA DOS GRAFOS 
AVALIAÇÃO: AV1 , TEÓRICA, 2020 .1 ; Duração da Prova: 4 Horas 
Nome do(a) A luno(a ) : Nº de mat r ícu la: 
 
 
 
 
 
 
 
 
INSTRUÇÕES IMPORTANTES 
 
Esta avaliação consta de 6 questões (3 subjetivas e 3 objetivas) que totalizam 10 pontos. A pontuação de cada 
questão está indicada antes o enunciado da mesma. As respostas deverão conter memória de cálculo para as 
questões subjetivas que exigem cálculos e deverão ser justificadas. A interpretação faz parte da questão e o 
professor não poderá ser consultado para tirar dúvidas sobre conteúdos. 
A resolução das questões pode ser digitada ou manuscrita (neste caso, postar arquivo em pdf com fotos da 
resolução). 
Local de postagem da avaliação: Tarefas ----> Atividade Avaliativa – Provas. 
 
 
 
 
 
 
 
 
 
Questões Objetivas: 
 
Questão 1 (Valor 1,8): Diferente de muitos dos ramos da Matemática que foram motivados por problemas envolvendo 
cálculos, movimento, entre outros, o desenvolvimento da Teoria de Grafos se deu através de problemas envolvendo jogos 
e quebra-cabeças. Os grafos têm sido objeto de estudo desde o século XVIII e têm sido parte importante na solução de 
problemas famosos. Considere os Grafos representados a seguir: 
 
 
 
 
 
Com base nos Grafos acima, analise as afirmações: 
I. G é um pseudografo conexo, ∆(𝐺) = 6 , 𝛿(𝐺) = 1. 
II. F é um subgrafo de G. 
III. A matriz de adjacência de G tem ordem 6 × 6 e a matriz de incidência de G tem ordem 6 × 13. 
IV. H é um multigrafo bipartido. 
V. F é um grafo simples bipartido. 
 
Com base nas afirmações, assinale a alternativa que indica a afirmação correta: 
 
a) As afirmações I, II e IV são corretas. 
b) As afirmações I, II, III e V são corretas. 
c) Apenas as afirmações I e III são corretas. 
d) Apenas as afirmações I, II e III são corretas. 
e) Todas as afirmações são corretas. 
 
 
 
G F H 
 
Questão 2 (Valor 1,8): A Teoria dos Grafos é um ramo da matemática que estuda as relações entre os objetos de um 
determinado conjunto. Dependendo da aplicação, as arestas de um grafo podem ou não ter direção, pode ser permitido ou 
não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Considere 
os Grafos representados a seguir: 
 
 
Com base nos Grafos acima, analise as afirmações: 
I. ∆+(𝐺) = 2 = 𝛿+(𝐺). 
II. O vértice 3 é um sumidouro do grafo F e ∆−(𝐺) = 3. 
III. H é um grafo regular e conexo. 
IV. O grafo G não possui vértice fonte nem vértice sumidouro. 
 
Com base nas afirmações, assinale a alternativa que indica a afirmação correta: 
 
a) As afirmações I, II e IV são corretas. 
b) Apenas as afirmações II e IV são corretas. 
c) Apenas a afirmação IV é correta. 
d) As afirmações I, II e III são corretas. 
e) Todas as afirmações são corretas. 
 
Questão 3 (Valor 1,4): Uma das formas mais comuns de “informar” uma estrutura de grafo para um computador é através 
de matrizes. Considere que a matriz abaixo represente a matriz de adjacência de um grafo não orientado G: 
 
|
|
0 1 2 0 0 0
1 1 0 1 1 0
2 0 0 3 1 1
0 1 3 1 0 0
0 1 1 0 1 0
0 0 1 0 0 0
|
|
 
 
Com base na matriz acima, assinale a alternativa correta: 
 
a) G é um grafo completo. 
b) G é um grafo simples. 
c) G é um pseudografo e ∆(𝐺) = 3. 
d) G é um pseudografo regular. 
e) G possui vértice isolado. 
 
 
 
 
 
 
G F H 
https://pt.wikipedia.org/wiki/Matem%C3%A1tica
 
 
Questões Subjetivas: 
 
A Teoria dos Grafos é de fundamental importância aos cursos de Ciência e Engenharia da Computação. Isto se deve a 
inúmeros motivos, entre eles, o fato de servir de modelo matemático para alguns dos problemas mais importantes e difíceis 
da computação. Vários problemas do mundo real podem ser analisados usando a Teoria dos Grafos, por exemplo, o 
escalonamento de processos pode ser visualizado como uma aplicação direta do problema de coloração de grafos e o 
problema de reconhecimento de padrões pode ser visto como uma instância do problema de isomorfismo em grafos. 
 
Questão 4 (Valor 1,5): Considere o Grafo a seguir: 
 
Pede-se: 
a) Grau de Entrada de todos os vértices. 
b) Grau de Saída de todos os vértices. 
c) Matriz de Adjacência. 
d) Lista de adjacência. 
e) Ciclo de maior tamanho. 
Questão 5 (Valor 1,5): Considere o Grafo a seguir: 
 
Pede-se: 
a) Grau de todos os vértices. 
b) ∆(𝐺) 𝑒 𝛿(𝐺). 
c) Matriz de Adjacência. 
d) Lista de adjacência. 
 
 
 
 
Questão 6 (Valor 2,0): De acordo com os conceitos básicos sobre Grafos, pede-se: 
 
a) Há possibilidade de um Grafo ser completo e não regular? Caso positivo, apresente um exemplo; caso negativo, 
justifique devidamente. 
b) Há possibilidade de um Grafo ser completo e não conexo? Caso positivo, apresente um exemplo; caso negativo, 
justifique devidamente. 
c) Verifique se o par de Grafos abaixo são isomorfos. Caso não seja, justifique. Caso seja, encontra a bijeção entre os 
Grafos: 
 
d) Considere a matriz abaixo: 
|
1 0 2 0
1 1 0 1
1 2 0 1
1 1 0 0
| 
 
Esboce a representação de um Grafo Orientado cuja matriz de adjacência é dada pela matriz acima. 
 
 
 
 
Bom Trabalho!!!