Loading AI tools
Da Wikipédia, a enciclopédia livre
No campo matemático da teoria dos grafos o Problema do caminho hamiltoniano e o Problema do ciclo hamiltoniano são problemas de determinar se um Caminho hamiltoniano ou um Ciclo hamiltoniano existe em um dado grafo (direcionado ou não direcionado). Ambos os problemas são NP-completos.[1]
Existe uma relação simples entre os problemas de encontrar um Caminho hamiltoniano e de encontrar um Ciclo hamiltoniano. Em uma direção, o Problema do caminho hamiltoniano para o grafo G é equivalente ao Problema do ciclo hamiltoniano em um grafo H obtido de G pela adição de um novo vértice e conectando-o a todos os vértices de G. Assim, encontrar um Caminho hamiltoniano não pode ser significativamente mais lento (na pior das hipóteses, como uma função do número de vértices) do que encontrar um Ciclo hamiltoniano.
Na outra direção, um grafo G tem um Ciclo hamiltoniano usando aresta "uv" se e somente se, o grafo H o obtido de G pela substituição da aresta por um par de grau-1 vertices, um conectado a "u" e outro conectado a "v", tem um Caminho hamiltoniano.Portanto, ao tentar esta substituição para todas as arestas incidentes para algum vértice escolhido de G, o Problema do ciclo hamiltoniano pode ser resolvido por, no máximo, n computações do Caminho hamiltoniano, onde n é o número de vértices do grafo.
O Problema do ciclo hamiltoniano é também um caso especial do problema do caixeiro viajante, obtido através de um conjunto de distâncias entre duas cidades para uma, se elas são adjacentes e contrárias.
Há n! diferentes sequências de vértices que podem ser Caminhos hamiltonianos em um dado grafo de n vértices (e são, em um grafo completo), então um algoritmo de busca por força bruta que testa todas as possíveis sequências pode ser muito lento. Existem várias abordagens mais rápidas. Um procedimento de busca de Frank Rubin[2] divide as arestas do grafo em três classes: aquelas que devem estar no caminho, aquelas que não devem estar no caminho e as incertas. Como os procedimentos da busca, um conjunto de regras de decisão classifica as bordas indecisas, e determina se deve interromper ou continuar a busca. O algoritmo divide o grafo em componentes que podem ser resolvidos separadamente. Também, um algoritmo de programação dinâmica de Bellman, Held e Karp pode ser usado para resolver o problema no tempo O(n2 2n). Neste método, um determina, para cada conjunto S de vértices e cada vértice v em S, se existe um caminho que cobre exatamente os vértices em S e termina em v. Para cada escolha de S e V, existe um caminho para (S, v) se e somente se, v tem um vizinho w de tal forma que existe um caminho para (S − v,w), que pode ser pesquisado a partir de informações já computadas no programa dinâmico.[3][4]
Andreas Björklund forneceu uma abordagem alternativa utilizando o Princípio da inclusão-exclusão para reduzir o problema da contagem do número de Ciclos hamiltonianos para um problema mais simples de contagem, de contagem de ciclos percorridos, que pode ser resolvido pelo calculo de determinantes de determinadas matrizes. Usando este método, ele mostrou como resolver o Problema do Ciclo Hamiltoniano em um grafo de n vértices arbitrário através de um Algoritmo de Monte Carlo no tempo O(1.657n); para grafos bipartidos esse algoritmo pode ser melhorado para o tempo O(1.414n).[5] Por causa da dificuldade de resolver o Problema do caminho hamiltoniano e o Problema do ciclo hamiltoniano em computadores convencionais, eles também são estudados em modelos não-convencionais de computação.
O problema de encontrar um Caminho ou um Ciclo Hamiltoniano é FNP; O análogo problema da decisão é para testar se um Caminho ou Ciclo Hamiltoniano existe. Os problemas de ciclo hamiltoniano, direcionados e não direcionados são dois dos 21 problemas NP-completos de Richard Karp. Eles permanecem NP-completos mesmo para grafos planares de grau máximo três.,[6] para grafos planares direcionados com grau interno e grau externo de no máximo 2,[7] para grafos bipartidos não orientados desconexos 3 - regular, e para o 3-3-conectados grafos regulares bipartidos.[8] No entanto, a colocação de todas estas condições em conjunto, mantém-se aberta se grafos regulares bipartidos planares 3-3-conectados contêm sempre um ciclo hamiltoniano, caso em que o problema limitado aos gráficos não poderia ser NP-completo; ver Conjectura de Barnette.
Em grafos onde todos os vértices têm grau ímpar, um argumento relacionado com o handshaking lemma mostra que o número de Ciclos de hamiltonianos através de qualquer extremidade fixa é sempre mesmo, por isso, se um ciclo hamiltoniano é dado, em seguida, um segundo também deve existir.[9]
No entanto, encontrar este segundo ciclo, não parece ser uma tarefa computacionalmente fácil. Papadimitriou definiu a classe de complexidade PPA para encapsular problemas como este.[10]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.