Problema drumului hamiltonian

Problema drumului hamiltonian și problema ciclului hamiltonian  sunt probleme de determinare dacă există o cale hamiltoniană sau un ciclu hamiltonian într-un grafic dat ( direcționat sau nedirecționat ). Ambele probleme sunt NP-complete [1] .

Relația dintre problemele de pe calea hamiltoniană și ciclul hamiltonian

Există o relație simplă între problemele de a găsi o cale hamiltoniană și de a găsi un ciclu hamiltonian. Într-o direcție, problema unei căi hamiltoniene pentru un grafic este echivalentă cu problema unui ciclu hamiltonian dintr-un grafic H obținut dintr-un grafic G prin adăugarea unui nou vârf și conectarea acestuia la toate vârfurile graficului G. Astfel, găsirea o cale hamiltoniană nu poate fi semnificativ mai lentă (în cel mai rău caz, , în funcție de numărul de vârfuri) decât căutarea unui ciclu hamiltonian.

În sens opus, problema unui ciclu hamiltonian pentru un grafic G este echivalentă cu problema unui drum hamiltonian într-un grafic H obţinută prin copierea unui vârf v al graficului G (în v'), adică vârful v ' va avea aceeași vecinătate cu v și adăugând două vârfuri auxiliare de gradul unu, dintre care unul este legat de v, iar celălalt de v' [2] .

Problema ciclului hamiltonian este, de asemenea, un caz special al problemei vânzătorului ambulant , obținută prin setarea tuturor distanțelor dintre două puncte la unul dacă sunt adiacente și două în caz contrar. După rezolvarea problemei vânzătorului ambulant, verificați dacă distanța totală este egală cu n (dacă da, traseul este un ciclu hamiltonian, dacă nu există un ciclu hamiltonian, calea cea mai scurtă va fi mai lungă decât această valoare).

Algoritmi

Sunt n ! secvențe diferite de vârfuri, care ar putea fi căi hamiltoniene într-un graf dat cu n vârfuri (și sunt atât de multe în graficul complet ), astfel încât un algoritm de forță brută care încearcă toate secvențele posibile ar fi foarte lent.

Un algoritm exact timpuriu pentru găsirea unui ciclu hamiltonian într-un graf direcționat a fost algoritmul de enumerare (algoritmul lui Martello) [3] .

Procedura de căutare a lui Frank Rubin [4] împarte muchiile graficului în trei clase - cele care trebuie să fie pe cale, cele care nu pot aparține căii și muchii pentru care nu a fost luată nicio decizie. În timpul căutării, un set de reguli de decizie clasifică marginile pentru care nu a fost luată nicio decizie și determină dacă să se oprească sau să continue căutarea. Algoritmul împarte graficul în componente care pot fi procesate separat.

Pentru a rezolva problema în timp , se poate folosi algoritmul de programare dinamică Bellman, Held și Karp . Această metodă determină, pentru fiecare set S de vârfuri și fiecare vârf v al lui S , dacă există o cale care trece prin toate vârfurile lui S și se termină la v . Pentru fiecare pereche ( S , v ) există o cale dacă și numai dacă v are un vârf w învecinat astfel încât să existe o cale pentru , care poate fi obținută din informațiile de programare dinamică deja obținute [5] [6] .

Andreas Björklund oferă o abordare alternativă folosind principiul includerii/excluderii pentru a reduce numărul de cicluri hamiltoniene iterate, iar problema numărării ciclului poate fi rezolvată prin calcularea determinantului unei matrice.

Folosind această metodă, el a arătat cum se rezolvă problema ciclului hamiltonian pentru grafice arbitrare cu n vârfuri folosind algoritmul Monte Carlo în timp . Pentru graficele bipartite, acest algoritm poate fi îmbunătățit până la timp [7] .

Pentru grafice cu gradul maxim trei, o căutare exactă de backtracking poate găsi un ciclu hamiltonian (dacă există unul) în timp [8] .

Căile și ciclurile hamiltoniene pot fi găsite folosind soluția SAT .

Datorită complexității rezolvării problemelor hamiltoniene de cale și ciclu pe computere obișnuite, acestea au fost studiate pentru modele de calcul non-standard. De exemplu, Leonard Adleman a arătat că problemele traseului hamiltonian ar putea fi rezolvate cu un computer ADN . Folosind paralelismul inerent reacțiilor chimice, problema poate fi rezolvată folosind mai multe etape ale reacțiilor chimice care depind liniar de numărul de vârfuri ale graficului. Totuși, acest lucru necesită un număr factorial de molecule de ADN implicate în reacție [9] .

Rezolvarea optică a problemei hamiltoniene a fost propusă de Oltean [10] . Ideea este de a crea o structură sub formă de grafic de cabluri optice și separatoare de fascicule, prin care se trece un fascicul pentru a rezolva problema. Punctul slab al acestei abordări este creșterea exponențială a energiei necesare din numărul de noduri.

Dificultate

Problema găsirii unui ciclu sau cale hamiltonian este FNP . O problemă similară de decidebilitate  este de a verifica dacă există un ciclu sau o cale hamiltoniană. Problemele ciclului hamiltonian dirijate și nedirecționate au fost două dintre cele 21 de probleme NP-complete ale lui Karp . Ele rămân NP-complete chiar și pentru grafurile plane nedirecționate de gradul maxim trei [11] , pentru grafurile plane direcționate cu semigrade de intrare și ieșire cel mult două [12] , pentru grafurile bipartite nedirecționate planare 3-regular fără punți, pentru 3-conectate. -grafice bipartite regulate [13] , subgrafe ale unei rețele pătrate [14] și pentru subgrafe cubi ale unei rețele pătrate [15] .

Totuși, graficele plane cu 4 conexiuni sunt întotdeauna hamiltoniene, conform rezultatului lui Tutt, iar problema găsirii unui ciclu hamiltonian în aceste grafice se poate face în timp liniar [16] prin calculul așa-numitei căi Tutt. Tutt a dovedit acest rezultat arătând că orice graf planar cu două conexiuni conține calea lui Tutt. Căile Tutt, la rândul lor, pot fi calculate în timp patratic chiar și pentru graficele plane cu două conexiuni [17] , care pot fi folosite pentru a găsi cicluri hamiltoniene și cicluri lungi în graficele planare generalizate.

Punând totul împreună, rămâne o întrebare deschisă dacă grafurile plane bipartite regulate cu 3 conexiuni trebuie să conțină întotdeauna un ciclu hamiltonian și, dacă da, problema mărginită de aceste grafice nu va fi NP-completă (vezi articolul „ Conjectura lui Barnett ").

În graficele în care toate vârfurile sunt de grad impar, argumentul lemei de strângere de mână arată că numărul de cicluri hamiltoniene printr-o muchie fixă ​​este întotdeauna par, astfel încât dacă este dat un ciclu hamiltonian, atunci trebuie să existe altul [18] . Cu toate acestea, găsirea acestui al doilea ciclu nu arată ca o simplă sarcină de calcul. Papadimitriou a definit clasa de complexitate PPA pentru a reuni probleme ca aceasta [19] .

Note

  1. ↑ Garey și Johnson 1979 , p. 199-200, A1.3: GT37 - 39.
  2. ↑ teoria graficelor - Reducerea de la ciclul hamiltonian la calea hamiltoniană - Mathematics Stack Exchange . Preluat la 18 februarie 2019. Arhivat din original la 23 aprilie 2019.
  3. ↑ Martello, 1983 , p. 131–138.
  4. ↑ Rubin, 1974 , p. 576–80.
  5. ↑ Bellman, 1962 , p. 61–63.
  6. ↑ Held, Karp, 1962 , p. 196–210.
  7. ↑ Björklund, 2010 , p. 173–182.
  8. ↑ Iwama, Nakashima, 2007 , p. 108–117.
  9. ↑ Adleman, 1994 , p. 1021–1024.
  10. ↑ Oltean, 2006 , p. 217–227.
  11. ↑ Garey, Johnson & Stockmeyer, 1974 , p. 47–63.
  12. ↑ Plesńik, 1979 , p. 199–201.
  13. ↑ Akiyama, Nishizeki, Saito, 1980-1981 , p. 73–76.
  14. ↑ Itai, Papadimitriou, Szwarcfiter, 1982 , p. 676–686.
  15. ↑ Buro, 2000 , p. 250–261.
  16. ↑ Chiba, Nisizeki, 1989 , p. 187–211.
  17. ↑ Schmid, Schmidt, 2018 .
  18. ↑ Thomason, 1978 , p. 259–268.
  19. ↑ Papadimitriou, 1994 , p. 498–532.

Literatură