Grafos Planares

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: n  r  a  2 (chamada de fórmula Euler ( pronuncia-se “óiler”))
Se n  3, então 3n  6  a
Se n  3 e se não existem ciclos de comprimento 3, então 2 n  4  a
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 K 5, 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

1
1
A
0

1
Teoria dos Grafos – Módulo 3 – pág. 1

1 0 1
0 1 0
1 0 2

0 2 0

Grafo direcionado

Matriz adjacência

1
0
A
0

0

1 0 0
0 1 1
1 0 0

0 1 0

Matriz de adjacência simplificada

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