Um grafo é semieuleriano se ele possui exatamente dois vértices de grau ímpar. Esse caminho que percorre todas as arestas exatamente uma vez é chamado de caminho euleriano.
Faça uma pesquisa e responda o que é o algoritmo de Hierholzer?
Exemplifique usando o grafo a seguir. Encontre os circuitos fechados e faça a união entre eles!
- Hierholzer.png (58.74 KiB) Exibido 6213 vezes
Trata-se de um algoritmo para que seja possível determinar uma cadeia fechada, ou seja, um algoritmo que determina diferentes ciclos e depois os une para formar um ciclo euleriano.
Temos 3 ciclos:
• C = {c, f, g, i, h, a, b, c}
• H = {a, c, g, c, e, h, d, a}
• K = {d, b, e, f, i, e, d}
O que é o ciclo hamiltoniano?
• Este ciclo diz que devemos partir de um vértice e passar por todos os vértices do grafo sem repeti-los.