Circuitos de Euler


Para resolver problemas como o que foi apresentado anteriormente, consideram-se soluções óptimas, quando existirem, os circuitos de Euler.
 
 
Dizemos que um grafo admite um circuito de Euler, quando admite um caminho a começar e acabar no mesmo vértice, que percorra todas as arestas e não mais do que uma vez qualquer delas.
 
 
Já tinha sido discutido o problema de Königsberg. O grafo escolhido para esse problema não admite um circuito de Euler.
Neste texto quando dissermos vértice ímpar, estamos a dizer vértice de grau ou valência ímpar. O memso para vértice par. Com o mesmo sentido poderemos falar de nós pares..... Por vezes, Euler utilizou a palavra rede e a palavra figura com o actual significado de grafo.
 
 
Por exemplo: o grafo
admite um circuito de Euler. A partir de A, podemos percorrer todas as arestas e voltar a A, sem qualquer repetição de arestas. A-B-D-E-D-C-B-D-A é um circuito de Euler
como se pode ver na figura acima.
Esta solução óptima não é única.

Tarefas 2.1.1.
(a) O grafo acima admite vários circuitos de Euler. Por tentativa e erro, apresente outro circuito de Euler que aquele grafo admita.
(b) O grafo
não admite um circuito de Euler. Tente uma prova em linguagem corrente.

voltar ao sumário