grafos

GRAFOS – FÓRMULA DE EULER

O matemático suiço do século XVIII, Leonhard Euler percebeu que um grafo simples, planar (desenhado na sua forma planar) e conexo divide o plano em um certo número de regiões, incluindo regiões totalmente fechadas e a região infinita exterior. Euler estabeleceu uma relação entre o número de arestas, o número de vértices e o número de regiões para tais gráficos que é dada pela fórmula:

n – a + r = 2

onde n é o número de vértices, a é o número de arestas e r é o número de regiões.

Verificação da fórmula de Euler

Considere os tres grafos que se seguem:

1 2 3

Vamos demonstrar a fórmula de Euler por indução.

No grafo 1 o número de arestas é a = 0, consistindo o grafo de um único vértice. Portanto:

n = 1 a = 0 r = 1

De modo que a fórmula n - a + r = 2 se verifica.

Assumimos agora que a fórmula se verifica para qualquer grafo conexo, planar e simples, com k arestas, e consideremos o grafo com k+1 arestas. Para dedução indutiva devemos relacionar o caso de “k+1” com o caso de “k” arestas. Vamos considerar então dois casos de “k+1” arestas.

Caso 1: O grafo tem um vértice de grau 1 como na figura 2. Eliminamos então a aresta e vértice, que conecta o vertice de grau 1. Isto nos deixa com um grafo de k arestas, algum número n vértices e algum número de regiões, r para os quais n - a + r = 2

No grafo original, antes de retirar a aresta e o nó deve também valer a fórmula, ou seja

(n + 1) – (a+1) + r = 2

que pela hipótese de indução é verdadeira.

Caso 2: O grafo não vértices de grau 1, como é o caso da figura 3 acima. Retiramos então uma aresta que define uma região fechada. O resultado é um grafo planar simples com k arestas, algum número n de vértices, da forma:

n – k + r =3 – 2 + 1 =2

verificando-se a