Explique como o algoritmo de Hierholzer para encontrar um ciclo euleriano funciona.
Passo 1
O que a pergunta pede: você quer entender como o algoritmo de Hierholzer funciona para encontrar um ciclo euleriano em um grafo. Vou assumir que queremos a versão geral (explicação, condições necessárias, algoritmo passo a passo, exemplo e dicas de implementação).
Informações relevantes (que o algoritmo precisa que sejam verdadeiras para funcionar):
Informações relevantes (que o algoritmo precisa que sejam verdadeiras para funcionar):
- O grafo pode ser não direcionado ou direcionado; as condições para existência de ciclo euleriano são diferentes em cada caso (vou listar explicitamente abaixo).
- Precisamos trabalhar sobre arestas (cada aresta deve ser usada exatamente uma vez).
- O enunciado não deu um grafo específico, então vou mostrar um exemplo concreto para deixar tudo visualizável.
Passo 2
Definições básicas (sem pular etapas).
- Um caminho é uma sequência de vértices em que cada par consecutivo é ligado por uma aresta, e uma aresta não precisa ser distinta necessariamente (mas aqui queremos caminhar sem reutilizar arestas).
- Um trail é um caminho que não repete arestas.
- Um circuito é um trail que começa e termina no mesmo vértice.
- Um ciclo euleriano (ou circuito euleriano) é um circuito que usa todas as arestas do grafo exatamente uma vez.
- Em termos simples: queremos uma lista de vértices
com tal que cada aresta do grafo apareça exatamente em uma transição .
Passo 3
Condições de existência (o que precisa ser verdade para o algoritmo funcionar):
- Para grafos não direcionados: o grafo deve ser conexo quando ignoramos vértices isolados (i.e., a componente que contém arestas deve ser única) e todo vértice deve ter grau par. Em notação: para cada vértice
temos que é par. Essas condições são necessárias e suficientes para existir um ciclo euleriano. - Para grafos direcionados: cada vértice precisa satisfazer
e o grafo deve ser fortemente conexo se considerarmos apenas vértices com arestas (ou, mais fraco mas prático, que o subgrafo orientado que contém as arestas seja fortemente conectado quando consideramos arcos com equilíbrio). Essas condições garantem existência de circuito euleriano dirigido.
Observação rápida do porquê (intuição): se um vértice tem grau ímpar, ao entrar/saír através de arestas não dá para emparelhar entradas/saídas e sobrarão arestas sem pareamento quando caminhamos; por isso é impossível fechar um circuito que use todas as arestas.
Passo 4
Intuição do algoritmo de Hierholzer (visão geral antes de entrar no passo a passo técnico).
- A ideia é simples e elegante: comece em algum vértice e siga arestas não utilizadas até voltar ao vértice inicial — porque os graus são pares, você não ficará “preso” antes de fechar um ciclo. Isso produz um ciclo (talvez não use todas as arestas).
- Se ainda existem arestas não usadas, escolha um vértice do ciclo atual que tenha arestas não utilizadas e construa outro ciclo a partir dele; então “esplice” (insira) esse novo ciclo dentro do ciclo anterior. Repita até que não reste nenhuma aresta. O resultado final é um único ciclo que passa por todas as arestas — ou seja, um ciclo euleriano.
Passo 5
Algoritmo passo a passo (versão conceitual para grafo não direcionado):
- Verifique as condições: o grafo deve ser conexo (ignorando vértices isolados) e todo vértice deve ter grau par. Se não, não existe ciclo euleriano.
- Escolha um vértice inicial
que tenha arestas (qualquer vértice com ). - Construa um ciclo inicial: comece em
e percorra arestas não usadas sempre escolhendo qualquer aresta disponível até voltar a . Cada aresta percorrida é marcada como usada; chame o ciclo obtido de . Pelo fato dos graus serem pares você sempre consegue voltar a sem ficar preso (expliquei isso depois). - Enquanto existirem arestas não usadas no grafo: escolha um vértice
que pertença ao ciclo e que tenha arestas não usadas incidentes. A partir de construa outro ciclo usando apenas arestas não usadas (novamente você retorna a ). Insira em substituindo a ocorrência de por seguido de exceto o último repetido — isso é o “splicing”. Atualize ciclo resultante. - Quando não houver mais arestas não usadas,
é um ciclo que usa todas as arestas, ou seja, o ciclo euleriano.
Explicação da etapa de não ficar preso ao construir um ciclo: ao chegar a um vértice durante o passeio, o número de arestas não usadas que saem desse vértice é sempre par (inicialmente
é par; cada vez que você passa por ele usando uma aresta você consome duas “meias arestas” no sentido de entrada+saída), portanto sempre há uma aresta nova para continuar, até que você volte ao início do passeio. Isso evita ficarmos num vértice sem arestas livres antes de fechar o ciclo.
Passo 6
Implementação prática (método com pilha que é o mais usado em código, iterações em
):
Usamos uma pilha , um vetor/lista
para armazenar o circuito final, e listas de adjacência
que permitem consumir arestas. Pseudocódigo explicativo (variáveis em TeX):
Usamos uma pilha
- Inicialize
, . - Enquanto
não estiver vazia: - Seja
. - Se
contém alguma aresta não usada para um vizinho : marque a aresta como usada (em grafos não direcionados, remova a entrada em também), empilhe em . - Caso contrário (não há arestas livres saindo de
): faça e append em .
- Seja
- Ao final,
contém os vértices do ciclo euleriano em ordem reversa (ou na ordem correta dependendo de como você adiciona), usando cada aresta exatamente uma vez.
Por que isso corresponde à ideia de splicing? Porque sempre que você esgota as arestas a partir de um vértice, você o coloca no caminho final; novos ciclos são naturalmente inseridos por meio da ordem de empilhamento e desempilhamento, sem precisar fazer manipulação explícita de “inserir” listas.
Passo 7
Exemplo concreto e mastigado (faça comigo):
Considere o grafo com vértices e arestas formando dois triângulos que se encontram em
:
e
. Todos os graus:
— todos pares.
Aplicando Hierholzer (escolhendo arestas na ordem natural):
Considere o grafo com vértices
Aplicando Hierholzer (escolhendo arestas na ordem natural):
- Começo em
. Caminho inicial: . Ciclo . Marquei as arestas desses três passos. - Ainda há arestas não usadas (as do outro triângulo). No ciclo
o vértice tem arestas livres. Começo outro ciclo em : . Esse é . - Esplico
dentro de no lugar do primeiro , resultando no ciclo final , que usa todas as arestas exatamente uma vez. Esse é o ciclo euleriano.
Se você seguir a versão com pilha, o empilhar e desempilhar produz exatamente essa ordem sem que você precise manualmente “colar” as listas.
Passo 8
Prova de correção (argumento sucinto que você pode usar numa prova):
- Terminação: cada aresta é marcada usada exatamente uma vez; há
arestas, logo após consumos o processo não encontra mais arestas. - Cada aresta é usada: enquanto houver arestas não usadas, o algoritmo faz um passeio adicional a partir de algum vértice do ciclo atual que tem arestas livres — esse passeio usa pelo menos uma aresta nova. Como não criamos arestas novas e não perdemos arestas, no fim iremos consumir todas.
- Não ficamos presos antes de fechar um ciclo: devido aos graus pares (ou in=out em grafos dirigidos), sempre que entramos em um vértice via uma aresta não usada existe uma saída não usada (exceto no caso que estamos retornando ao ponto de partida do passeio), garantindo que o passeio fecha.
Portanto, o ciclo final utiliza todas as arestas exatamente uma vez e é fechado — é um ciclo euleriano.
Passo 9
Complexidade e detalhes práticos (o que você precisa saber para implementar direito):
- Complexidade de tempo: se você representar
como listas com iteradores que permitem remover arestas amortizadamente, o algoritmo roda em tempo (onde é o número de arestas) porque cada aresta é processada (visitada/removida) apenas uma vez. Cada push/pop da pilha é amortizado. - Complexidade de memória:
para armazenar o grafo e estruturas auxiliares. - Atenção ao grafo não direcionado: quando “remover” ou marcar a aresta
você precisa lidar com as duas entradas nas listas de adjacência ( e ). Uma técnica prática é numerar as arestas e marcar por id de aresta como usada, ao invés de tentar remover elementos por valor das listas. - Para grafos direcionados, o mesmo esquema funciona se as arestas tiverem orientação; a condição muda para
.
Passo 10
Casos especiais e dicas de prova/uso em exame (como responder rápido num teste):
- Primeiro verifique as condições (grau par e conectividade). Se falhar, responda que não existe ciclo euleriano.
- Se existir, descreva a ideia em 2–3 frases: “fazer um ciclo qualquer; enquanto sobrar aresta iniciar novo ciclo em um vértice do ciclo atual e inserir; repetir até usar todas as arestas.”
- Se o examinador pedir complexidade, diga
com justificativa de que cada aresta é processada uma vez. - Se pedirem implementação, escreva a versão com pilha (é a mais compacta) e explique que marcamos arestas como usadas por id.
Resposta
Comece em qualquer vértice com arestas, percorra arestas não usadas até voltar ao vértice inicial formando um ciclo; enquanto existirem arestas não usadas escolha um vértice do ciclo atual com arestas livres, faça um novo ciclo a partir dele usando apenas arestas não usadas e splicing (inserção) desse ciclo no ciclo principal; repita até não restarem arestas. O algoritmo usa cada aresta exatamente uma vez, funciona se e somente se (não direcionado) o grafo for conectado (ignorando vértices isolados) e todos os vértices tiverem grau par (ou, direcionado,
para todo
), e pode ser implementado em
usando uma pilha e listas de adjacência.