Lista 1 - Teoria Grafos Conceitos Iniciais - Resposta

Prévia do material em texto

1) O grafo das palavras é definido assim: cada vértice é uma palavra da 
língua portuguesa e duas palavras são adjacentes se diferem em exatamente 
uma posição. Por exemplo, rato e ralo são adjacentes, enquanto ralo e 
rota não são. Faça uma figura da parte do grafo definida pelas palavras 
abaixo: 
Caiado, cavado, cavalo, girafa, girava, ralo, ramo, rata, rato, 
remo, reta, reto, rota, vaiado, varado, virada, virado, virava 
 
Caiado 
cavado 
cavalo 
girafa 
girava 
ralo 
ramo 
rata 
rato 
remo 
reta 
reto 
rota 
vaiado 
virada 
varado 
virava 
 
 
 
2) Considere o grafo: 
a) O grafo é simples? 
b) O grafo é completo? 
 
 
 
 
 
 
 
 
 
Grafo simples 
Um grafo simples é um grafo que não possui laços nem arestas paralelas. Num grafo simples, 
uma aresta com vértices (nós terminais) u e v é representada por uv. 
 
Grafo completo 
 
Um grafo completo de n vértices, denominado Kn, é um grafo simples com n vértices v1; v2 ... 
vn, cujo conjunto de arestas contém exatamente uma aresta para cada par de vértices 
distintos. 
 
A letra K representa a letra inicial da palavra komplett do alemão, que significa “completo”. 
 
 
 
3) Esboce um grafo com as seguintes características: 
a. Simples com 3 nós, cada um com grau 2 
b. 4 nós e ciclos de comprimento 1, 2, 3 e 4 
c. Não completo com 4 nós, cada um com grau 4 
 
 
 
 
 
 
4) O grafo de interseção de uma coleção de conjuntos A1, A2, .... , An é o grafo que tem um 
vértice para cada um dos conjuntos da coleção e tem uma aresta conectando os vértices se 
esses conjuntos têm uma interseção não vazia. Construa o grafo de interseção para as 
seguintes coleções de conjuntos. 
a. 
 
b. 
 
c. 
 
a) 
 
b) 
 
c) 
 
 
5) Pode haver um grafo simples com 15 vértices, cada um com grau 5? 
Resposta: 
Não. O grau desse suposto grafo seria 15 × 5 = 75, que é um número ímpar. Sabe-se que o grau 
de qualquer 
grafo deve ser um número par. 
 
 
 
 
 
6) Determine se cada um dos grafos abaixo é bipartido. 
 
a. 
 
b. 
 
c. 
 
d. 
 
e. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
7) Quantas arestas tem um grafo com vértices de graus 5; 2; 2; 2; 2; 1? Desenhe um possível grafo 
 
 
 
 
 
 
8) Existe um grafo simples com cinco vértices dos seguintes graus? Se existir, desenhe um 
possível grafo 
 
a. 3; 3; 3; 3; 2 
b. 1; 2; 3; 4; 5 
c. 1; 2; 3; 4; 4 
d. 3; 4; 3; 4; 3 
e. 0; 1; 2; 2; 3 
f. 1; 1; 1; 1; 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
9) Desenhe todos os subgrafos do grafo abaixo. 
 
 
 
 
10) Quantos vértices tem um grafo regular de grau 4 com 10 arestas? 
 
 
11) O grafo reverso de um grafo dirigido G = (V, E), representado por Gr, é o grafo dirigido (V, 
F) onde (u, v) ∈ F , se, e somente se, (v, u) ∈ E. Desenhe os grafos Gr correspondentes aos 
seguintes grafos: 
 
 
 
Respostas: 
 
 
 
 
 
 
12) Seja G um grafo dirigido. Mostre que G = Gr se, e somente se, a relação associada com 
G é simétrica