O que é um caminho hamiltoniano?

É um caminho através de um grafo que visita cada vértice exatamente uma vez, usando apenas arestas que existem no grafo — não precisa voltar ao seu ponto de partida (isso o tornaria um ciclo hamiltoniano).

Por que é difícil encontrar um caminho hamiltoniano?

O problema do caminho hamiltoniano é NP-completo, significando que nenhum algoritmo conhecido o resolve dramaticamente mais rápido do que testar combinações de ordenações, e o número de ordenações possíveis cresce fatorialmente com o número de nós.

Por que esta calculadora é limitada a 10 nós?

A busca com retrocesso explora um espaço de busca que pode crescer fatorialmente no pior caso. Dez nós mantém essa busca confortavelmente rápida para uma ferramenta baseada em navegador, cobrindo ainda a maioria dos exemplos de grafos inseridos manualmente que as pessoas querem verificar.

Como funciona a busca com retrocesso?

Ela constrói um caminho um nó de cada vez, sempre se estendendo a um vizinho não visitado; se atingir um beco sem saída onde nenhum vizinho não visitado está disponível, ela retrocede (desfaz o último passo) e tenta um vizinho diferente, repetindo a partir de cada possível nó inicial.

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

Um caminho hamiltoniano só precisa visitar cada vértice uma vez; um ciclo hamiltoniano adicionalmente exige que o caminho retorne ao seu vértice inicial, formando um laço fechado — ambos são NP-completos de detectar.

Todo grafo tem um caminho hamiltoniano?

Não — muitos grafos, especialmente esparsos ou desconectados, não têm nenhum. Um grafo desconectado nunca pode ter um caminho hamiltoniano, já que o caminho precisaria saltar entre componentes sem nenhuma aresta para usar.

Como isso difere da Calculadora de Árvore Geradora Mínima?

Uma árvore geradora mínima conecta cada nó usando uma estrutura de árvore (que pode se ramificar), enquanto um caminho hamiltoniano é uma única linha sem ramificações que visita cada nó exatamente uma vez — um requisito muito mais restritivo.

Onde o problema do caminho hamiltoniano é usado na vida real?

Está intimamente relacionado ao problema do caixeiro viajante e aparece em planejamento de rotas, sequenciamento de DNA (montagem de fragmentos), e problemas de quebra-cabeça como o passeio do cavalo em um tabuleiro de xadrez.

Verificador de Caminho Hamiltoniano — Encontre um Caminho que Visite Cada Nó Exatamente Uma Vez

Nosso Verificador de Caminho Hamiltoniano busca um caminho através de um grafo que visite cada nó exatamente uma vez, tentando cada possível nó inicial e retrocedendo através de rotas possíveis, com seu grafo inserido como uma lista de arestas em texto simples (ex. A-B, B-C, C-D).

Resposta rápida

Digite seu grafo como uma lista de arestas (até 10 nós) para buscar instantaneamente um caminho hamiltoniano — uma rota que visita cada nó exatamente uma vez — via retrocesso.

Arestas (separadas por vírgula)

Digite arestas como NóA-NóB, ex. A-B, B-C, C-D. Máximo de 10 nós.

Como usar Verificador de Caminho Hamiltoniano — Visite Cada Nó Uma Vez Online

1
Digite seu grafo como uma lista de arestas separadas por vírgula, ex. A-B, B-C, C-D.
2
Clique em 'Calcular' para buscar um caminho hamiltoniano.
3
Revise o caminho encontrado, ou a confirmação de que nenhum existe.

Por que usar Verificador de Caminho Hamiltoniano — Visite Cada Nó Uma Vez Online?

Um caminho hamiltoniano visita cada vértice de um grafo exatamente uma vez — diferente de um caminho euleriano, que trata de visitar cada aresta, este trata de visitar cada nó. Determinar se um existe é NP-completo em geral, significando que nenhum algoritmo conhecido é dramaticamente mais rápido do que testar possibilidades sistematicamente, então esta calculadora usa busca com retrocesso: constrói um caminho um nó de cada vez, e retrocede sempre que um beco sem saída é alcançado, tentando cada possível nó inicial. Como o espaço de busca cresce fatorialmente com o tamanho do grafo, esta calculadora é deliberadamente limitada a no máximo 10 nós, onde a busca exaustiva com retrocesso ainda se completa instantaneamente.

Perguntas frequentes

Ferramentas relacionadas

Solucionador do Caixeiro Viajante — Programação Dinâmica Exata de Held-Karp Online

Encontre a rota de ida e volta mais curta exata que visita cada cidade exatamente uma vez, usando o algoritmo de programação dinâmica de Held-Karp. Calculadora gratuita, até 12 cidades.

Calculadora de Ordenação Topológica — Algoritmo de Kahn Online

Encontre uma ordem topológica válida para um grafo direcionado usando o algoritmo de Kahn, ou detecte que nenhuma ordem existe devido a um ciclo. Calculadora gratuita com uma entrada simples de lista de arestas.

Calculadora de Árvore Geradora Mínima — Algoritmo de Kruskal Online

Encontre a árvore geradora mínima de um grafo ponderado usando o algoritmo de Kruskal. Calculadora gratuita com uma entrada simples de lista de arestas e detecção de ciclos via union-find.