Notas de aula - Grafos

Prévia do material em texto

NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
GRAFOS 
 
 
 
 
 
 
 
 
 
NOTAS DE AULA 
 
 
 
 
PROF.: JÚLIO TADEU CARVALHO DA SILVEIRA 
 
 
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 2 
 
SUMÁRIO 
1. GRAFOS........................................................................................................................................................... 3 
1.1 DEFINIÇÕES E TERMINOLOGIA....................................................................................................................... 3 
1.2 GRAFOS BIPARTIDOS ................................................................................................................................. 12 
1.3 REPRESENTAÇÕES COMPUTACIONAIS DE GRAFOS ........................................................................................... 14 
1.4 GRAFOS DIRECIONADOS (DIGRAFOS), GRAFOS PONDERADOS .......................................................................... 17 
2. CONECTIVIDADE, PLANARIDADE, COLORAÇÃO ..................................................................................................... 21 
2.1 GRAFOS SIMPLES – CAMINHOS, CICLOS, GRAFOS EULERIANOS E HAMILTONIANOS .............................................. 21 
2.2 CAMINHOS E CICLOS EM GRAFOS PONDERADOS E/OU DIRECIONADOS............................................................... 27 
2.3 SUBGRAFOS, CONECTIVIDADE, EMPARELHAMENTOS ...................................................................................... 29 
2.4 PLANARIDADE .......................................................................................................................................... 35 
2.5 COLORAÇÃO DE VÉRTICES ........................................................................................................................... 38 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 3 
1. GRAFOS 
1.1 DEFINIÇÕES E TERMINOLOGIA 
As definições a seguir se aplicam a grafos simples não direcionados. 
 Grafo (ou grafo simples) 
Um grafo G é um par G = (V, E), onde: 
V ou V(G) é um conjunto não vazio. 
Seus elementos são denominados vértices (ou nós) de G. 
E ou E(G) é um conjunto de pares não–ordenados de elementos distintos de V. 
Seus elementos são denominados arestas (edges) de G. 
O nome grafo decorre de que esta estrutura admite uma representação geométrica. 
EXEMPLO 1: G = (V, E), com |V| = 10 e |E| = 8 
V = { v1, v2, v3, v4, v5, v6, v7, v8, v9, v10 } 
E = { {v2,v3}, {v3,v4}, {v4,v5}, {v5,v3}, {v4,v6}, {v7,v4}, {v8,v9}, {v9,v10} } 
Representação geométrica 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5
 
FIGURA 1 – REPRESENTAÇÃO GEOMÉTRICA DO GRAFO DO EXEMPLO 1. 
Uma aresta é especificada pelos seus vértices extremos: e = {u,v} = {v,u}. 
Outras notações: e = uv = vu ou ainda e = v-w = w-v 
Alguns autores também usam a notação de par ordenado (v,w), utilizada em grafos 
direcionados, para especificar um par não-ordenado quando o contexto estiver implícito. 
No grafo do EXEMPLO 1, v2  V e {v5,v3}  E. 
Ou então (v5,v3)  E 
 v3-v5  E 
 v5v3  E. 
 CONVENÇÃO: 
 n = |V| e m = |E|. No grafo do EXEMPLO 1, temos n = 10 e m = 8. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 4 
 Vértices adjacentes e vértice isolado 
Vértices unidos por uma aresta são denominados adjacentes. No EXEMPLO 1, o vértice v3 é 
adjacente aos vértices v2, v4 e v5. Um vértice isolado não tem vértices adjacentes. No EXEMPLO 1, v1 
é um vértice isolado. 
 Aresta incidente: uma aresta é dita incidente aos seus dois vértices extremos. 
No EXEMPLO 1, a aresta (v2,v3) é incidente a v2 e a v3. 
 Arestas adjacentes: duas arestas que possuem vértice extremo em comum. 
No EXEMPLO 1, a aresta (v2,v3) é adjacente à aresta (v4,v3). 
 Pseudografos e Multigrafos 
É possível estender a definição de um grafo de forma a permitir arestas do seguinte tipo: 
 Laços (loops): arestas da forma (v,v), unindo um vértice a si mesmo; 
 Arestas paralelas: e1 = (v,w) e e2 = (v,w); ou seja, duas arestas distintas que unem o 
mesmo par de vértices. 
Um grafo que possua laços é denominado pseudografo; um grafo que contenha arestas 
paralelas é denominados multigrafos, como ilustrado na FIGURA 2. 
3
2
1
4
 
FIGURA 2 – PSEUDOGRAFO E MULTIGRAFO. 
Neste estudo NÃO ABORDAREMOS pseudografos e multigrafos: o termo grafo sempre será 
utilizado para designar um grafo simples (sem laços nem arestas paralelas). 
 GRAFO TRIVIAL: 
O grafo em que |V| = 1 é denominado grafo trivial. 
v4
 
FIGURA 3 – GRAFO TRIVIAL: n = 1, E =  
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 5 
 Grau de um vértice 
Denomina-se grau de um vértice v, notando-se grau(v) ou d(v), ao número de arestas que 
sejam incidentes a v. Ou, de forma equivalente, ao número de vértices adjacentes a v. A notação 
d(v) refere-se ao termo degree (inglês). 
Observe que d(v)  IN ; se d(v) = 0 então v é um vértice isolado. 
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 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5
 
 Isomorfismo 
Dois grafos G1(V1,E1) e G2(V2,E2) são isomorfos se existe uma bijeção f: V1  V2 que 
preserve as adjacências entre seus respectivos vértices. Ou seja: 
|V1| = |V2| 
|E1| = |E2| 
(v,w)  E1  ( f(v) , f(w) )  E2. 
Em outras palavras, rearranjamos a disposição dos vértices (que podem até mesmo ser 
renomeados) de forma que as arestas do “novo” grafo correspondam às mesmas arestas (e seus 
respectivos vértices extremos) do grafo original. 
Como consequência da definição acima, é imediato verificar que |V1| = |V2| e |E1| = |E2| 
são condições necessárias (mas não suficientes) para o isomorfismo. Veja o exemplo ilustrado na 
FIGURA 4 abaixo, e complete o quadro a seguir: 
v2
v7
v6
v3
v4v1
v5
e
b
d
a
c
g
f
G1 G2 
FIGURA 4 – GRAFOS ISOMORFOS. 
Complete: f(v1) = f(v2) = f(v3) = f(v4) = 
f(v5) = f(v6) = f(v7) = 
Resposta: f(v1) = g f(v2) = e f(v3) = a f(v4) = c 
f(v5) = f f(v6) = b ou d f(v7) = b ou d 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 6 
O isomorfismo entre grafos pode ser visualizado mesmo sem rotularmos os vértices (apenas 
identificando a mesma estrutura de conectividades), como na FIGURA 5 a seguir. 
G1 G2 G3 G4 
FIGURA 5 – ISOMORFISMO: G1 E G2 SÃO ISOMORFOS. G3 E G4 SÃO ISOMORFOS 
 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: 
mv
v
2||2)( 

Ed
V
 
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: 



IP VV
IP
V
dd(SSdS
ip v
i
v
p
v
vvv )())( 
Analisemos SP e SI separadamente: 
(1) SP = 
 PV
d
pv
pv )( Como SP é um somatório de valores pares, SP é um valor par. 
Sabemos que S e SP são pares, e de S = SP + SI decorre que SI também será um valor par. 
(2) SI = 
 IV
d
iv
iv )( Como SI é par, e consiste em um somatório de nI valores ímpares, 
decorre que nI é um valor (quantidade de vértices) par. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 7 
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 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5 
 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. 
K1 K2 K3 K4 K4 K5 
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. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 8 
 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 outros termos, quantas arestas tem o Kn? 
A resposta vem da Análise Combinatória: 
A solução consiste em calcular a quantidade de combinações com 2 elementos (pares 
não-ordenados, que podem ser selecionadas dentre os n vértices possíveis. 
22
)1(
!2!)1(
!2
)(
2
2 nnnn
n
n
n
nn











 CKE 
Aplicando ao K5, temos 10
2
45
)K(E 5 

 
Além dos exemplos da FIGURA 7, verifique a fórmula para outros valores de n. 
EXERCÍCIOS 1.1 
1) Construir uma representação geométrica do grafo a seguir: 
V = { A, B, C, D, E, F } 
E = { {A,C}, {A,D}, {A,E}, {B,C}, {B,D}, {B,E}, {C,E}, {D,E} } 
2) Caracterize os conjuntos V e E de cada uma das representações a seguir: 
 a) 
3
2
1
64
5
G1 
V1 = { 
E1 = { 
 b) 
3
2
1
64
5
G2 
V2 = { 
E2 = { 
3) Desenhe os grafos G3 e G4, obtidos do G1 (questão 2) através dos isomorfismos indicados: 
 c) 
 
D
B
A F
C
E
G3 
f : V1  V3 f (1) = A f (2) = B f (3) = C 
 f (4) = D f (5) = E f (6) = F 
 d) 
 
4
2
1 6
3
5
G4
 
g : V1  V4 
g(i) = 7 – i 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 9 
 
4) Calcule d(v) para cada vértice dos grafos G1 e G2 anteriores. 
Verifique se G1 e G2 satisfazem os teoremas 1.1 e 1.2. 
5) Desenhe todos os grafos distintos (não isomorfos) contendo 2, 3 ou 4 vértices. 
6) Existe algum grafo com 6 vértices, cujos graus são 0, 1, 2, 3, 4, 5? 
7) Desenhe algum grafo com 6 vértices, cujos graus são 2, 3, 3, 3, 3, 3; ou prove porque tal grafo 
não existe. 
8) Desenhe um grafo com 10 vértices, em todos os vértices tenham grau 1; ou prove que não 
existe grafo com tais características. 
9) Existe algum grafo com 5 vértices, cujos graus são 0, 1, 2, 3, 4? Por que? 
10) Prove que em qualquer grafo não trivial existem pelo menos dois vértices de mesmo grau. 
11) Desenhe todos os grafos não isomorfos que tenham o mesmo número de vértices e também 
o mesmo número de arestas. Faça isso para n = 3, 4, 5. 
12) Quantos grafos não isomorfos com 5 vértices de graus 1, 1, 1, 1, 2, você consegue desenhar? 
13) Quantos grafos não isomorfos com 5 vértices de graus 1, 1, 1, 2, 3, você consegue desenhar? 
14) Quantos grafos não isomorfos com 6 vértices de graus 1, 1, 1, 1, 1, 3, você consegue 
desenhar? 
15) Desenhe dois grafos NÃO isomorfos com 6 vértices, que tenham graus 1, 1, 1, 2, 2, 3. 
D
B
A F
C
E
 
D
B
A F
C
E
 
16) Desenhe TRÊS grafos NÃO isomorfos que sejam 2 regulares com 8 vértices. 
a) 
 
b) 
 
c) 
 
 
17) Desenhe dois grafos diferentes (não isomorfos) com |V| = 6 e que sejam 3-regulares. 
18) Qual é o nº de arestas em um grafo r-regular com n vértices? 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 10 
19) Existe algum grafo com |V| = 6 e que seja 4-regular? Você consegue desenhar um? 
20) Existe algum grafo com |V| = 5 e que seja 3-regular? Você consegue desenhar um? 
21) 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? 
22) Caracterize um grafo 2-regular. 
23) 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? 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
3) 
c) 
D
B
A F
C
E
G3 
d) 
4
2
1 6
3
5
G4 
5) 
 
6) Existe algum grafo com 6 vértices, cujos graus são 0, 1, 2, 3, 4, 5? 
Não. Demonstre esta impossibilidade a partir dos teoremas 1.1 ou 1.2. 
7) Desenhe algum grafo com 6 vértices, cujos graus são 2, 3, 3, 3, 3, 3; ou prove porque tal grafo 
não existe. 
Não. Demonstre esta impossibilidade a partir dos teoremas 1.1 ou 1.2. 
8) 
 
9) 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, e sejam os vértices v0 e v5 tais que d(v0) = 0 e d(v5) =5. 
Assim, o vértice v5 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 v5. Logo, tal grafo não existe. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 11 
10) 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 da Cada de Pombos, pelo menos dois vértices terão 
graus idênticos. 
12) 
 
Existe algum outro? 
13) 
 
Existe algum outro? 
14) Dica: existem apenas dois grafos possíveis. 
15) 
D
B
A F
C
E
 
D
B
A F
C
E
 
18) 
Sabemos que mv
v
2)( 
V
d . Se G é r-regular, nrv
v

V
d )( . Logo, nrm 2 ; e assim 
2
nr
m  . 
19) 
 
20) Dica: Aplique os teoremas 1.1 ou 1.2. 
21) Com n = 10 existem 5 grafos não–regulares não isomorfos. Você consegue desenhá-los? 
 Com n = 11 existem 6 grafos não–regulares não isomorfos. Você consegue desenhá-los? 
 E para n = 12, quantos existem? 
22) Descreva a estrutura do grafo. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 12 
1.2 GRAFOS BIPARTIDOS 
 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 }. 
A
D
C
B E
F
A
DC
B
E
F 
FIGURA 8 – UM GRAFO BIPARTITE, MOSTRADO EM DUAS VERSÕES ISOMORFAS 
 TEOREMA 1.3: Um grafo G(V,E) ´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. 
 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| = q, com n = p + q. 
 
FIGURA 9 – GRAFO BIPARTITE COMPLETO: K2,3 
EXERCÍCIOS 1.2 
1) Seja G um grafo formado por um único ciclo simples contendo todos os seus vértices. 
G é bipartido? 
2) O Kn é bipartido? Para quais valores? Para que valores ele não é bipartido? 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 13 
3) Todo grafo 2-regular (conexo ou não) é bipartido? 
4) 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. 
e
b
d
a
c
g
f
 
5) Quantas arestas tem o Kp,q , para p e q quaisquer? 
6) 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? 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) Dica: use o Teorema 1.3 para sua resposta. 
 Teste alguns exemplos de grafos contento um número par ou ímpar de vértices. 
2) Use o Teorema 1.3. 
3) Use o Teorema 1.3. 
4) Use o Teorema 1.3. Uma partição (coluna) terá 3 vértices, e a outra terá 4 vértices. 
5) 
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 . 
6) 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 
1.3 REPRESENTAÇÕES COMPUTACIONAIS DE GRAFOS 
Muitas aplicações práticas utilizam modelagem que utilizem determinados grafos, sobre os 
quais serão implementados algoritmos para resolução de problemas específicos. 
As duas estruturas de dados mais utilizadas para representação computacional de grafos são 
as matrizes de adjacências e as listas de adjacências, descritas a seguir. Uma terceira forma, 
menos utilizada é a matriz de incidências, que não será coberta neste estudo. 
 Matriz de Adjacências: 
Uma típica matriz de adjacências de um grafo G = (V, E) é uma matriz An×n definida como: 
 1 ≤ i ≤ n: A[i][i] = 0 vi não é adjacente a si mesmo 
 1 ≤ i , j ≤ n, i ≠ j, A[i][j] = A[j][i] = 1 se vi e vj são adjacentes 
 0 caso contrário. 
A FIGURA 10 ilustra uma típica matriz de adjacências para o grafo do EXEMPLO 1. 
































0100000000
1010000000
0100000000
0000001000
0000001000
0000001100
0001110100
0000011010
0000000100
0000000000
10
9
8
7
6
5
4
3
2
1
10987654321
 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5
 
FIGURA 10 – MATRIZ DE ADJACÊNCIAS PARA O GRAFO DO EXEMPLO 1 
Observe que a matriz de adjacências possui as seguintes características: 
 É uma matriz quadrada; 
 Todos os elementos da diagonal principal são nulos; 
 Ela é simétrica em relação à diagonal principal. 
 Listas de Adjacências 
Dependendo da razão entre a quantidade de arestas e o número de vértices do grafo, 
podemos ter um percentual muito pequeno de elementos não nulos na matriz de adjacências, 
configurando o que se denomina matriz esparsa. Normalmente este desperdício de memória não 
é um problema muito relevante. 
Porém, em determinadas aplicações, a quantidade de grafos (e vértices) pode ser de 
considerável magnitude, e a quantidade de memória pode se tornar um fator relevante. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 15 
Uma forma alternativa de armazenamento computacional de grafos é a representação em 
listas de adjacências, como ilustrado na FIGURA 11 a seguir. 
v7
v4
v3
v1
v2
v3
v4
v5
v6
v7
v8
v9
v10
v5
v9
v8 v10
v9
v4
v4
v4 v3
v3 v5 v6
v3 v2
 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5
FIGURA 11 – LISTAS DE ADJACÊNCIAS PARA O GRAFO DO EXEMPLO 1 
Nesta estrutura, temos uma lista encadeada associada a cada vértice v. Esta lista contém nós 
para todos os vértices adjacentes a ele. O uso de memória para representar “arestas inexistentes” 
é evitado, o que não acontece na matriz de adjacências. 
A economia de memória tem um preço. Na matriz de adjacências, descobrimos se uma 
aresta (v,w)  E de forma imediata: basta verificarmos A[v][w] ou A[w][v]. Já com listas de 
adjacências, devemos percorrer os nós relativos ao vértice v (ou w) para descobrirmos se tal 
aresta existe. 
Temos então um balanço espaço versus desempenho, que deve ser avaliado para a escolha 
da estrutura mais adequada a uma determinada aplicação. 
EXERCÍCIOS 1.3 
1) Desenhe as matrizes e listas de adjacências dos grafos a seguir: 
 a) 
3
2
1
64
5
b) 
CG
E
B
FD
A
 
2) Desenhe uma representação da matriz de adjacências do K4. Quais são as características da 
matriz de adjacências do Kn? Quantos elementos nulos existem? Quantos não nulos? 
3) Quais são as características da matriz de adjacências de um grafo r-regular com n vértices? 
Quantos elementos nulos e não nulos existem em tal matriz? 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 16 
4) Caracterize um grafo cuja matriz de adjacências tenha uma linha com todos os elementos 
nulos. O que você pode dizer da lista de adjacências deste grafo? 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
3) Caracterize as linhas e colunas da matriz. 
 Obtenha uma expressão em função de n e k. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 17 
1.4 GRAFOS DIRECIONADOS (DIGRAFOS), GRAFOS PONDERADOS 
Alguns problemas poder exigir uma modelagem que utilize extensões da definição usual de 
um grafo simples. Em determinado problemas de otimização, pode ser necessário que a cada 
aresta seja associado um peso (valor). Outras aplicações exigem que as arestas sejam orientadas 
(modeladas como pares ordenados), indicando um sentido no percurso da aresta em questão. 
 Digrafo 
Um grafo direcionado (ou digrafo) G possui arestas orientadas. Uma aresta orientada é um 
par ordenado de vértices distintos de G. 
Desta forma, uma aresta orientada e será representada como e = (v,w), onde v,w  V, e 
v ≠ w. Neste caso, a aresta (v,w) possui uma única direção: do vértice v para o vértice w. Dizemos 
que a aresta (v,w) é divergente de v e convergente a w. 
 EXEMPLO 2 
Na representação geométrica de um digrafo, as arestas são representadas como setas 
indicativas de direção, conforme ilustrado na FIGURA 12. 
V = { a, b, c, d, e, f, g } 
E = { (a,b), (a,c), (d,a), (d,g), 
 (g,e), (f,g), (e,f), (f,e) } 
c
b
a
g
f
e
d
 
FIGURA 12 – GRAFO DIRECIONADO 
 Digrafos – graus de um vértices, fontes, sumidouros 
Para qualquer vértice v em um dígrafo, definimos: 
grau de entrada de v – in(v): número de arestas convergentes a v (in-degree) 
grau de saída de v – out(v): número de arestas divergentes a v (out-degree) 
No digrafo do EXEMPLO 2, temos: 
in(a) = 1 out(a) = 2 
in(b) = 1 out(b) = 0 
in(c) = 1 out(c) = 0 
in(d) = 0 out(d) = 2 
in(e) = 2 out(e) = 1 
in(f) = 1 out(f) = 2 
in(g) = 2 out(g) = 1 
c
b
a
g
f
e
d
 
FIGURA 13 – GRAUS DE ENTRADA E SAÍDA DO DIGRAFO DO EXEMPLO 2 
Se um vértice tem grau de entrada igual a ZERO, este vértice é chamado fonte. Já um vértice 
cujo grau de saída seja ZERO é chamado sumidouro. No EXEMPLO 2, temos que o vértice d é uma 
fonte, e os vértices b e c são sumidouros. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 18 
 Digrafos – Matriz de Adjacências 
























000000
00000
000000
00000
0000000
0000000
00000
1
11
1
11
11
g
f
e
d
c
b
a
gfedcba
 
c
b
a
g
f
e
d
 
FIGURA 14 – MATRIZ DE ADJACÊNCIAS PARA O DIGRAFO DO EXEMPLO 2 
 Grafos Ponderados 
Em determinadas aplicações, podemos atribuir valores às arestas de um grafo qualquer, seja 
ele direcionado ou não. Formalmente,a cada aresta (v,w) – ou vw em grafos não ponderados –
 será atribuído um peso, tipicamente um valor associado a um custo ou ganho quando tal aresta 
for selecionada ou “percorrida”. Temos então um grafo dito ponderado. 
 EXEMPLO 3: GRAFO PONDERADO 
v3v2
9
v1 v6
4
v7
3
v4
v5
10
6
12
5
8
7
 
FIGURA 15 – GRAFO PONDERADO 
 Matriz de Adjacências em grafos ponderados 
Em um grafo ponderado, o peso de uma aresta vw será atribuído ao seu respectivo 
elemento A[v][w] da sua matriz de adjacências. 
Em aplicações envolvendo grafos, os pesos das arestas geralmente estarão associados a 
funções de ganhos ou a custos, dependendo do tipo de problema considerado. A partir da 
modelagem em um grafo, é elaborar um algoritmo que minimize uma determinada função. Casos 
típicos envolvem a minimização de (funções de) custos ou maximização de (funções de) ganhos. 
Em problemas de otimização, um elemento da matriz cuja aresta não pertence ao grafo 
geralmente recebe um valor muito grande, quando o problema envolve custo, ou muito pequeno, 
quando são computados ganhos. Formalmente, usamos a notação ∞ ou –∞ nestes casos. A figura 
a seguir ilustra a matriz de adjacências do EXEMPLO 3, considerando os pesos como custos 
associados a cada aresta. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 19 
 































37
4
510
34512
101298
96
786
7
6
5
4
3
2
1
7654321
v
v
v
v
v
v
v
vvvvvvv
 
v3v2
9
v1 v6
4
v7
3
v4
v5
10
6
12
5
8
7
 
FIGURA 16 – MATRIZ DE ADJACÊNCIAS PARA O GRAFO DO EXEMPLO 3 
 EXEMPLO 4: DIGRAFOS PONDERADOS 
Os mesmos conceitos de grafos ponderados também se aplicam a grafos direcionados. 
c
b
a
g
f
e
d
5
11
487 7
8
6
 
FIGURA 17 – DIGRAFO PONDERADO 
A matriz de adjacências do grafo do EXEMPLO 4 é representada a seguir, onde os pesos são 
associados a uma função de custo. 































6
87
4
118
75
g
f
e
d
c
b
a
gfedcba
 
c
b
a
g
f
e
d
5
11
487 7
8
6
 
FIGURA 18 – MATRIZ DE ADJACÊNCIAS PARA O DIGRAFO DO EXEMPLO 4 
EXERCÍCIOS 1.4 
1) Preencha os elementos de matriz de adjacências do dígrafo abaixo: 
C
FE
B
D
A






















______
______
______
______
______
______
FEDCBA
F
E
D
C
B
A
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 20 
 
2) Indique os graus de entrada e de saída dos vértices do digrafo da questão 1): 
in(A) = out(A) = 
in(B) = out(B) = 
in(C) = out(C) = 
in(D) = out(D) = 
in(E) = out(E) = 
in(F) = out(F) = 
Existe alguma fonte ou sumidouro no digrafo acima? Indique quais. 
3) Considere a seguinte definição de um digrafo não-ponderado abaixo: 
EM PASCAL: 
const 
 MAX = 100; 
 
var 
 A: array[1..MAX,1..MAX] of integer; 
 
 n: integer; { Número de vértices } 
 
EM C: 
#define MAX 100 
 
int A[MAX][MAX]; 
 
int n; // Núm. de vértices 
 
A partir das definições acima, escreva o código de duas funções, grauentrada(v) e 
grausaida(v), que retornam, respectivamente, os graus de entrada e de saída de um vértice, 
passado como parâmetro – o valor v é o índice do vértice na matriz de adjacências. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 21 
2. CONECTIVIDADE, PLANARIDADE, COLORAÇÃO 
2.1 GRAFOS SIMPLES – CAMINHOS, CICLOS, GRAFOS EULERIANOS E HAMILTONIANOS 
 caminho, caminho simples, comprimento de um caminho1 
Um caminho em um grafo é uma sequência de vértices tal que quaisquer dois vértices 
consecutivos na sequência sejam adjacentes no grafo. Formalmente, um caminho em G(V,E) é 
uma sequência P = u1, u2,  uk de elementos de V tal que, (ui, ui+1)  E, para i = 1, 2, , k-1. 
O comprimento de um caminho em um grafo simples é o nº de arestas “tomadas” no 
percurso. Ou seja, u1, u2,  uk é um caminho (sequência) com k vértices e de comprimento k-1. 
Neste caso, o vértice u1 é chamado origem do caminho, e uk é o vértice destino. 
No grafo do EXEMPLO 1, podemos enumerar alguns caminhos e seus respectivos 
comprimentos: 
 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5 
Em todos os caminhos exemplificados acima, v2 é a origem e v6 o destino; e também 
dizemos que v2 alcança ou atinge v6. 
Um caminho simples em um grafo G é um caminho em que todos os vértices são distintos; 
ou seja, não temos vértices repetidos. Dos caminhos exemplificados acima, apenas os dois últimos 
são caminhos simples de v2 a v6. Observe que, embora nem todo caminho seja simples, todo 
caminho simples é um caminho. 
 caminho mínimo e distância 
Um caminho mínimo entre dois vértices vi e vj é um caminho de comprimento mínimo 
dentre todos os possíveis caminhos entre eles. Um caminho mínimo (também chamado caminho 
mais curto ou caminho de comprimento mínimo) pode não ser único, podendo existir outros 
caminhos de igual comprimento. Porém nenhum outro caminho tem comprimento menor que o 
do caminho mínimo. 
Observe que um caminho mínimo é necessariamente um caminho simples. No grafo do 
EXEMPLO 1, o caminho v2,v3,v4,v5,v3,v4,v6 certamente não é um caminho mínimo. 
 
1
 Alguns autores utilizam os termos passeio (para caminho) e caminho (para caminho simples). 
v2,v3,v4,v5,v3,v4,v6 comprimento 6 
v2,v3,v4,v3,v4,v6 comprimento 5 
v2,v3,v4,v6 comprimento 3 
v2,v3,v5,v4,v6 comprimento 4 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 22 
A distância entre dois vértices v e w, denotada por d(v,w), é definida como o comprimento 
de um caminho mínimo entre eles. No grafo do EXEMPLO 1, a d(v2,v6) = 3, pois v2,v3,v4,v6 é um 
caminho mínimo entre eles (verifique que não existe um caminho menor). 
 Ciclo, ciclo simples2 
Um ciclo é um caminho de comprimento mínimo TRÊS, em que os vértices origem e destino 
são coincidentes: o percurso “volta” ao vértice inicial. Se todo o caminho da origem ao penúltimo 
vértice for um caminho simples, temos então um ciclo simples: todos os vértices exceto o último 
são distintos. No EXEMPLO 1 temos: 
v2,v3,v2 NÃO é um ciclo, apenas um caminho de comprimento 2 
v2,v3,v4,v5,v3,v2 é um ciclo de comprimento 5 
v3,v4,v5,v3 é um ciclo simples (caminho simples de v3 a v5) de comprimento 3 
Dois ciclos são considerados idênticos se um deles puder ser obtido do outro através da 
rotação de seus vértices ou pela inversão no sentido do percurso. Assim, observe que TEMOS APENAS 
UM CICLO no grafo do EXEMPLO 1: C = <v3,v4,v5,v3>. Os ciclos <v4,v5,v3,v4>, <v5,v3,v4,v5>, 
<v3,v5,v4,v3>, <v5,v4,v3,v5>, e <v4,v3,v5,v4> são todos idênticos ao ciclo C. 
v3
v4
v5 
FIGURA 19 – ÚNICO CICLO SIMPLES DO GRAFO DO EXEMPLO 1: <v3,v4,v5,v3> 
Finalmente, um grafo acíclico é um grafo que não possui nenhum ciclo. 
 Grafo conexo 
Um grafo G = (V, E) é conexo se, para todo par de vértices v,w  V, existe um caminho entre 
v e w. Ou seja, temos todos os nós de um grafo conexo conectados por algum caminho possível. 
Se existirem dois vértices quaisquer sem caminho entre eles, o grafo é dito desconexo. Por 
exemplo, o grafo do EXEMPLO 1 é dito desconexo: não existe caminho entre os vértices v2 e v10. 
Observe que a representação gráfica de um grafo desconexo é uma figura necessariamente 
descontínua. 
 Grafos hamiltonianos, grafos eulerianos 
Um caminho hamiltoniano é um caminho que contenha cada vértice do grafo exatamente 
uma vez. Em outras palavras, um caminho hamiltoniano é um caminho simples que contém todos 
 
2
 Alguns autores utilizam os termos passeio fechado (para ciclo) e ciclo (para ciclo simples). 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 23 
os vértices do grafo. Um ciclo em que todos os vértices da origem até o penúltimo vértice formam 
um caminho hamiltoniano é chamado ciclo hamiltoniano. Um grafo que possui algum ciclo 
hamiltonianoé chamado grafo hamiltoniano. 
Um caminho que contenha cada aresta do grafo exatamente uma vez é chamado caminho 
euleriano. Um ciclo que contenha cada aresta do grafo exatamente uma vez é chamado ciclo 
euleriano. Um grafo que possui um ciclo euleriano é chamado grafo euleriano. 
Como exemplo, para o grafo representado a seguir (FIGURA 20), temos: 
Caminho hamiltoniano: E,D,C,A,B Ciclo hamiltoniano: A,C,E,D,B,A 
Caminho euleriano: C,E,D,C,A,B,D Ciclo euleriano: existe algum? 
C
E
B
D
A
 
FIGURA 20 – CAMINHOS (E CICLOS) HAMILTONIANOS E EULERIANOS. 
Um grafo G admite algum caminho ou ciclo euleriano? Caso afirmativo, como identificá-los? 
Um grafo G admite algum caminho ou ciclo hamiltoniano? Caso afirmativo, como identificá-los? A 
primeira questão é mais simples, e pode ser respondida pelos teoremas a seguir. Identificar ciclos 
ou caminhos hamiltonianos é um problema mais complexo. 
 TEOREMA 1.4: Um grafo conexo é euleriano se e somente se todos os seus vértices possuem 
grau par (nenhum vértice tem grau ímpar). 
A prova do teorema pode ser feita duas partes: 
i. G é euleriano  todo vértice de G tem grau par 
ii. Todo vértice de G tem grau par  G é euleriano 
Veremos a seguir uma demonstração da parte ii, que se baseia em um algoritmo para a 
obtenção de um ciclo euleriano para G conexo com todos os vértices de grau par. A prova 
completa do teorema 1.4 será omitida. 
Seja um grafo G, conexo e com todos os vértices de grau par. Certamente G possui um ciclo 
C1 (por que?). Se tal ciclo possui todas as arestas do grafo, temos então um ciclo euleriano. Caso 
contrário, remova de G todas as arestas em C1, e também os vértices que se tornarem isolados 
após esta operação. O grafo resultante admite outro ciclo C2 (novamente: por que?). Repete-se o 
processo: remove-se as arestas do ciclo encontrado (e vértices isolados), e procura-se novo ciclo, 
removendo suas arestas e vértices isolados, até que não reste nenhuma aresta no grafo 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 24 
resultante. Ao final, teremos k ciclos C1, C2, …, Ck. Pelo menos dois destes ciclos possuem um 
vértice em comum, e podemos uni-los em um único ciclo. No conjunto de ciclos resultante, 
repete-se o processo de união de ciclos com vértice em comum, até que tenhamos um único ciclo 
resultante de todas as uniões, que certamente é um ciclo euleriano. Veja o exemplo a seguir. 
CG
E
B
FD
A
 
FIGURA 21 – UM GRAFO COM UM CICLO EULERIANO - C,E,D,F,E,G,C,A,B,D,C 
PASSO 1 PASSO 2 PASSO 3 
C1 = G,C,E,G C12 = C1  C2 = E,G,C,E,D,F,E (C12)  C3 = C,E,D,F,E,G,C,A,B,D,C 
C2 = D,F,E,D C3 = A,B,D,C,A 
C3 = A,B,D,C,A 
 TEOREMA 1.5: Um grafo conexo possui caminho euleriano se e somente se 
 i. nenhum de seus vértices possui grau ímpar, ou 
 ii. exatamente dois de seus vértices possuem grau ímpar. 
O primeiro caso satisfaz o TEOREMA 1.4, e temos um ciclo euleriano. 
No segundo caso, o caminho euleriano não é um ciclo, e deve começar em um 
dos vértices de grau ímpar e terminar no outro. 
Embora a prova do TEOREMA 1.5 seja omitida, verifique que o grafo da FIGURA 20 satisfaz este 
teorema e não satisfaz o TEOREMA 1.4. 
 Comentários sobre o TEOREMA 1.5: 
Pelo Teorema 1.2, sabemos que qualquer grafo contém uma QUANTIDADE PAR de vértices com 
grau ímpar. Se esta quantidade for: 
 ZERO: o grafo admite um ciclo euleriano; 
 DOIS: o grafo admite um caminho euleriano, mas não um ciclo euleriano; 
 QUALQUER OUTRO VALOR PAR: o grafo não admite caminho euleriano. 
EXERCÍCIOS 2.1 
1) Desenhe CINCO grafos não isomorfos com 10 vértices e 2-regulares (conexos ou desconexos). 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 25 
 
2) Prove que o Kn é conexo. 
3) Existe algum grafo com 6 vértices e que seja conexo e 2-regular? 
Existe algum grafo com 6 vértices e que seja desconexo e 2-regular? 
4) Existe algum grafo com 6 vértices e que seja conexo e 3-regular? 
Existe algum grafo com 6 vértices e que seja desconexo e 3-regular? 
5) Qual é o número mínimo de arestas em um grafo conexo com n vértices? 
6) Qual é o número máximo de arestas em um grafo desconexo com n vértices? 
7) Para o grafo a seguir, faça o que se pede: 
C
FE
B
D
A
G
 
a) Indique os graus de todos os vértices: 
d(A) = d(C) = d(E) = d(G) = 
d(B) = d(D) = d(F) = 
b) Indique um caminho hamiltoniano. 
c) Indique um ciclo hamiltoniano. 
d) Qual a distância entre os vértices B e E? d(B,E) = 
e) Indique três caminhos simples de A a F, de comprimentos distintos: 
caminho: comprimento = 
caminho: comprimento = 
caminho: comprimento = 
f) Indique quatro ciclos simples. 
g) Indique um caminho euleriano, ou prove que tal caminho não existe 
h) Indique um ciclo euleriano, ou prove que tal ciclo não existe. 
8) Prove que existe um ciclo hamiltoniano em um grafo conexo e 2-regular. 
9) O Kn possui um caminho euleriano? Para quais valores de n? 
10) O Kn possui um ciclo hamiltoniano? Para quais valores de n? 
11) Use os teoremas apropriados para provar se os grafos a seguir possuem ou não caminhos e 
ciclos eulerianos. Nos casos possíveis, indique os caminhos e ciclos de Euler. 
Tente também encontrar caminhos e ciclos hamiltonianos em cada um destes grafos. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 26 
 
12) Para o grafo G abaixo, faça o que se pede: 
D
BA
C
GF
E
 
 Grafo G 
a) Indique: 
 d(A) = d(B) = d(C) = d(D) = 
 d(E) = d(F) = d(G) = 
b) Indique um CAMINHO EULERIANO em G (que não seja 
ciclo), ou prove porque G não admite tal caminho.
c) Indique um CICLO EULERIANO em G, ou prove porque G não admite tal ciclo. 
d) Indique um CICLO HAMILTONIANO em G, ou prove porque G não admite tal ciclo. 
e) Indique todos os CICLOS SIMPLES de G. 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) 
 
5) Resposta: n-1. 
6) Resposta: o número de arestas do Kn-1. Por que? 
7) 
C
FE
B
D
A
G
 
b) A, B, D, G, C, E, F 
c) O grafo não possui um ciclo hamiltoniano. 
d) d(B,E) = 2 
e) A, C, E, F comprimento 3 
A, C, E, D, F comprimento 4 
A, C, G, D, E, F comprimento 5 
A, B, D, G, C, E, F comprimento 6 
f) E, F, D, E 
C, E, D, G, C 
C, E, F, D, G, C 
A, C, G, D, B, A 
g) C, A, B, D, G, C, E, F, D, E. 
h) Veja comentários sobre o TEOREMA 1.5. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 27 
 
2.2 CAMINHOS E CICLOS EM GRAFOS PONDERADOS E/OU DIRECIONADOS 
Os conceitos relativos a caminhos e ciclos podem ser estendidos a grafos ponderados e 
também a digrafos (ponderados e não ponderados). 
 Caminho e ciclos em digrafos não ponderados 
Os conceitos relativos a caminhos e ciclos são análogos aos grafos não direcionados, apenas 
devendo-se respeitar as direções das arestas. A única exceção é que, em um dígrafo, podemos ter 
um ciclo de comprimento 2. 
No digrafo do EXEMPLO 2 temos: 
Caminho simples: 
d,g,e,f comprimento 3 
 
Ciclos simples: 
f,g,e,f comprimento 3 
e,f,e comprimento 2 
c
b
a
g
f
e
d
 
 Caminho e ciclos em grafos e digrafos ponderados 
Em grafos e digrafos ponderados, os comprimentos dos caminhos e ciclos são calculados 
somando-se os pesos das arestas envolvidas, independendo da quantidade de arestas percorridas 
no caminho. 
No grafo ponderado do EXEMPLO 3, temos: 
Caminhos simples: 
v1,v3,v5 comprimento 18 
v1,v7,v4,v5 comprimento 15 
v3v2
9
v1 v6
4
v7
3
v4
v5
10
6
12
5
8
7
 
 
No digrafo do EXEMPLO 4, temos: 
Caminho simples: 
d,g,e,f comprimento 21 
 
Ciclos simples: 
f,g,e,f comprimento 18 
e,f,e comprimento 11 c
b
a
g
f
e
d
5
11
487 7
8
6
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 28 
 
EXERCÍCIOS 2.2 
1) Para o digrafo ponderado representado abaixo, faça o que se pede: 
a. Preencha TODOS os elementos da sua matriz de adjacências, considerando que o peso de 
cada aresta está associado a CUSTO. 
C
F
8
E
6
9
B
3
D
A
12
7
5
8
5
 





















______
______
______
______
______
______
FEDCBA
F
E
DC
B
A
 
b. Enumere os seguintes caminhos de A a D, indicando também seus comprimentos. 
Caminho simples de comprimento mínimo: Comprimento = 
Caminho simples de comprimento máximo: Comprimento = 
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 29 
 
2.3 SUBGRAFOS, CONECTIVIDADE, EMPARELHAMENTOS 
Os assuntos desta seção serão aplicados a grafos não ponderados, embora também se 
apliquem a grafos ponderados. 
 Subgrafos 
Seja um grafo G = (V, E). Dizemos que G' = (V', E') é um subgrafo de G se V'  V e E'  E. 
Neste caso, dizemos que G é um supergrafo de G'. Observe que o subgrafo G' pode não ter todos 
os vértices e/ou arestas de G, mas não pode ter vértices e/ou arestas que não estejam em G. Um 
possível subgrafo do EXEMPLO 1 é ilustrado a seguir. 
v3
v9
v8
v1
v10v6
v4
v5 
(a)
v3
v2
v9
v8
v1
v10v6
v7
v4
v5 
(b) 
FIGURA 22 – UM SUBGRAFO (a) DO GRAFO DO EXEMPLO 1 (b) 
Se um G' é um subgrafo de G tal que V' = V, dizemos que G' é um subgrafo gerador de G. 
Em outras palavras, um subgrafo gerador tem todos os vértices do supergrafo. Um possível 
subgrafo gerador do EXEMPLO 1 é ilustrado a seguir. 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5 
(a)
v3
v2
v9
v8
v1
v10v6
v7
v4
v5 
(b) 
FIGURA 23 – UM SUBGRAFO GERADOR (a) DO GRAFO DO EXEMPLO 1 (b) 
Se G' é um subgrafo de G tal que todas as arestas de G que unam vértices de G' também 
aparecem em G', dizemos tal que G' é um subgrafo induzido de G. Mais precisamente, G' é um 
subgrafo de G, induzido por V', quando (  v,w  V' ) ( {v,w}  E  {v,w}  E' ). A figura a seguir 
ilustra o subgrafo do EXEMPLO 1 induzido por V' = { v3,v4,v5,v6,v7,v8,v9 }. 
v3
v9
v8
v6
v7
v4
v5 
(a)
v3
v2
v9
v8
v1
v10v6
v7
v4
v5 
(b) 
FIGURA 24 – UM SUBGRAFO (a) DO GRAFO DO EXEMPLO 1 (b), INDUZIDO POR { v3,v4,v5,v6,v7,v8,v9 } 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 30 
 
 Componentes conexos 
Seja G' um subgrafo conexo de G. Dizemos que G' é maximal (quanto à conectividade) 
se G não admite nenhum outro subgrafo G" que contenha G' e também seja conexo. Observe a 
FIGURA 25, representando subgrafo do EXEMPLO 1, ilustrados a seguir. 
v3
v2
v9
v8
v1
v10v6
v7
v4
v5 
v3
v6
v4
v5
v3
v2 v6
v4
v5
v3
v6
v4
v5
G1
G3
G2
G4
v3
v2 v6
v7
v4
v5
 
FIGURA 25 – SUBGRAFOS CONEXOS DE G: G4 É CONEXO E MAXIMAL. 
Na FIGURA 13, vemos quatro subgrafos de G. O subgrafo G1 é conexo, mas não maximal, pois 
podemos adicionar vértices e/ou arestas de G em G1, obtendo outros subgrafos conexos de G. A 
adição de {v3,v5} a G1 resulta no grafo G2, que é conexo. A adição de v2 e {v2,v3} a G1 resulta em G3, 
que é conexo. G2 e G3 são supergrafos conexos de G1, obtidos por adição de vértices e/ou arestas 
de G. Portanto, G1 não é subgrafo maximal quanto à conectividade. Na verdade, G2 e G3 também 
são não maximais: ambos são subgrafos do G4, que é um subgrafo conexo e maximal de G. 
Chamamos componentes conexos de G aos seus subgrafos conexos maximais. Temos então 
outra definição para grafos conexos: grafo é dito conexo quando tem apenas um componente 
conexo. O grafo G da FIGURA 26 é desconexo, pois tem três componentes conexos, ilustrados a 
seguir. 
v3
v2
v9
v8
v1 v10
v6
v7
v4
v5
G4
G5 G6
 
FIGURA 26 – COMPONENTES CONEXOS DE G (FIGURA 13): G4, G5 E G6 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 31 
 
 Exclusão de vértices e arestas 
Em um grafo G(V,E) podemos realizar as operações de remoção de vértices e de arestas. A 
operação de remoção de uma aresta envolve apenas a sua remoção do conjunto E. A remoção de 
um vértice v envolve a sua exclusão de V, e a consequente exclusão, do conjunto E, de todas as 
arestas incidentes a ele. 
Podemos generalizar tais operações para remoção de um subconjunto de vértices ou de 
arestas de um grafo. Formalmente, para subconjuntos V'  V e E'  E: 
G – E' = G' ( V, E – E' ) 
G – V' = G' ( V – V', E – { {v,w} | v V' ou w V' } ) 
 Cortes de vértices, cortes de arestas 
Seja um grafo conexo G(V,E). Um corte de vértices Vc  V é um subconjunto minimal de 
vértices tal que G – Vc é desconexo ou trivial. Como Vc é minimal, para todo subconjunto próprio 
Vc'  Vc, G - Vc' é conexo e não trivial. Analogamente, um corte de arestas VE  E é um 
subconjunto minimal de arestas tal que G - Ec é desconexo. Como Ec é minimal, para qualquer 
subconjunto próprio Ec'  Ec, G - Ec' é conexo. Como exemplo, considere o grafo representado na 
FIGURA 27 a seguir. 
G
H
E
FA
D
B
C
 
FIGURA 27 – CORTES DE VÉRTICES E ARESTAS 
O conjunto de vértices { C,D,F } desconecta o grafo, mas não é minimal (não sendo corte de 
vértices), pois seu subconjunto { C,D } também o desconecta (este último é um corte de vértices). 
Outro corte de vértices é o conjunto { E }, este de cardinalidade mínima 1. 
O conjunto de arestas { AB, CE, DE } desconecta o grafo, mas não é minimal (não sendo corte 
de arestas), pois seu subconjunto { CE, DE } também o desconecta. Os conjuntos { AC, BC, EC } e 
{ CE, DE } são corte de arestas, este último de cardinalidade mínima: não existe outro corte de 
arestas de menor cardinalidade. 
Denomina-se conectividade de vértices cV como o valor da menor cardinalidade de um corte 
de vértices de G; ou seja, o menor número de vértices que o torne desconexo ou trivial. De 
maneira análoga, a conectividade de arestas cE é o valor da menor cardinalidade de um corte de 
arestas de G (o menor número de arestas que o desconecte). Se um grafo G é desconexo, temos 
cV = cV = 0. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 32 
 
Portanto, o grafo da FIGURA 27 acima tem conectividades de vértices e arestas dadas por 
cV = 1 e cE = 2. Como exercício, desenhe os grafos resultantes da remoção de cada um dos cortes 
de vértices e arestas considerados. 
Um grafo é dito k-conexo em vértices quando cV  k; ou seja, não existe corte de vértices 
com menos do que k vértices. De forma análoga, um grafo k-conexo em arestas tem cV  k, não 
existindo corte com menos de k arestas. O grafo da FIGURA 15 é 1-conexo em vértices, 1-conexo 
em arestas e 2-conexo em arestas (também chamado biconexo em arestas). 
Uma importante desigualdade sobre conectividade: para todo grafo, cV  cE (por que?). De 
forma mais completa, sendo w um vértice de grau mínimo de G, temos cV  cE  d(w) (novamente, 
por que?). 
Um vértice v é uma articulação quando G – v é desconexo. Uma aresta e é denominada 
ponte quando G – e é desconexo. O grafo da FIGURA 15 tem o vértice E como articulação, e não tem 
nenhuma ponte (sendo portanto, biconexo em arestas). 
 Emparelhamentos em grafos bipartidos 
Seja G = (V, E) um grafo bipartido. Um emparelhamento em G é um subconjunto de arestas 
de G, E'  E tal que duas arestas distintas de E' não sejam incidentes a nenhum vértice em comum. 
Ou em outras palavras, um emparelhamento “cobre” alguns vértices sem nenhum vértice 
repetido. 
Um emparelhamento é maximal se nenhum outro emparelhamento o contém. Já um 
emparelhamento máximo é um emparelhamento (maximal) com o número máximo de arestas. 
A
F
B
D
E
G
C
(a) 
A
F
B
D
E
G
C
(b) 
A
F
B
D
E
G
C
(c) 
A
F
B
D
E
G
C
(d) 
FIGURA 28 – EMPARELHAMENTOS: (b), (c), (d): os dois últimos são maximais. 
Na FIGURA 28 acima, vemos um grafo (a) e alguns emparelhamentos. O emparelhamento 
{ { C,F } } – item (b) – não é maximal, pois está contido no emparelhamento { { C,F }, { B,E } }, que é 
um emparelhamento maximal, ilustrado no item (c). Já o emparelhamento ilustrado no item (d), 
{ { C,F }, { B,D }, { A,E } }, é um emparelhamento máximo, composto por três arestas. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 33 
 
EXERCÍCIOS 2.3 
1) Prove que o Kn é conexo. 
2) Quais são os valores cV e cE para o grafo Kn? 
3) Você consegue desenhar um grafo conexo 3-regular que tenha uma ponte? 
4) Prove ou dê um contraexemplo. Se a aresta {v,w} é uma ponte então esta aresta é o únicocaminho ente v e w. 
5) Quantas articulações e quantas pontes você consegue encontra no grafo a seguir? 
CG
E
B
FD
A
 
6) Prove ou dê um contraexemplo. Todo grafo conexo que tem uma ponte também tem uma 
articulação. 
7) Prove ou dê um contraexemplo. Se um grafo G é biconexo em arestas (sem pontes) então 
todo par de vértices faz parte de algum ciclo de G. 
8) Quais são os valores cV e cE para cada um dos grafos abaixo? 
 
9) Seja G um grafo formado por um único ciclo simples contendo todos os seus vértices. Para 
que valores de n, G é um grafo bipartido? Nestes casos, qual é o tamanho de um 
emparelhamento máximo de G? 
10) Qual é o tamanho de um emparelhamento máximo do Kp,q ? Demonstre sua solução. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 34 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
2) cV = cE = n – 1 
 
3) 
 
 
5) Duas articulações: vértices C e D. Duas pontes: arestas: CG e DF 
6) Contra–exemplo: 
 
 
9) Para todo valor n par. A cardinalidade do emparelhamento máximo, neste caso, é n/2. 
10) O tamanho do emparelhamento máximo do Kp,q é o valor máximo dentre p e q. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 35 
 
2.4 PLANARIDADE 
Uma representação de um grafo qualquer é dita uma representação plana quando não 
existem arestas que se cruzem (apenas se encontram com outras arestas adjacentes nos vértices 
em comum). Dizemos que G é um grafo planar se G admite uma representação plana. Por 
exemplo, o K4 é um grafo planar (veja figuras (b) e (c) abaixo). 
(a) (c)(b)
1
2
3
4
1
2
3
4
1
2
3 5
4
 
FIGURA 29 – DUAS REPRESENTAÇÕES PLANAS PARA O K4: (b) e (c) 
Observe que qualquer representação geométrica de um grafo divide o plano em regiões, ou 
faces, sendo que existe exatamente UMA região ilimitada, denominada face externa. Veja que na 
FIGURA 29 (a), a face externa é representada pela região 5, enquanto nas FIGURAS 29 (b) e (c) a face 
externa é representada pela região 4. 
Quaisquer representações planas de um mesmo grafo possuem sempre o mesmo número 
de faces. Este número, denotado por f, é um valor constante e único para cada grafo. 
 TEOREMA 1.6: (Fórmula de Euler) 
Seja G um grafo planar e conexo. Então n + f = m + 2. 
A prova deste teorema será omitida, e pode ser feita por indução sobre o número de 
arestas. 
 TEOREMA 1.7: Seja G um grafo planar e conexo, com n 3. Então são válidas as seguintes 
desigualdades: 
(a) m  3n – 6; e 
(b) Se G não contém ciclo de comprimento 3, então m  2n – 4. 
A prova deste teorema será omitida, e tem consequências importantes para determinarmos 
se um grafo é planar, como veremos a seguir. 
 LEMA 1.2: Os grafos K5 e K3,3 (FIGURA 30 abaixo) são não–planares. 
K5 K3,3 
FIGURA 30 – GRAFOS NÃO-PLANARES 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 36 
 
Para o K5 temos n = 5 e m = 10, e consequentemente m  3n – 6; desta forma, K5 não é 
planar, pois não satisfaz ao TEOREMA 1.7 (a). Para o K3,3 temos: n = 6 e m = 9. Embora satisfaça ao 
Teorema 1.7 (a), note que o K3,3, que não tem ciclo de comprimento ímpar, não satisfaz ao 
Teorema 1.7 (b), sendo não planar. Os grafos K5 e K3,3 têm um papel especial para a determinação 
de planaridade em grafos, como veremos a seguir. 
 Subdivisão de um grafo, Homeomorfismo 
Seja um grafo G, e {v,w} uma aresta de G. A subdivisão da aresta {v,w} é a inserção de k 
vértices v1,v2,,vk à aresta {v,w} de forma que esta seja transformada em um caminho simples 
v,v1,v2,,vk,w, de forma que todos os k vértices vi tenham grau 2, sendo adjacentes apenas entre 
si (ou então a v ou a w). Dizemos que um grafo G′ é a subdivisão de um grafo G se G′ poder ser 
obtido de G através de subdivisões de arestas de G. A FIGURA 30, abaixo, ilustra a definição. 
D
E
A
C
B
D
E
A
C
B
G G′ 
FIGURA 31 – G′ É SUBDIVISÃO DE G 
Dois grafos G′ e G′′ são ditos homeomorfos se um deles é a subdivisão do outro, ou se 
ambos são resultados da subdivisão de um terceiro grafo G. Na FIGURA 31, G e G′ são 
homeomorfos, enquanto na Figura 32 (abaixo), G e G′ são homeomorfos, bem como G e G′′. 
Ainda, G′ e G′′ são também homeomorfos, pois ambos são subdivisões de G. 
G G′ G′′ 
FIGURA 32 – G, G’ E G′’: GRAFOS HOMEOMORFOS 
 TEOREMA 1.8: (Teorema de Kuratowski) 
Um grafo é planar se e somente se não contém um subgrafo homeomorfo a K5 
ou homeomorfo a K3,3. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 37 
 
EXERCÍCIOS 2.4 
1) Desenhe uma representação plana para o grafo abaixo, ou prove que este grafo é não-planar. 
BA
C D
E
 
2) Desenhe uma representação plana para o grafo abaixo, ou prove que este grafo é não-planar. 
 
3) Desenhe uma representação plana para o K2,3. 
4) Desenhe uma representação plana para o K2,4. 
5) Mostrar que o Grafo de Petersen, ilustrado abaixo, é não-planar. 
Grafo de Petersen 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) 
BA
C D
E
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 38 
 
2.5 COLORAÇÃO DE VÉRTICES 
Seja G = (V, E) um grafo qualquer, e C = { c1, c2, c3,  cp } um conjunto de p cores distintas. 
Uma coloração de G é conjunto de atribuições destas cores aos vértices de G, de forma que 
vértices adjacentes tenham cores distintas. Formalmente, uma coloração é uma função 
cor: V  C tal que {v,w}  E  cor(v)  cor(w). 
Uma k-coloração de G é uma coloração que utiliza k cores; ou seja, o conjunto imagem da 
função cor tem cardinalidade k. Neste caso, dizemos que G é k-colorível. Observe que todo grafo é 
n-colorível. Basta pegarmos uma cor distinta para cada vértice de G. Mas o objetivo é utilizarmos o 
menor número possível de cores. 
O número cromático de G, notado por (G), é o valor mínimo de k para o qual o grafo G é 
k-colorível. Qualquer coloração com (G) cores é chamada coloração mínima. A figura abaixo 
mostra um grafo G que admite uma 3-coloração. Pode-se verificar facilmente que esta coloração é 
mínima. Desta forma, (G) = 3. 
D
F
B H
EA
G
C
c2
c1
c2 c3
c3c3
c1
c1
 
FIGURA 33 – UMA 3-COLORAÇÃO (MÍNIMA) PARA G 
 LEMA 1.1: Um grafo é bicolorível se e somente se for bipartido. 
A prova do LEMA 1.1 é bastante simples. Seja G um grafo bipartido, sendo V = V1  V2 tal que 
vértices de uma mesma partição não são adjacentes. Podemos então escolher duas cores, uma 
para colorir os vértices de V1, e outra para colorir os vértices de V2. Reciprocamente, se um grafo é 
bicolorível, então podemos particionar V em subconjuntos de vértices de mesma cor. Como 
vértices de mesma cor não são adjacentes, temos que G é um grafo bipartido. 
 Problema das quatro cores 
O Teorema das Quatro Cores diz que é possível colorir as regiões de qualquer mapa 
desenhado no plano (que pode ser modelado como um grafo planar) usando no máximo quatro 
cores, de forma que regiões adjacentes sejam de cores distintas. A FIGURA 20 abaixo ilustra um 
mapa com 5 regiões, e seu respectivo grafo, que é 4-colorível, como mostrado. O problema das 
quatro cores relaciona os estudos de COLORAÇÃO e PLANARIDADE em grafos. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 39 
 
A
D
C
B
F
E
F
C
B
A
D
E
c1
c2
c3
c2
c3c4 
FIGURA 34 – UMA 4-COLORAÇÃO DE UM MAPA 
EXERCÍCIOS 2.5 
1) Determine (G) para o grafo G abaixo. Prove que o valor (G) está correto: 
(a) Mostre uma (G)-coloração para o grafo; e 
(b) Prove que esta coloração é mínima. 
D
EA
B
GF
C
 
2) Construa o menor grafo sem triângulos cujo número cromático seja 3. 
Um grafo sem triângulos não tem o K3 como subgrafo. 
3) Qual é o valor de (Kn)? 
4) Seja G um grafo composto apenas por um ciclo simples contendo todos os seus vértices. Qual 
é o número cromático de G? 
5) Determine (G) para todos os grafos abaixo. Mostre a (G)-coloração de cada um deles. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 40 
 
6) Determine o número cromático do grafo abaixo. Apresente uma coloração para este valor. 
 
RESPOSTASE COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) (G) = 3 
a) 
c1
c2c1
c2
c1c2
c3
 
b) 
G contém um ciclo de comprimento ímpar (A,B,C,D,E,A). 
Portanto, pelo TEOREMA 1.3, G não é bipartido. 
 
Logo, pelo LEMA 1.1, G não é 2-colorível, e a 3-coloração 
apresentada é uma coloração mínima para G.