AV1 Antiga

Prévia do material em texto

2 
 
Questão 1 (1,2 pontos) 
 
Considere o grafo abaixo G1 abaixo, e as seguintes 
afirmações sobre G1: 
 
 
 
I. G1 é regular. 
II. G1 admite caminho euleriano. 
III. G1 contém uma ponte ou articulação. 
 
Das afirmações acima, são corretas: 
 
a) Apenas I. 
b) Apenas II. 
c) Apenas I e II. 
d) Apenas I e III. 
e) Nenhuma delas. 
 
Questão 2 (1,2 pontos) 
 
Considere o grafo abaixo G2 abaixo, e as seguintes 
afirmações sobre G2: 
 
 
 
I. G2 é euleriano. 
II. G2 é hamiltoniano. 
III. G2 contém uma ponte ou uma articulação. 
 
Das afirmações acima, são corretas: 
 
a) Apenas I. 
b) Apenas II. 
c) Apenas I e II. 
d) Apenas II e III. 
e) Todas elas. 
 
 
 
Questão 3 (1,2 pontos) 
 
Considere as seguintes afirmações sobre os grafos Kn : 
 
I. Todo grafo Kn , com n > 1, é conexo. 
II. Todo grafo Kn é regular. 
III. Todo grafo Kn , com n > 2, contém uma ponte. 
 
Das afirmações acima, são corretas: 
 
a) Apenas I. 
b) Apenas II. 
c) Apenas I e II. 
d) Apenas I e III. 
e) Todas delas. 
 
Questão 4 (1,2 pontos) 
 
Considere as seguintes afirmações sobre grafos: 
 
I. O grafo K2,3 é um grafo regular. 
II. O grafo K2,3 é um grafo conexo. 
III. O grafo K2,3 admite caminho euleriano. 
 
Das afirmações acima, são corretas: 
 
a) Apenas I. 
b) Apenas II. 
c) Apenas I e II. 
d) Apenas II e III. 
e) Todas elas. 
 
 
 
Questão 5 (1,2 pontos) 
 
Considere as seguintes afirmações sobre grafos 
simples, sendo n o número de vértices: 
 
I. Um caminho de comprimento MAIOR QUE n 
certamente NÃO É um caminho simples. 
II. Um caminho de comprimento MENOR QUE n 
certamente É um caminho simples. 
III. Se G possui um caminho de comprimento 
MAIOR QUE n, então G é conexo. 
 
São corretas as seguintes afirmações: 
 
a) Apenas I. 
b) Apenas II. 
c) Apenas I e II. 
d) Apenas II e III. 
e) Todas elas. 
 
 
Questão 6 (1,3 pontos) 
 
Desenhe uma REPRESENTAÇÃO PLANA do grafo K2,3 , ou prove porque este grafo é não-planar. 
 
 
 
 
 
 
 
 
 
 
 
Questão 7 (1,3 pontos) 
 
Desenhe uma REPRESENTAÇÃO PLANA de um grafo 4-regular, ou prove porque tal grafo não existe. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Questão 8 (1,4 pontos) 
 
Escreva o pseudo-códico da função Grau, que retorna o grau de um vértice v em um grafo simples. 
Não precisa declarar variáveis locais da função. 
{ Variáveis globais } 
A: vetor[1..100,1..100] de inteiro { Matriz de Adjacências } 
n: inteiro { Número de vértices do grafo } 
 
Função Grau (v: inteiro) 
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
___________________________________________________________________________________________
__________________________________________________________________________________________