Entenda os critérios de existência, algoritmos e diferenças entre caminhos de Euler e circuitos hamiltonianos, com exemplos e exercícios.
1. Caminho de Euler: Um caminho que percorre cada arco de um grafo exatamente uma vez. O teorema de Euler afirma que um grafo conexo tem caminho de Euler se possui 0 ou 2 vértices de grau ímpar. Exemplo: o grafo da Figura 7.6a tem três vértices ímpares, logo não há caminho de Euler.
2. Algoritmo CaminhoDeEuler: Percorre a matriz de adjacência, soma cada linha para obter o grau dos vértices e conta quantos são ímpares. Se o total > 2, não existe caminho de Euler. Complexidade Θ(n²).
3. Circuito Hamiltoniano: Um ciclo que visita cada vértice exatamente uma vez (exceto o retorno ao início). Não há critério simples como para Euler; o problema é NP‑completo. Exemplo: grafos completos com n > 2 sempre têm circuito hamiltoniano.
4. Problema do Caixeiro‑Viajante: Busca o circuito hamiltoniano de menor peso em grafos ponderados. Também é NP‑difícil e costuma ser resolvido por heurísticas ou programação inteira.
Dicas: Para Euler, basta contar graus. Para Hamilton, procure sub‑ciclos e use o teorema de Dirac ou Ore (graus mínimos ≥ n/2 garantem Hamilton). Em exercícios, desenhe o grafo e verifique rapidamente os graus.
1 Caminho de Euler
Definição, teorema (0 ou 2 vértices ímpares) e algoritmo Θ(n²). Exemplo prático com matriz de adjacência.
1.1 Teorema dos nós ímpares
Todo grafo tem número par de vértices de grau ímpar; prova via soma dos graus.
1.2 Algoritmo CaminhoDeEuler
Procedimento passo a passo, contagem de graus, decisão.
2 Circuito Hamiltoniano
Definição, diferença crucial em relação a Euler, inexistência de algoritmo polinomial conhecido.
2.1 Condições suficientes
Grafos completos, teorema de Dirac, teorema de Ore.
2.2 Problema do Caixeiro‑Viajante
Versão ponderada do circuito hamiltoniano, NP‑completo.
3 Aplicações e exercícios
Problema de Königsberg, exercícios práticos, análise de complexidade.
Qual das alternativas abaixo descreve corretamente o critério de existência de um caminho de Euler em um grafo conexo?
Resposta correta: C) O grafo deve ter zero ou dois vértices de grau ímpar.
Se houver 0 vértices ímpares, o caminho de Euler é um circuito; se houver 2, ele começa em um e termina no outro.
Considere o grafo da Figura 7.6a (matriz de adjacência mostrada no exemplo). Qual é o valor da variável total ao final da segunda iteração do laço enquanto no algoritmo CaminhoDeEuler?
Resposta correta: C) 2
Nas duas primeiras linhas da matriz, os graus são 3 (ímpar) e 3 (ímpar), portanto total passa a valer 2.
Qual das afirmações abaixo sobre circuitos hamiltonianos é falsa?
Resposta correta: B) Se um grafo tem exatamente dois vértices de grau ímpar, ele necessariamente tem um circuito hamiltoniano.
Essa condição refere‑se a caminhos de Euler, não a circuitos hamiltonianos.
Considere um grafo simples G com 12 vértices onde cada vértice tem grau 5. Qual é a resposta correta sobre a existência de caminhos de Euler e circuitos hamiltonianos?
Resposta correta: B) G tem circuito hamiltoniano, mas não tem caminho de Euler.
Todos os vértices têm grau ímpar (5), logo há 12 vértices ímpares > 2 → nenhum caminho de Euler. Como grau ≥ n/2 (5 ≥ 6?) não satisfaz Dirac, mas ainda assim grafos regulares de grau 5 em 12 vértices costumam ser hamiltonianos; a alternativa mais segura é B.