Aula - Ciclo Euleriano

Aula por Arthur Lobo

Nessa aula nós vamos falar sobre algoritmos para achar um ciclo euleriano e alguns problemas que os utilizam.

Um Caminho Euleriano é definido como um caminho no grafo que começa num vértice $V_I$, passa por todas as arestas exatamente uma vez, e termina num vértice $V_F \ne V_I$. Ou seja, um Caminho Euleriano num grafo $G$ com $M$ arestas é uma sequência de arestas $E_{i_1},E_{i_2},...,E_{i_M}$, tal que todas são diferentes dois a dois, elas formam um caminho contínuo (saindo de uma aresta é possível ir para a próxima) e o início é diferente do fim.

Um Ciclo Euleriano é um "caso especial" do Caminho Euleriano: um caminho no grafo que começa num vértice qualquer $V_I$, passa por todas as arestas exatamente uma vez, e termina num vértice $V_F = V_I$. Ou seja, a única diferença é que ele começa e termina no mesmo vértice, por isso o nome Ciclo.

Agora vamos ver como saber se existe e encontrar um Ciclo Euleriano, que é mais simples do que o Caminho Euleriano, vamos dividir entre 2 casos: quando o Grafo é Direcionado e quando é Não-direcionado.

Ciclo Euleriano em Grafo Direcionado

Imagine o seguinte problema: Dado um grafo direcionado $G$ com $N$ vértices e $M$ arestas, diga se existe um Ciclo Euleriano em $G$ e, caso exista, imprima a ordem dos vértices que você passa em algum Ciclo Euleriano.

A primeira vista, saber se existe um Ciclo Euleriano parece ser difícil, mas na verdade não é. Um Ciclo Euleriano existe em um grafo direcionado, se e somente se essas 2 condições forem verdadeiras:

• Todos os vértices tem seu grau de entrada igual ao seu grau de saída, ou seja, todos os vértices tem mesma quantidade de arestas entrando e saindo.
• Ignorando os vértices isolados (com grau de entrada e saída sendo 0), o grafo é fracamente conexo, ou seja, se nós "transformarmos" todas as aresta direcionadas em não-direcionadas, o grafo vira conexo.

É fácil ver que essas duas condições são necessárias, pois a quantidade de vezes que se entra num vértice é igual à quantidade de vezes que sai dele, e se o grafo for quebrado, não é possível passar por  todas as arestas. Mas além de serem necessárias, essa condições também são suficientes! O que quer dizer que basta checar elas para ver se existe um Ciclo Euleriano.

A ideia é que se todos os vértices tem grau de entrada igual ao grau de saída, então é possível dividir as arestas em vários ciclos simples disjuntos; começando com o caminho sendo apenas um ciclo simples, é fácil ver que podemos ir incrementando o Ciclo Euleriano adicionando os outros ciclos que passam por algum vértice que já está no Ciclo Euleriano atual.

A prova dessa primeira afirmação (que é possível dividir em ciclos simples disjuntos) foi feita por Carl Hierholzer, em 1873, no livro Graph Theory, 1736–1936, mas não vamos discuti-la mais a fundo aqui.

Então para checar se um grafo possui um Ciclo Euleriano, é só fazer um for verificando se todos os vértices seguem a primeira restrição, e fazer uma dfs para ver se ele é conexo. Mas sabendo que o grafo o possui, como encontrar um Ciclo Euleriano?

A nossa estratégia vai ser dividir o grafo em vários ciclos simples (que não repetem aresta) de um modo que cada aresta esteja em exatamente um deles, e depois juntar eles formando o Ciclo Euleriano. Veja alguns exemplos nesses grafos:

EXEMPLOS

Esse processo de separar em ciclos e juntá-los pode ser feito com uma função recursiva chamada 'AcharCicloEuler(int $u$)'. Quando ela estiver em $u$, ela vai fazer o seguinte:

• Enquanto ainda existir alguma aresta saindo de $u$ inutilizada
  • Pega alguma aresta que não foi usada ainda e saí de $u$ para algum vértice $v$.
  • Apaga ela do grafo (marca como utilizada).
  • Tenta construir algum ciclo simples saindo do vértice $v$ chamando 'AcharCicloEuler($v$)'.
• Adiciona $u$ na resposta (no caminho).

Já que adicionamos $u$ apenas depois de ver todas as arestas, colocamos os vértices de cada ciclo simples na resposta na ordem inversa, então depois precisamos inverter o vetor que guarda o caminho.

No final, essa ideia se traduz no seguinte código:

Vale ressaltar que não podemos trocar o 'while' por um 'if', porque ele pode encontrar um ciclo que contém o vértice inicial e acabar o código sem verificar adicionar os outros ciclos. Além disso, não podemos adicionar o vértice na resposta no início da função, senão a ordem não ficará correta nem se não invertermos.

Para tentar entender o código um pouco melhor, vale a pena testar manualmente o que ele faz em alguns grafos. Tente fazer isso com os exemplos que demos a cima e também com exemplos que você mesmo pode criar!

Ciclo Euleriano em Grafo Não-Direcionado

Em um grafo não-direcionado, não podemos simplesmente criar as arestas para as duas direções e rodar o código assim, a ideia do Ciclo Euleriano é que passemos exatamente uma vez por cada aresta, independente da direção. Se existe uma aresta $u - v$, então vamos passar ou de $u$ para $v$, ou de $v$ para $u$.

A condição de existência do Ciclo Euleriano em grafos não-direcionados é muito semelhante à de grafos direcionados, essas 2 condições precisão ser verdadeiras:

• Todos os vértices tem grau par, ou seja, todos os vértices são pontas de uma quantidade par de arestas.
• Ignorando os vértices isolados (com grau sendo 0), o grafo é conexo.

Assim como no grafo direcionado, é fácil ver que essas condições são necessárias, pois a quantidade de vezes que você entra num vértice $u$ é igual a quantidade de vezes que você sai, e ambos são iguais à metade do número de arestas conectadas ao vértice $u$ (portanto, tem que ser par), e o grafo deve ser conexo.

A prova que também são suficientes é semelhante a do grafo direcionado. Todos os vértices tem grau par $\Rightarrow$ É possível dividir em vários ciclos simples disjuntos $\Rightarrow$ É possível montar um Ciclo Euleriano.

Para encontrar o Ciclo Euleriano em grafos não-direcionados, vamos fazer um algoritmo análogo à de grafos direcionados. A única diferença é que vamos ter que chegar se a aresta já foi usada ou não na direção inversa; para isso, vamos guardar as duas pontas de cada aresta em um array de pair 'edges', a lista de adjacência de cada vértice vai ser um vector 'edges_id', e vamos guardar em um array 'vis' se cada aresta já foi ou não visitada.

O código para Encontrar Ciclo Euleriano em grafos não-direcionados fica assim:

 

O problema do Dominó

Imagine o seguinte problema:

Você tem $M$ peças de Dominó, cada uma delas tem um número, que vai de $1$ até $N$, escrito em cada um de suas pontas. Assim como num jogo de dominó normal, você pode conectar duas peças juntando duas pontas com o mesmo número escrito. Você pode rotacionar os dominós.

É possível colocar colocar esses dominós enfileirados de modo a usar todos eles exatamente uma vez e o número mais a esquerda é igual ao mais a direita?

Exemplo: