Métodos para descobrir circuitos de Euler

1. (10)
Para quem estiver interessado em instruções para não ter que procurar circuitos de Euler por tentativa e erro, aqui fica um esboço de método que resulta: nunca usar uma aresta que seja a única ligação entre duas partes do grafo que ainda seja necessário percorrer.
 
A figura seguinte ilustra isto muito bem.
 
Começamos o circuito em A e chegamos a D, passando por B e C, e nós queremos saber o que é que devemos fazer a seguir. Ir por E seria má ideia porque a parte não percorrida do grafo ficaria então dividida em duas regiões, uma para a esquerda e outra para a direita, desligadas uma da outra. Nunca mais poderíamos vir da parte da esquerda para a direita, pois já tínhamos usado todas as ligações possíveis entre as duas.
Por isso, é melhor continuar e percorrer todas a parte direita e acabá-la antes de usar a aresta de D para E. Este tipo de raciocínio pode ser aplicado todas as vezes que for preciso escolher uma nova aresta. Vejamos como é que isto funciona , partindo do ponto A. A partir do vertex A há duas arestas possíveis e nenhuma delas divide o grafo em duas porções não percorridas que fiquem desligadas. Nestas condições, tanto podemos ir para a esquerda como para baixo.. Tendo ido para baixo até B, temos agora três escolhas e nenhuma delas divide o grafo em duas partes por percorrer e que fiquem desligadas uma da outra. Depois de escolhermos ir de B para C, rapidamente verificamos que é aceitável escolher qualquer das três arestas a partir de C. Podemos completar por este processo o circuito de Euler? A figura (c) mostra uma das muitas maneiras de o conseguir.
O método que acabámos de descrever deixa ainda muitas opções para a escolha das arestas a seguir. Quando há várias arestas aceitáveis como próximo passo, podemos escolher uma delas ao acaso. Podemos até escolher pelo processo de moeda ao ar. Quando os computadores trabalham algoritmos deste tipo, usam geradores de números aleatórios. Se não gostar de muito acaso, comece a numerar todas as arestas do grafo, e, sempre que faça uma escolha, tome a correspondente ao número mais baixo.

2.
Algoritmo (3) de determinação de um circuito de Euler sobre um grafo G=(V,A) a partir de um vértice A, qualquer.
Se em A não incidem arestas, então Euler(A) = [A];
Se em A incidem arestas, então
a partir de A crie um caminho em G, de tal forma que não se passe por uma aresta mais do que uma vez até que volte a A;
Seja este caminho, eliminar as arestas de G;
Devolver o caminho
[circuito de Euler[A], Euler[A1], Euler[A2], .... Euler[An],A].
Fim.


voltar ao sumário