Teoria dos grafos Questionário 1 AVA

Prévia do material em texto

• Pergunta 1 
0,5 em 0,5 pontos 
 
Considere o grafo representado na figura abaixo: Assinale a alternativa que apresenta a função programa g 
que lhe corresponde. 
 
 
 
 
 
 
Resposta Selecionada: a. 
g(x) = 1-2, g(y) = 1-3, g(z) = 2-3 
 
 
• Pergunta 2 
0,5 em 0,5 pontos 
 
Considere o grafo apresentado na figura 2. Assinale a alternativa que representa a matriz de adjacência do 
grafo. 
 
 
 
 
 
Resposta Selecionada: e. 
 
 
 
• Pergunta 3 
0 em 0,5 pontos 
 
Considere o grafo direcionado com pesos da figura 3, bem como as asserções que se seguem. 
 
 
I – A figura 4 representa a lista de adjacência correspondente ao grafo. 
 
 
 
 
 
 
 
 
 
 
II – Existe um ciclo de comprimento 3. 
III – Existe um caminho que passa por todos os nós uma única vez. 
 
São corretas as asserções: 
Resposta Selecionada: a. 
Apenas I. 
 
 
• Pergunta 4 
0 em 0,5 pontos 
 
Considere o grafo da figura 5. 
 
 
 
 
 
 
 
A respeito do grafo, pode-se afirmar que: 
 
Resposta Selecionada: a. 
É bipartido completo e denomina-se K5. 
 
 
• Pergunta 5 
0 em 0,5 pontos 
 
A respeito do grafo K3,2, pode-se afirmar que: 
 
 
I – Trata-se de um grafo planar. 
II – Trata-se de um grafo simples. 
III – Trata-se de um grafo conexo. 
 
São corretas as asserções: 
 
Resposta Selecionada: e. 
Apenas III. 
 
 
• Pergunta 6 
0,5 em 0,5 pontos 
 
O número cromático do grafo K3,3 é: 
Resposta Selecionada: a. 
2 
 
 
• Pergunta 7 
0,5 em 0,5 pontos 
 
(POSCOMP 2013, questão 37) Seja G o grafo representado pela figura a seguir. 
 
 
 
 
 
 
Assinale a alternativa que apresenta, corretamente, o número cromático associado ao grafo. 
 
Resposta Selecionada: a. 
 3 
 
 
• Pergunta 8 
0,5 em 0,5 pontos 
 
Considere as seguintes asserções: 
 
 
I – Em muitas áreas da computação, é conveniente modelar um algoritmo ou um programa usando um grafo. 
II – Instalações de fornecimento de luz, água e esgoto em uma instalação podem ser representadas por um 
grafo. 
III – Uma rede de radares instalada sobre uma determinada rede de avenidas ou ruas pode ser representada 
por um grafo. 
 
 
São corretas as afirmações: 
 
Resposta Selecionada: e. 
I, II e III. 
 
 
• Pergunta 9 
0,5 em 0,5 pontos 
 
POSCOMP 2014 questão 36. Considerando que um grafo possui n vértices e m arestas, assinale a alternativa 
que apresenta, corretamente, um grafo planar. 
Resposta Selecionada: d. 
n = 8, m = 12 
 
 
• Pergunta 10 
0,5 em 0,5 pontos 
 
Considere as seguintes afirmações: 
 
I – Dois grafos não são isomorfos se um tem mais nohs que o outro. 
II – Dois grafos não são isomorfos se um tem mais arcos que o outro. 
III – Dois grafos não são isomorfos se um tem um ciclo e o outro não. 
 
São corretas as afirmações: 
 
Resposta Selecionada: c. 
I, II e III.