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:
[spoiler title=’Solução’ style=’yellow’ collapse_link=’true’]Podemos reduzir isso para um Ciclo Euleriano: Os números escritos no dominó (de $$1$$ até $$N$$) vão ser os vértices e os dominós vão ser as arestas.
Se um dominó tem $$A$$ em uma ponta e $$B$$ na outra, vamos criar uma aresta não-direcionada entre $$A$$ e $$B$$.
Queremos que o primeiro número seja igual ao último, portanto temos que ter um ciclo; também queremos usar todos os dominós, portanto vamos usar todas as arestas.
Portanto, reduzimos o problema para encontrar um Ciclo Euleriano em um grafo não-direcionado.[/spoiler]