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?
Ora, o grafo admite o circuito euleriano BDECADCBAEB. Se o grafo admite um circuito euleriano, então o grafo em si é euleriano.
Teorema de Euler
O teorema de Eulerafirma 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.
Este grafo não é euleriano, uma vez que o grau dos vértices E e 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 E e F de modo a tornar o seu grau par, que será a10, obtendo-se:
Confirma-se que um possível circuito de Euler é
Aa1Ba3Da6Fa5Ea7Ga9Ha8Fa10Ea4Ca2A
Grafos-grelha retangulares e não-retangulares
É possível ainda eulerizar grafos-grelha retangulares, obtendo-se
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:
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.