Eulerizar um grafo
Dois exemplos, uma nota e uma tarefa.

 
Quando eulerizamos um grafo, começamos por localizar os vértices de valência ímpar. O grafo (a) da figura seguinte tem dois, B e C. Seguidamente, acrescentamos uma aresta terminando em cada um desses vértices. A figura (b) representa uma maneira de eulerizar o grafo. B e C têm agora valência par, como é necessário que aconteça a todos os vértices após a eulerização. Para ver um circuito de Euler no grafo eulerizado na figura, basta seguir em (c) as arestas pela ordem numérica atribuída e seguindo as setas, partindo e terminando no vertex A.
O último passo, representado na figura (d), consiste em sobrepor o nosso circuito de Euler sobre o grafo original. Há duas arestas que são percorridas duas vezes. A cada uma das repetições corresponde uma aresta acrescentada.
neste tipo de problemas, podemos considerar como genericamente verdadeira a seguinte afirmação: se acrescentarmos novas arestas correctamente, o número de repetições de arestas é igual ao número de arestas acrescentadas durante a eulerização.
Quando acrescentarmos novas arestas para eulerizar um grafo, é desejável acrescentar só arestas que dupliquem arestas existentes. Se procedermos deste modo, a regra enunciada em itálico, é sempre verdadeira.
 
Na figura seguinte, precisamos de transformar X e Y em vértices de valência par.. Acrescentando uma aresta de X a Y, (b) pode parecer uma ideia atraente, mas fazer isso pode ser equivalente a duplicar mais do que uma aresta. (Lembremos que duplicar uma aresta significa acrescentar uma aresta que liga dois vértices que já estejam ligados por uma aresta a ser duplicada). Para ver bem a razão desta nota, acrescente essa longa aresta e tente sobrepor o circuito de Euler do novo grafo no grafo original. Esta longa aresta não conta como uma simples aresta repetida, dado que a alternativa de usar uma longa aresta não corresponde a uma só aresta repetida , mas a toda uma série de arestas ligando X a Y (como mostra a linha mais gorda da figura (c)).
Se não acrescentarmos a longa aresta (arco), mas em vez disso seguirmos a regra que cada aresta acrescentada deve duplicar uma aresta existente, seremos capazes de contar (na figura (d)) as arestas que tiverem de ser repetidas contando o número de arestas duplicadas que precisam de ser acrescentadas (três neste caso).
 
Agora que já aprendemos a eulerizar, o próximo passo será tentar sempre obter as melhores eulerizações que pudermos, ou seja eulerizações com o menor número de arestas acrescentadas. É claro que há muitas maneiras de eulerizar um grafo e é sempre possível que o menor número de arestas acrescentadas pode ser obtido por diferentes eulerizações. Por esta razão usamos frases como "uma melhor eulerização" muito mais frequentemente que frases do tipo "a melhor eulerização". Lembremo-nos que procuramos uma melhor eulerização: procurar encontrar um novo circuito sobre o circuito original com o menor número de passos perdidos (arestas repetidas).


voltar ao sumário