Problema del camí Hamiltoniano

Erro al crear miniatura:

En el camp matemàtic de la teoria de grafos, el problema del camí hamiltoniano i el problema cicle d'Hamilton són problemes de determinar si un camí hamiltoniano o un cicle d'Hamilton existix en un grafo donat. Abdós problemes són NP-complet.

En el camp matemàtic de la teoria de grafos, el problema del camí hamiltoniano i el problema cicle d'Hamilton són problemes de determinar si un camí hamiltoniano o un cicle d'Hamilton existix en un grafo donat (ya siga dirigit o no dirigit). Abdós problemes són NP-complet.

Relació entre problemes

Existix una relació simple entre els problemes de trobar un camí d'Hamilton i un cicle Hamiltoniano. En una direcció, el problema del camí Hamiltoniano per al grafo G és equivalent al problema cicle Hamiltoniano en un grafo H obtingut de G per mig de l'adició d'un nou vèrtiç i de la conexió a tots els vèrtiços de G. Per lo tant, la busca d'un camí d'Hamilton no pot ser significativament més llenta (en el pijor dels casos, com una funció del número de vèrtiços) que trobar un cicle d'Hamilton.

En l'atra direcció, un grafo G té un cicle d'Hamilton utilisant l'aresta uv i solament si el grafo H és obtingut per G per mig de la substitució de l'aresta per un parell de vèrtiços de grau 1, un conectat a o i l'atre conectat a v, té un camí d'Hamilton. Per lo tant, en tractar esta substitució per a totes les arestes incidents fins a cert vèrtiç seleccionat de G, el problema del cicle Hamiltoniano pot ser resolt com a màxim per n càlculs en la majoria dels camins Hamiltonianos, a on n és el número de vèrtiços en el grafo.

El problema del Cicle hamiltoniano és també un cas especial del Problema del viajante, obtingut per mig de l'establiment de la distància entre dos ciutats a un si són adjacents i dos en un atre cas, i la verificació de que la distància total recorreguda és igual a n (si és aixina, la ruta és un circuit hamiltoniano; si no hi ha circuit Hamiltoniano a continuació llavors la ruta més curta serà més llarga).

Algoritmes

Hi ha n! diferents seqüències de vèrtiços que poden ser camins Hamiltonianos donat un grafo de n vèrtiços (i són, en un grafo complet), per lo que un algoritme de busca de força bruta que posa a prova totes les possibles seqüències serien molt llent. Hi ha varis enfocaments més ràpits. Un procediment de busca per Frank Rubin dividix a les arestes del grafo en tres classes: els que deuen estar en el camí, els que no poden estar en el camí, i indecisos. A mida que procedix la busca, un conjunt de regles de decisió que classifica les arestes indecises, i determina si es deu detindre o continuar la busca. L'algoritme dividix el grafo en components que poden ser resoltes per separades. Ademés, un algoritme de programació dinàmica de Bellman, Held, i Karp pot ser utilisat per a resoldre el problema en un temps O(n² 2ⁿ). En este método, es determina, per a cada conjunt S de vèrtiços i cada vèrtiç v en S, si existix un camí que cobrix exactament els vèrtiços en S i termina en v. Per a cada elecció de S i v, existix un camí per a (S,v) si i solament si v té un veí w tal que existix un camí per a (S - v,w), que pot ser vist de l'informació ya calculada en la solució dinàmica.

Andreas Björklund va proporcionar un enfocament alternatiu utilisant el principi d'inclusió-exclusió per a reduir el problema de contar el número de cicles Hamiltonianos a un problema de conteo més simple, de contar les cobertes del cicle, que pot ser resolt per mig del càlcul de certs determinants. L'us d'este método, es va mostrar cóm resoldre el problema del cicle Hamiltoniano en els grafos n-vèrtiços arbitraris per mig d'un Algoritme de Mont Carlo en orde O(1.657ⁿ); per a grafos bipartitos este algoritme pot ser millorat en orde O(1.414ⁿ).

Per a grafos de màxim grau tres, una busca cuidadosa pot donar marcha arrere i trobar un cicle d'Hamilton (si existix) en orde O(1.251ⁿ).

Per la dificultat de resoldre el camí d'Hamilton i problemes del cicle en els equips convencionals, també s'han estudiat en models poc convencional de la computació. Per eixemple, Leonard Adleman va mostrar que el problema del camí Hamiltoniano pot ser resolt usant un ordenador ADN. Explotar el paralelisme inherent en les reaccions químiques, el problema pot ser resolt utilisant un número d'etapes de reacció químiques llineals en el número de vèrtiços delgrafo, no obstant, es requerix un número factorial de distints tipos de molècula de ADN de participar en la reacció.