Tema 02 - Graus dos Vértices; Grafos Especiais - TEXTO DE APOIO

Prévia do material em texto

NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 8 
1.2 GRAUS DOS VÉRTICES; GRAFOS REGULARES; GRAFOS COMPLETOS; GRAFOS BIPARTIDOS 
• TEOREMA 1.1: A soma dos graus dos vértices de um grafo G(V, E) é um valor par, igual ao dobro 
do nº de arestas de G: 
� d(�)
�∈�
= 2 ⋅ |E| = 2� 
Cada aresta (v,w) contribui com duas unidades para o somatório acima: sendo uma unidade 
para o grau de cada um de seus extremos, d(v) e d(w). Desta forma, o somatório de todos os graus 
dos vértices de V será igual a 2m. 
• TEOREMA 1.2: Em um grafo qualquer, temos uma quantidade par de vértices de grau ímpar. 
Em um grafo G(V,E), podemos particionar o conjunto de n vértices V = Vp ∪ Vi, onde: 
Vp: subconjunto dos vértices de grau par, com np = |Vp| e 
Vi: subconjunto dos vértices de grau ímpar, com ni = |Vi|. 
Note que como Vp e Vi são disjuntos, temos n = np + ni. Seja S o somatório dos graus de 
todos os vértices de V. Sabemos que S é par, e podemos desmembrá-lo em duas parcelas: 
S = Sp + Si, sendo Sp: soma dos np valores pares (todos os graus pares), e 
 Si: soma dos ni valores ímpares (todos os graus ímpares). 
Temos então: 
S = � d(�)
�∈�
= � d(�)
�∈��
+ � d(�)
�∈��
= S� + S� = 2� 
Analisemos Sp e Si separadamente: 
(1) S� = ∑ d(�)�∈�� Como Sp é um somatório de valores pares, Sp é um valor par. 
Sendo S e Sp pares, de S = Sp + Si decorre que Si também será um valor par. 
(2) S� = ∑ d(�)�∈�� Sendo Si par, e consistindo de um somatório de ni valores 
ímpares, decorre que ni é um valor par. 
 
Comprove os teoremas 1.1 e 1.2 no grafo do EXEMPLO 1: 
d(v1) = 0 d(v6) = 1 
d(v2) = 1 d(v7) = 1 
d(v3) = 3 d(v8) = 1 
d(v4) = 4 d(v9) = 2 
d(v5) = 2 d(v10) = 1 
S = 16 np = 4 ni = 6 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 9 
• Grafo regular: 
Um grafo é dito r-regular, ou regular de grau r (para algum r ∈ IN ) se o grau de todos os seus 
vértices tem o mesmo valor r. Formalmente, 
G é r-regular ⇔ (∀ v ∈ V) d(v) = r. Veja o exemplo ilustrado na FIGURA 6. 
 
FIGURA 6 – UM GRAFO 3-REGULAR 
Problema: Qual é o nº de arestas em um grafo r-regular com n vértices? 
• Grafo completo: Kn 
Um grafo G com n vértices é dito completo – e notado Kn – quando existe aresta unindo 
todo par de vértices de G. Formalmente, (∀ v,w ∈ V, v ≠ w) (v,w) ∈ E. 
Veja os exemplos ilustrados na FIGURA 7 a seguir. Observe que são ilustradas DUAS VERSÕES 
ISOMORFAS para o K4. 
 
FIGURA 7 – GRAFOS COMPLETOS 
Como exercício, tente desenhar outros grafos completos. 
Observe que nem todo grafo regular é completo, mas todo grafo completo é regular. Mais 
precisamente, o Kn é um grafo (n-1)-regular. Por exemplo: observe que o K5 é um grafo 4-regular. 
• Número de arestas do Kn – número máximo de arestas em um grafo 
Qual o número máximo de arestas que um grafo G com n vértices pode ter? 
Colocando em outras palavras, quantas arestas tem o Kn? 
A resposta vem da Análise Combinatória: 
Observe que todos os pares de vértices contribuirão com exatamente uma aresta para 
este cálculo. Portanto, a solução consiste em calcular a quantidade de combinações 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 10 
com 2 elementos (pares não-ordenados, que podem ser selecionadas dentre os n 
vértices possíveis. 
|E(K�)| = C� � = �2�� = 
�!
 (� − 2)! ∙ 2! = ⋯ = 
� ∙ (� − 1)
2 = 
�� − �
2 
Aplicando ao K5, temos 
|E(K#)| = C# � = �25� = 
5!
 3! ∙ 2! = ⋯ = 
5 ∙ 4
2 = 10 
Além dos exemplos da FIGURA 7, verifique a fórmula para outros valores de n. 
• Grafo bipartido (ou bipartite): 
Um grafo G(V,E) é dito bipartido (ou bipartite) quando V pode ser particionado em dois 
subconjuntos V1 e V2 (formalmente, V = V1 ∪ V2 sendo V1 ∩ V2 = ∅) de forma que não existam 
arestas unindo vértices de uma mesma partição (subconjunto). 
Formalmente, (u,w) ∈ E  [ {u,w} ⊄ V1 ∧ {u,w} ⊄ V2 ]. A FIGURA 8 ilustra duas 
representações de um mesmo grafo. A representação à direita deixa claro que o grafo é bipartite, 
isolando graficamente as partições V = { A, C } ∪ { B, E, D, F }. Observe que não temos arestas entre 
os vértices A e C, e nem arestas envolvendo exclusivamente os vértices B, E, D, e F. 
 
FIGURA 8 – UM GRAFO BIPARTITE, MOSTRADO EM DUAS VERSÕES ISOMORFAS 
• TEOREMA 1.3: Um grafo G(V,E) é bipartido se e somente se não possui nenhum ciclo de 
comprimento ímpar. 
A prova do TEOREMA 1.3 será omitida, embora possa ser verificada em diversos livros na 
literatura sobre o assunto. 
 
 
 
 
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 11 
• Grafo bipartido completo: 
Um grafo G é bipartido completo é um grafo bipartido que possui arestas unindo todos os 
pares de vértices pertencentes a partições distintas. Formalmente, (∀ u ∈ V1) (∀ w ∈ V2) (u,w) ∈ E. 
Um grafo bipartido completo é notado por Kp,q , onde p = |V1| e q = |V2|, com n = p + q. 
 
FIGURA 9 – GRAFO BIPARTITE COMPLETO: K2,3 
EXERCÍCIOS 1.2 
1) Desenhe TRÊS grafos NÃO isomorfos que sejam 2–regulares com 8 vértices. 
a) 
 
b) 
 
c) 
 
2) Desenhe todos os grafos NÃO isomorfos que sejam 2–regulares com 10 vértices. 
3) Desenhe dois grafos diferentes (não isomorfos) com |V| = 6 e que sejam 3-regulares. 
4) Qual é o nº de arestas em um grafo r-regular com n vértices? 
5) Existe algum grafo com |V| = 6 e que seja 4-regular? Você consegue desenhar um? 
6) Existe algum grafo com |V| = 5 e que seja 3-regular? Você consegue desenhar um? 
7) Quantos grafos distintos (não isomorfos) 2-regulares com 10 vértices você consegue 
desenhar? E 2-regulares com 11 vértices? E 2-regulares com 12 vértices? 
8) Caracterize um grafo 2-regular. 
9) Você consegue desenhar algum grafo 3-regular com 6 vértices? E com 8 vértices? 
Caracterize o número de vértices em grafos 3-regulares; ou seja: que valores de n admitem 
tais grafos, e que valores não admitem? 
10) Seja G um grafo formado por um único ciclo simples contendo todos os seus vértices. 
G é bipartido? Justifique sua resposta. 
11) O Kn é bipartido? Para quais valores? Para que valores ele não é bipartido? 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 12 
12) Todo grafo 2-regular (conexo ou não) é bipartido? 
13) O grafo G abaixo é bipartido? Prove sua resposta. Caso seja, desenha uma representação 
isomórfica para G que evidencie esta condição: separe as partições em duas colunas para 
melhor visualização. 
 
14) Quantas arestas tem o Kp,q , para p e q quaisquer? 
15) Um grafo estrela (com n vértices) tem um vértice com grau n-1, e n-1 vértices com grau 1 
(veja exemplo abaixo, onde n = 7). Um grafo estrela é bipartido? É bipartido completo? 
 
16) Os grafos G1 e G2 são isomorfos? 
 
17) Qual o número mínimo de arestas em um grafo bipartido completo com n = 8 vértices? 
a) Entre 1 e 7 arestas. 
b) Entre 8 e 11 arestas. 
c) entre 12 e 15 arestas. 
d) Entre 16 e 18 arestas. 
e) Mais que 19 arestas. 
18) Qual o número máximo de arestas em um grafo bipartido completo com n = 8 vértices? 
a) Entre 1 e 7 arestas. 
b) Entre 8 e 11 arestas. 
c) entre 12 e 15 arestas. 
d) Entre 16 e 18 arestas. 
e) Mais que 19 arestas. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 13 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) Existem somente três grafos possíveis: 
 
 
2) Dica: apenas cinco grafos são possíveis. 
4) Sabemos que mv
v
2)( =
∈ V
d . Se G é r-regular, nrv
v
=
∈V
d )( . Logo, nrm =2 ; e assim 
2
nr
m = . 
5) 
 
6) Dica: Aplique os teoremas 1.1 ou 1.2. 
7) Com n = 10 existem 5 grafos 2–regulares não isomorfos. Você consegue desenhá-los? 
Com n = 11 existem 6 grafos 2–regulares não isomorfos. Você consegue desenhá-los? 
E para n = 12, quantos existem? 
8) 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. 
10) Dica: use o Teorema 1.3 para sua resposta. 
Teste alguns exemplos de grafos contento um número par ou ímpar de vértices. 
11) Use o Teorema 1.3. 
12)Use o Teorema 1.3. 
13) 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. 
14) 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 
15) 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. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 14 
16) 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.a 
17) a: o K1,7 tem exatamente 7 arestas. 
18) d: o K4,4 tem exatamente 16 arestas.