Tema 02 - Graus dos Vértices; Grafos Especiais - GABARITO DOS EXERCÍCIOS

Prévia do material em texto

CURSO: CIÊNCIA DA COMPUTAÇÃO 
DISCIPLINA: TEORIA EM GRAFOS 
TEMA 2: Graus dos Vértices; Grafos Especiais 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) Não. Demonstre esta impossibilidade a partir dos teoremas 1.1 ou 1.2. 
2) Demonstre esta impossibilidade a partir dos teoremas 1.1 ou 1.2. 
3) Existe algum grafo com 5 vértices, cujos graus são 0, 1, 2, 3, 4? Por que? 
Não. Suponha que exista tal grafo, sendo V = { v0, v1, v2, v3, v4 }. Considere que v0 e v4 os vértices 
de graus d(v0) = 0 e d(v4) =4. Assim, o vértice v4 deveria ser adjacente a TODOS os demais vértices 
do grafo – inclusive ao vértice v0. Mas isto é um absurdo, pois v0 é um vértice isolado, e não 
poderia ser adjacente a nenhum outro vértice, inclusive ao v4. Logo, tal grafo não existe. 
4) Prove que em qualquer grafo não trivial existem pelo menos dois vértices de mesmo grau. 
Dica. Em um grafo (simples) com n vértices, todos os graus dos vértices devem ser valores entre 
0 e n-1 (inclusive). Formalmente: (vV) [ d(v)  { 0,1,2,,n-1} ]. 
Temos então n vértices e n valores distintos para os graus destes vértices. Porém, não podemos 
um vértice grau 0 e também um vértice com grau n-1 no mesmo grafo (resultado análogo ao 
exercício 9). 
Assim, apenas n-1 valores distintos serão graus de algum vértice. 
Temos então: n vértices do grafo, e apenas n-1 valores possíveis para seus graus. 
Consequentemente, pelo Princípio das Casas de Pombo, pelo menos dois vértices terão graus 
idênticos. 
5) Existem somente três grafos possíveis: 
 
6) Grafos NÃO isomorfos que sejam 2–regulares com 10 vértices. 
 
 
7) Desenhe dois grafos não isomorfos com 6 vértices e que sejam 3–regulares. 
 
 
8) Grafo com 5 vértices e que seja 3–regular. 
Como cada um dos 5 vértices possui grau 3, o somatório dos graus de todos eles seria 5 x 3 = 15, um valor 
ímpar. Assim, de acordo com os Teoremas 1.1 e 1.2, tal grafo não existe. 
 
9) Grafo com 6 vértices e que seja 4–regular. 
 
 
10) Qual é o número de vértices de um grafo 3-regular com m = 69 arestas? 
Resp.: de acordo com o Teorema 1.1: ∑ 𝑑(𝑣)𝑣∈𝑉 = 3𝑛 = 138 ⟹ 𝑛 = 𝟒𝟔 vértices 
 
11) Qual o número máximo de arestas em um grafo bipartido contendo 30 vértices no total? 
Para todo Kp,q, temos m = p∙q. De acordo com o problema p + q = 30. 
Podemos “distribuir” os 30 vértices pelas duas partições de um grafo bipartido completo, e calcular a 
quantidade de arestas, da seguinte forma: 
 
|E(K1,29)| = 1 ∙ 29 = 29 |E(K2,28)| = 2 ∙ 28 = 56 |E(K3,27)| = 3 ∙ 27 = 81 
… … … 
|E(K10,20)| = 10 ∙ 20 = 200 |E(K11,19)| = 11 ∙ 19 = 209 |E(K12,18)| = 12 ∙ 18 = 216 
|E(K13,17)| = 13 ∙ 17 = 221 |E(K14,16)| = 14 ∙ 16 = 224 |E(K15,15)| = 15 ∙ 15 = 221 
 
Resp.: para o K15,15 temos m = 225. 
 
12) Todo grafo Kn é regular, pois todos os vértices possuem grau n-1. 
O somatório de todos os graus é n x (n-1), valor igual ao dobro do número de arestas (Teorema 1.1). 
Assim: 
Resp.: 𝑛(𝑛 − 1) = 2 × 190 ⟹ 𝑛2 − 𝑛 = 380 ⟹ 𝑛 = 𝟐𝟎 vértices 
 
13) Sabemos que mv
v
2)( 
V
d . Se G é r-regular, nrv
v

V
d )( . Logo, nrm 2 ; e assim 
2
nr
m  . 
14) Para n = 11, existem 6 grafos 2–regulares não isomorfos. Você consegue desenhá-los? 
E para n = 12, quantos existem? 
15) Resposta: número de “grupos” de três vértices contidos no K10. Como ABC e BAC se referem ao mesmo 
triângulo, a resposta se trata, portanto, no número de combinações (e não de permutações) de 3 vértices. 
Resp.: 𝐶10
3 = 
10!
3!∙7!
 = ⋯ = 10 × 3 × 4 = 𝟏𝟐𝟎 triângulos 
 
16) Grafo 2-regular: OU É FORMADO por um ciclo único com todos os vértices; OU É COMPOSTO por um 
conjunto de ciclos todos disjuntos entre si. 
17) Use o Teorema 1.3. Desenhe uma versão isomórfica com uma partição (coluna esquerda) com os vértices a, g, 
f; e outra (a direita) com os vértices b, c, d, e. 
18) Temos p vértices em V1: todos com grau q. Temos q vértices em V2: todos com grau p. Logo: 
pq
qppq
vv
vv
qp  
 22
)()()K(E
21 VV
, dd 
19) Pelo Teorema 1.3, todo grafo estrela, por não conter ciclo de comprimento ímpar, 
é um grafo bipartido. Além disso, todo grafo estrela é um grafo bipartido completo, 
podendo ser notado como K1,n-1. O grafo do exemplo é um K1,6. 
20) Sim; todo grafo estrela é bipartido, e também bipartido completo. O grafo estrela para n = 7 é o grafo K1,6; e 
um grafo estrela qualquer com n vértices ao todo é o K1 , n–1. 
21) Sim. Numere os vértices de G2, e tente redesenhá-lo como um grafo bipartido típico, e constate que a 
representação é idêntica à do grafo G1. 
22) a: o K1,7 tem exatamente 7 arestas. 
23) d: o K4,4 tem exatamente 16 arestas.