Problema do caminho hamiltoniano
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]
Relações entre os problemas[editar | editar código-fonte]
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.
Algoritmos[editar | editar código-fonte]
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.
Complexidade[editar | editar código-fonte]
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]
Referências[editar | editar código-fonte]
- ↑ Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. [S.l.]: W.H. Freeman. ISBN 0-7167-1045-5 A1.3: GT37–39, pp. 199–200.
- ↑ Rubin, Frank (1974), «A Search Procedure for Hamilton Paths and Circuits», Journal of the ACM, 21: 576-80.
- ↑ Bellman, R. (1962), «Dynamic programming treatment of the travelling salesman problem», Journal of the ACM, 9: 61–63, doi:10.1145/321105.321111.
- ↑ Held, M.; Karp, R. M. (1962), «A dynamic programming approach to sequencing problems», J. SIAM, 10 (1): 196–210, doi:10.1137/0110015.
- ↑ Björklund, Andreas (2010), «Determinant sums for undirected Hamiltonicity», Proc. 51st IEEE Symposium on Foundations of Computer Science (FOCS '10), pp. 173–182, arXiv:1008.0541
, doi:10.1109/FOCS.2010.24.
- ↑ Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), «Some simplified NP-complete problems», Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884.
- ↑ Plesńik, J. (1979), «The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two» (PDF), Information Processing Letters, 8 (4): 199–201.
- ↑ Akiyama, Takanori; Nishizeki, Takao; Saito, Nobuji (1980-1981), «NP-completeness of the Hamiltonian cycle problem for bipartite graphs» (PDF), Journal of Information Processing, 3 (2): 73–76, MR 596313[ligação inativa].
- ↑ Thomason, A. G. (1978), «Hamiltonian cycles and uniquely edge colourable graphs», Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, 3, pp. 259–268, MR 499124, doi:10.1016/S0167-5060(08)70511-9.
- ↑ Papadimitriou, Christos H. (1994), «On the complexity of the parity argument and other inefficient proofs of existence», Journal of Computer and System Sciences, 48 (3): 498–532, MR 1279412, doi:10.1016/S0022-0000(05)80063-7.
