Verificador de Caminho Hamiltoniano

Verificador de Caminho Hamiltoniano

O Verificador de Caminho Hamiltoniano decide se um grafo contém um caminho hamiltoniano — uma sequência que visita cada vértice exatamente uma vez — ou um ciclo hamiltoniano, que adicionalmente retorna ao vértice inicial. Ele combina verificações prévias estruturais rápidas (conectividade, pré-requisitos de grau, teorema de Dirac, teorema de Ore) com uma busca por backtracking ajustada pela heurística de Warnsdorff, e visualiza o caminho testemunha com uma animação passo a passo.

O que é um Caminho Hamiltoniano?

Dado um grafo G = (V, E) com n vértices, um caminho hamiltoniano é uma sequência ordenada v₁, v₂, …, v_n de todos os vértices tal que cada par consecutivo (v_i, v_i+1) é uma aresta de G, e cada vértice aparece exatamente uma vez. Se adicionalmente (v_n, v₁) for uma aresta, a sequência é um ciclo hamiltoniano.

O problema recebeu o nome de William Rowan Hamilton, que em 1857 inventou o jogo icosiano — um quebra-cabeça que pedia ao jogador para encontrar um ciclo visitando cada vértice de um dodecaedro regular exatamente uma vez.

Por que é difícil: NP-Completude

Tanto o problema de decisão do caminho hamiltoniano quanto o do ciclo hamiltoniano são NP-completos (Karp, 1972). A menos que P = NP, não existe algoritmo de tempo polinomial que resolva todas as instâncias. No pior caso, o backtracking explora uma árvore de busca de tamanho até (n−1)! para um ciclo. É por isso que a calculadora limita a entrada a 20 vértices — um pequeno aumento polinomial em n produz um aumento explosivo no tempo de execução.

Na prática, a heurística de Warnsdorff (originalmente concebida por Heinrich Warnsdorff em 1823 para a jornada do cavalo) torna a busca dramaticamente mais rápida em grafos estruturados: em cada passo, o algoritmo estende o caminho atual para o vizinho não visitado com o menor número de vizinhos restantes não visitados. Esta regra gananciosa evita que a busca fique sem saída e frequentemente encontra um tour hamiltoniano com zero retrocessos em grafos bem comportados.

Condições Necessárias — Rejeição Rápida

Antes de executar uma busca custosa, a calculadora rejeita grafos que não podem conter um caminho hamiltoniano:

• Conectividade. Um caminho hamiltoniano deve visitar cada vértice, portanto, o grafo deve ter exatamente uma componente conectada. Para grafos direcionados, a conectividade fraca (ignorando a direção das setas) é necessária.
• Grau (não direcionado). No máximo dois vértices podem ter grau 1 — esses são os únicos candidatos para as extremidades do caminho. Para um ciclo hamiltoniano, cada vértice deve ter grau pelo menos 2.
• Grau (direcionado). Para um caminho hamiltoniano, no máximo um vértice pode ter grau de entrada 0 (o início) e no máximo um pode ter grau de saída 0 (o fim). Para um ciclo hamiltoniano, cada vértice deve ter tanto grau de entrada ≥ 1 quanto grau de saída ≥ 1.

Essas regras rejeitam muitas entradas sem esperança em tempo linear, evitando o esforço desperdiçado de backtracking.

Condições Suficientes — Teoremas Clássicos

Vários teoremas clássicos fornecem condições suficientes (mas não necessárias) que garantem um ciclo hamiltoniano em grafos simples não direcionados. Se qualquer um deles se aplicar, a calculadora marca o resultado como "GARANTE" sem sequer executar a busca — embora ainda exiba um ciclo testemunha.

Teorema de Dirac (1952)

Se G é um grafo simples não direcionado com n ≥ 3 vértices e cada vértice tem grau pelo menos n / 2, então G possui um ciclo hamiltoniano.

Teorema de Ore (1960)

Se para cada par de vértices não adjacentes u e v tivermos deg(u) + deg(v) ≥ n, então G possui um ciclo hamiltoniano. A condição de Ore é estritamente mais fraca que a de Dirac, portanto, Ore implica Dirac.

A falha na condição de Dirac ou Ore não significa que o grafo carece de um ciclo hamiltoniano — muitos grafos não satisfazem nenhuma delas, mas ainda assim contêm um (por exemplo, um ciclo simples de n vértices tem grau mínimo 2, bem abaixo de n/2 para n grande).

O Algoritmo de Busca Interno

Quando as pré-verificações não resolvem a questão, a calculadora executa uma busca por backtracking na representação de adjacência do grafo. Táticas principais:

1. Conjunto visitado por Bitmask. Os vértices visitados são armazenados como um bitmask (teste de associação rápido O(1) para até 20 vértices).
2. Heurística de Warnsdorff. Em cada extensão, os vizinhos são testados na ordem de seus graus não visitados restantes (menor primeiro), imitando uma ordem de "baixa ramificação".
3. Seleção de raiz. Para ciclo hamiltoniano, apenas um vértice inicial é necessário (ciclos são invariantes por rotação). Para caminho hamiltoniano, os inícios são testados em ordem crescente de grau de saída — as posições mais raras primeiro.
4. Limite de passos. Um limite rígido evita que instâncias patológicas rodem indefinidamente; a interface reporta o veredito como "expirado" se o limite for atingido.

Hamiltoniano vs Euleriano

É fácil confundir problemas hamiltonianos e eulerianos — eles soam parecidos, mas são fundamentalmente diferentes:

Formatos de Entrada Suportados

Lista de arestas

Uma aresta por linha ou separadas por vírgula. Separadores suportados: A-B, A B, A,B, A--B, A->B, A<-B. Use -> para forçar uma interpretação direcionada.

Matriz de adjacência

Matriz quadrada de valores 0/1, uma linha por linha, separada por espaço ou vírgula. Forneça rótulos opcionais no campo Rótulos da Matriz; caso contrário, A, B, C… são usados automaticamente.

Como usar este verificador

1. Escolha um formato de entrada — Lista de Arestas para grafos pequenos escritos à mão, Matriz de Adjacência para colagens de código ou livros didáticos.
2. Cole seu grafo na área de texto. Para entrada de matriz, forneça rótulos de vértices opcionalmente.
3. Escolha o que verificar: Apenas Caminho, Apenas Ciclo ou Ambos em uma execução.
4. Selecione o tipo de grafo — A detecção automática infere a direcionalidade pelo estilo da seta (->) ou pela simetria da matriz.
5. Clique em Verificar Hamiltoniano. A página de resultados mostra um título de veredito, a pré-verificação de condição necessária, os testes de condição suficiente Dirac / Ore, o caminho testemunha (se houver) e uma visualização interativa.
6. Reproduza a testemunha usando os controles Play / Step. Veja o caminho acender aresta por aresta no grafo.

Exemplo Prático — O Grafo de Petersen

O famoso grafo de Petersen (10 vértices, 15 arestas, 3-regular) é um exemplo clássico de um grafo com um caminho hamiltoniano, mas sem ciclo hamiltoniano. Cole isto no campo da lista de arestas e clique em Verificar:

O verificador confirma: caminho hamiltoniano encontrado (ex: 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), mas a busca exaustiva não encontra maneira de fechar o laço de volta — um resultado provado pela primeira vez na década de 1890.

Aplicações Comuns

• Roteamento e o Problema do Caixeiro Viajante — cada tour do TSP é um ciclo hamiltoniano no grafo ponderado completo.
• Montagem de genoma — a reconstrução de uma sequência de DNA a partir de leituras sobrepostas pode ser modelada como um caminho hamiltoniano em um grafo de sobreposição.
• Layout de circuito — ordenação de pinos em um PCB para fiação de comprimento mínimo.
• IA de jogos e solução de quebra-cabeças — jornadas do cavalo em um tabuleiro de xadrez, jogo icosiano.
• Agendamento — sequenciamento de tarefas para que cada uma mude de forma viável para a próxima.
• Ensino de combinatória — ilustração de NP-completude com pequenos exemplos solucionáveis à mão.

Perguntas Frequentes

O que é um caminho hamiltoniano?

Um caminho hamiltoniano é um trajeto em um grafo que visita cada vértice exatamente uma vez. Recebe o nome de William Rowan Hamilton, que estudou o problema no grafo do dodecaedro em 1857. Decidir se tal caminho existe é um problema NP-completo, portanto, nenhum algoritmo conhecido o resolve em tempo polinomial para todos os grafos.

Qual a diferença entre um ciclo hamiltoniano e um caminho hamiltoniano?

Um ciclo hamiltoniano é um caminho hamiltoniano que retorna ao seu vértice inicial, formando um laço fechado que visita cada vértice exatamente uma vez. Todo ciclo hamiltoniano contém um caminho hamiltoniano (basta remover a aresta de fechamento), mas o inverso não é verdadeiro: muitos grafos têm um caminho hamiltoniano, mas nenhum ciclo hamiltoniano.

O que diz o teorema de Dirac?

O teorema de Dirac (1952) afirma que qualquer grafo simples não direcionado com n ≥ 3 vértices no qual cada vértice tem grau pelo menos n/2 contém um ciclo hamiltoniano. É uma condição suficiente, mas não necessária: muitos grafos que não atingem o limite de Dirac ainda possuem ciclos hamiltonianos.

O que diz o teorema de Ore?

O teorema de Ore (1960) afirma que se, para cada par de vértices não adjacentes u e v em um grafo simples com n ≥ 3 vértices, a soma de seus graus for pelo menos n, então o grafo tem um ciclo hamiltoniano. A condição de Ore é mais fraca que a de Dirac, portanto, o teorema de Ore se aplica sempre que o teorema de Dirac se aplicar.

Por que a busca é limitada a 20 vértices?

Os problemas de decisão de caminho e ciclo hamiltoniano são NP-completos. O tempo de execução no pior caso escala exponencialmente com o número de vértices. Com poda e a heurística de Warnsdorff, a calculadora processa muitos grafos pequenos de até 20 vértices rapidamente, mas instâncias mais complexas podem expirar o tempo. Além de 20 vértices, você deve usar solvers especializados como o Concorde ou formulações de programação inteira.

O que é a heurística de Warnsdorff?

A regra de Warnsdorff, proposta em 1823 para o problema da jornada do cavalo, diz que a cada passo você deve visitar o próximo vértice que tenha o menor número de vizinhos restantes não visitados. Esta regra de aparência gananciosa poda drasticamente a árvore de backtracking na prática e frequentemente encontra caminhos hamiltonianos sem qualquer retrocesso em grafos regulares.

Esta ferramenta encontra todos os caminhos hamiltonianos?

Não — ela encontra um único caminho ou ciclo testemunha quando ele existe. Contar o número total de caminhos hamiltonianos é em si um problema #P-completo e muito mais difícil do que o problema de decisão. Para enumeração, ferramentas especializadas ou solvers de programação inteira são mais apropriados.

Leitura Adicional

• Caminho Hamiltoniano — Wikipédia (Inglês)
• Problema do caminho hamiltoniano — Wikipédia (Inglês)
• Teorema de Dirac sobre ciclos hamiltonianos — Wikipédia (Inglês)
• Teorema de Ore — Wikipédia (Inglês)
• Regra de Warnsdorff — Wikipédia (Inglês)

Operações matemáticas avançadas:

• Calculadora de Matriz de Adjacência Novo
• Calculadora de Antilog
• Calculadora de Função Beta
• Calculadora de Coeficiente Binomial
• Calculadora de distribuição binomial
• Calculadora de Lógica Binária
• Simplificador de Álgebra Booleana Novo
• Calculadora do Teorema Central do Limite
• Calculadora do Teorema Chinês do Resto
• Calculadora de Combinação Popular
• Calculadora de Função de Erro Complementar
• Calculadora de Números Complexos Popular
• Calculadora de Frações Contínuas
• Calculadora de Desarranjo (Subfatorial)
• Calculadora de Caminho Mais Curto de Dijkstra
• Calculadora de Entropia
• Calculadora da função de erro
• Calculadora da Função Totiente de Euler
• Calculadora de decaimento exponencial
• Calculadora de Crescimento Exponencial de Alta Precisão
• Calculadora de Integral Exponencial
• Calculadora de Expoentes (Alta Precisão) Popular
• Calculadora do Algoritmo Euclidiano Estendido
• Calculadora de Fatorial
• Calculadora de Função Gama
• Calculadora de Proporção Áurea
• Calculadora de Coloração de Grafos Novo
• Validador de Sequência de Graus de Grafo
• Calculadora de Ordem em Teoria dos Grupos Novo
• Calculadora de Meia-Vida
• Verificador de Caminho Hamiltoniano Novo
• Calculadora de Inclusão-Exclusão Novo
• Solucionador de Mapa de Karnaugh (K-Map) Novo
• Solucionador de Programação Linear Novo
• Calculadora de Estado Estacionário da Cadeia de Markov
• Calculadora de Árvore Geradora Mínima
• Calculadora de Exponenciação Modular Novo
• Calculadora do Inverso Multiplicativo Modular
• Calculadora de Distribuição Binomial Negativa Novo
• Calculadora de Fluxo em Rede (Fluxo Máximo) Novo
• Calculadora de Taxa de Crescimento Percentual Popular
• Calculadora de Permutação
• Calculadora de Permutações com Repetição Novo
• Calculadora do Princípio da Casa dos Pombos
• Verificador de Grafo Planar Novo
• Calculadora de Distribuição de Poisson
• Calculadora de Raízes de Polinômios
• Calculadora de Raiz Primitiva
• Calculadora de Probabilidade
• Calculadora de Distribuição de Probabilidade
• Calculadora de Proporção Popular
• Calculadora de Fórmula Quadrática
• Calculadora de Anéis e Corpos Novo
• Calculadora de Arredondamento Novo
• Calculadora Científica
• Calculadora de notação científica
• Calculadora de Teoria dos Conjuntos
• Calculadora de Algarismos Significativos Novo
• Solucionador do Problema do Casamento Estável Novo
• Calculadora de Números de Stirling
• Calculadora de Soma de Cubos
• Calculadora de soma de inteiros positivos
• Calculadora de Soma dos Quadrados
• Calculadora de Ordenação Topológica Novo
• Solucionador do Caixeiro Viajante (TSP) Novo
• Gerador de Tabela Verdade Popular
• Gerador de Diagrama de Venn (3 Conjuntos)