Grafos de Euler: Identificação e aplicação

Circuito e caminho de Euler

Um circuito de Euler é um circuito que passa em todas as arestas do grafo uma única vez. Um grafo é euleriano se admitir um circuito de Euler.

Já um caminho de Euler é um caminho que passa uma única vez em cada aresta.

Um grafo admite um caminho euleriano se e só se é conexo e no máximo dois dos seus vértices têm grau ímpar, iniciando-se o caminho num deles e terminando no outro.

Exemplo

Será que o grafo abaixo é euleriano?

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Euler: Identificação e aplicação

Ora, o grafo admite o circuito euleriano $\text{BDECADCBAEB}$ . Se o grafo admite um circuito euleriano, então o grafo em si é euleriano.

Teorema de Euler

O teorema de Euler afirma que um grafo é euleriano se e só se é conexo e todos os seus vértices são de grau par.

Exemplo

Podes confirmar mais facilmente que o grafo anterior é euleriano porque é conexo e todos os seus vértices têm grau quatro.

Eulerizar um grafo

Eulerizar um grafo é transformar um grafo que não é de Euler num que o é, duplicando arestas.

Chama-se melhor eulerização ao processo que acrescenta o mínimo de arestas possível.

Procedimento

1.	Acrescenta arestas aos vértices de grau ímpar por duplicação das já existentes até obteres um grafo conexo e só com vértices de grau par.
2.	Indica o circuito de Euler, verificando se resolveste bem o problema.

Exemplo

Considera o grafo abaixo.

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Euler: Identificação e aplicação

Este grafo não é euleriano, uma vez que o grau dos vértices $\text{E}$ e $\text{F}$ é $3$ (apesar do grau dos restantes vértices ser $2$ ). Como são apenas dois dos vértices com grau ímpar, o grafo admite um caminho de Euler.

Para eulerizar este grafo, adiciona-se uma aresta que ligue os vértices $\text{E}$ e $\text{F}$ de modo a tornar o seu grau par, que será $a_{10}$ , obtendo-se:

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Euler: Identificação e aplicação

Confirma-se que um possível circuito de Euler é

$\text{A}\ a_1\ \text{B}\ a_3\ \text{D}\ a_6\ \text{F}\ a_5\ \text{E}\ a_7\ \text{G}\ a_9\ \text{H}\ a_8\ \text{F}\ a_{10}\ \text{E}\ a_4\ \text{C}\ a_2\ \text{A}$

Grafos-grelha retangulares e não-retangulares

É possível ainda eulerizar grafos-grelha retangulares, obtendo-se

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Euler: Identificação e aplicação

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Euler: Identificação e aplicação

Em grafos de grelhas não-retangulares, necessitas de um pouco de mais atenção pois, usualmente, existem mais vértices de grau ímpar a ter em conta:

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Euler: Identificação e aplicação

Matemática Aplicada às Ciências Sociais; Modelos de grafos; 11º Ano; Grafos de Euler: Identificação e aplicação

Caso não se queira formar um circuito de Euler, é possível deixar dois vértices finais com grau ímpar, chamando-se a este caso uma semieulerização do grafo.