*53. Dê uma variante do algoritmo de Fleury para produzir caminhos eulerianos.
Passo 1
O enunciado pede uma variante do algoritmo de Fleury para construir um caminho (ou circuito) euleriano em um grafo conexo cuja todas vértices têm grau par (no caso de circuito) ou exatamente dois vértices têm grau ímpar (no caso de trilha). O conteúdo é teoria de grafos: encontrar trilha/circuito euleriano.
Passo 2
O algoritmo de Fleury clássico escolhe, a cada passo, uma aresta incidente ao vértice atual que não seja ponte (isto é, cuja remoção não desconecte o grafo), a menos que não haja outra opção. Isso garante que não isolemos parte do grafo antes de usar todas as arestas.
Passo 3
Para evitar o teste de ponte a cada passo (que é caro) e simplificar a implementação, podemos usar a ideia do algoritmo de Hierholzer como variante de Fleury:
– Em vez de testar pontes, percorremos qualquer aresta disponível até ficarmos sem arestas no vértice atual, formando um ciclo parcial.
– Quando travamos (grau zero), voltamos por um “caminho reverso” empilhado e inserimos esses vértices no circuito final, continuando de um ponto onde ainda restem arestas.
– Em vez de testar pontes, percorremos qualquer aresta disponível até ficarmos sem arestas no vértice atual, formando um ciclo parcial.
– Quando travamos (grau zero), voltamos por um “caminho reverso” empilhado e inserimos esses vértices no circuito final, continuando de um ponto onde ainda restem arestas.
Passo 4
Segue o pseudocódigo da variante:
Algoritmo Euleriano-Variante(G):
// G é conexo e tem uma trilha/circuito euleriano
1. stack ← [] // pilha de vértices
2. circuito ← [] // lista que armazenará a trilha final
3. escolha vértice inicial v0 // se há graus ímpares, escolha um deles; senão qualquer vértice
4. stack.push(v0)
5. enquanto stack ≠ [] faça
6. v ← stack.top()
7. se grau(v) > 0 então
8. escolha qualquer aresta não usada (v,w)
9. remova (v,w) de G
10. stack.push(w)
11. senão
12. stack.pop()
13. append v em circuito
14. retorna reverse(circuito)
Explicação das etapas:
- Mantemos uma pilha
stackpara lembrar o caminho atual. - Quando
vtem arestas, seguimos arbitrariamente por uma delas, removendo-a do grafo e empilhando o próximo vérticew. - Quando
vfica sem arestas, não há para onde ir: desempilhamosve o colocamos no início do roteiro final (circuito). - Ao final,
circuitocontém os vértices na ordem inversa; basta revertê-lo.
Passo 5
Correção e complexidade:
– Cada aresta é removida exatamente uma vez e cada vértice é empilhado/desempilhado no máximo grau(v) vezes.
– A complexidade é , onde
é número de vértices e
o número de arestas, bem melhor que o teste de ponte repetido em Fleury.
– A ordem final em
– Cada aresta é removida exatamente uma vez e cada vértice é empilhado/desempilhado no máximo grau(v) vezes.
– A complexidade é
– A ordem final em
circuito é uma trilha ou circuito euleriano válido.Resposta
Algoritmo Euleriano-Variante(G):
1. stack ← []
2. circuito ← []
3. escolha \(v_{0}\) (grau ímpar se existir, senão qualquer)
4. stack.push(\(v_{0}\))
5. enquanto stack ≠ [] faça
6. v ← stack.top()
7. se grau(v) > 0 então
8. escolha aresta (v,w) não usada
9. remova (v,w) de G
10. stack.push(w)
11. senão
12. stack.pop()
13. append v em circuito
14. retorna reverse(circuito)