teoria dos grafos

Prévia do material em texto

Teoria dos Grafos – Módulo 3 – pág. 1 
Teoria dos Grafos 
Módulo 3 
Grafos planares. 
Matriz de adjacências de um grafo. 
 
1. Grafos Planares 
 
Grafo planar aquele que pode ser representado em um plano sem qualquer interseção 
entre arestas e permite a representação no plano sem que as linhas se cruzem. 
O grafo A da figura é planar, pois pode ser representado por seu isomorfo B 
 
Propriedade matemáticas dos grafos planares. 
 Todo grafo completo com um número de vértices maior que 5 (n > 5) não é planar. 
 
 Indicado por n (número de vértices ou nós), a (número de arestas) e r (número de 
regiões do plano que o grafo divide o plano) temos a seguintes relações: 
 2 arn (chamada de fórmula Euler ( pronuncia-se “óiler”)) 
 Se n  3, então an  63 
 Se n  3 e se não existem ciclos de comprimento 3, então an  42 
 
Teorema de Kuratowski 
Todo grafo que apresenta como subgrafo o grafo completo K5 ou grafo bipartido K3,3 não 
é um grafo planar. 
O grafo da figura abaixo apresenta como subgrafo o grafo K5, portanto podemos afirmar 
com certeza que ele não é planar. Observe os 5 pontos centrais do grafo é um K5. 
 
 
 
2. Matriz de adjacência de um grafo 
 
Matriz de adjacência de um grafo é uma matriz que indica o número de arestas (ou 
arcos) entre 2 vértices. 
Cada elemento aij = p se existem p arcos entre os vértices i e j. Quando o grafo não é 
direcionado a matriz é simétrica sendo possível uma matriz adjacência simplificada como 
mostrado para os grafos abaixo. 
Grafo não direcionado Matriz de adjacência Matriz de adjacência simplificada 
 
 













0201
2010
0101
1011
A 
 
 
Teoria dos Grafos – Módulo 3 – pág. 2 
Grafo direcionado Matriz adjacência Matriz de adjacência simplificada 
 
 













0100
0010
1100
0011
A 
 
 
 
Não é possível por a matriz não 
simétrica. 
 
 
 
Exemplo 1 - módulo 3 – teoria dos grafos. 
Como foi exposto acima os grafo A é planar, pois conseguimos fazer a sua representação 
isomorfa que o grafo B. Verifique as propriedades matemáticas nestes grafos. 
 
Solução: Fazendo a contagem temos: n = 8 vértices; r = 6 regiões (no grafo A como sua 
representação é espacial as regiões são suas faces já na grafo B devemos contar as 5 
regiões internas mais 1 região externas já que sua representação é planar) e a = 12 
arestas. Aplicando as propriedades temos: 
2 arn  21268  é verdade. 
Se n  3, então an  63  8  3, então 2.8 – 6  8 é verdade 
Se n  3 e ∄ comprimento 3, então an  42  2.8 – 4  8 é verdade 
Logo as propriedades foram verificadas. 
 
Exemplo 2 - módulo 3 – teoria dos grafos. 
Decida se os grafos são isomorfos. Em caso afirmativo as funções que estabeleçam o 
isomorfismo. Caso não sejam isomorfos explique. 
 
Solução: As funções de isomorfismo são as equivalentes entre vértices e aresta de cada 
grafo. Se todas a equivalência são verdadeiras os 2 grafos ao isomorfos. 
Sendo f1 a função equivalência de vértices, temos: 
f1: 1  a (o vértice 1 do grafo (a) equivale a vértice a no grafo (b)). 
 2  b 3  c 4  d 
 
Sendo f2 a função equivalência de arestas, temos: 
F2: a1  e2 (a aresta a1 do grafo (a) equivale a aresta e2 a no grafo (b)). 
 a2  e7 a3  e6 a4  e1 
a5  e3 a6  e4 a7  e5 
Teoria dos Grafos – Módulo 3 – pág. 3 
 
Como foi verificado todas as equivalências podemos afirmar que os 2 grafos são 
isomorfos. 
 
Exemplo 3 - módulo 3 – teoria dos grafos. 
Verifique se o grafo da figura é planar. Se não for justifique. Se for prove desenhando seu 
isomorfo sem o cruzamento de aresta. 
 
Solução: O grafo é planar porque possui o seguinte isomorfo planar: 
 
 
Exemplo 4 - módulo 3 – teoria dos grafos. 
Um grafo possui 7 aresta e 7 regiões. Determine o seu número de aresta para que o 
mesmo seja planar. Desenhe o grafo 
Solução: Usando a fórmula de Euler, temos: 
2 arn 
277 n  2n vértices. 
 
 
 
Exemplo 5 - módulo 3 – teoria dos grafos. 
Escreva a matriz de adjacências do grafo representada na figura abaixo: 
 
 
 
Solução: como grafo possui 2 vértices, sua matriz de adjacências será de ordem 2 com 
os seguintes elementos: 
a11 = 0 (não existe laços no vértice 1 ou seja aresta partindo de 1 chegando em 1), 
a12 = 5 (existem 5 arestas partindo do vértice 1 e chegando no vértice 2), 
a21 = 5 (existem 5 arestas partindo no vértice 2 e chegando no vértice 1), 
a22 = 0 (não existe laços no vértice 2 ou seja aresta partindo de 2 chegando em 2) 
portanto a matriz de adjacências é: 







05
50
A 
 
Teoria dos Grafos – Módulo 3 – pág. 4 
Exercícios propostos 
1) Desenhe um grafo simples complementos com 4 vértices (K4). O K4 é planar? Justifique. 
A sua justificativa pode graficamente ou em texto. 
 
2) Escreva a matriz de adjacência de um grafo simples e completo de 5 vértices(K5) 
 
3) O grafo abaixo é planar? Justifique. A sua justificativa pode graficamente ou em texto. 
 
 
4) Escreva a matriz de adjacência do grafo abaixo que chamado grafo bipartido K3,3. 
 
 
5) Usando o teorema de Kuratowski verifique e justifique se o grafo da figura é planar.