Hamiltoni út probléma

A Hamilton-útprobléma és a Hamilton-ciklusprobléma  annak meghatározására szolgál, hogy van-e Hamilton-út vagy Hamilton-ciklus egy adott gráfban ( irányított vagy irányítatlan ). Mindkét probléma NP-teljes [1] .

A Hamilton-ösvény és a Hamilton-ciklus problémái közötti kapcsolat

Egyszerű kapcsolat van a Hamilton-ösvény megtalálásának és a Hamilton-ciklus megtalálásának problémái között. Az egyik irányban egy gráf Hamilton-útjának problémája ekvivalens a H gráf Hamilton-ciklusának problémájával, amelyet egy G gráfból kapunk úgy, hogy hozzáadunk egy új csúcsot és összekapcsoljuk a G gráf összes csúcsával. egy Hamilton-út nem lehet lényegesen lassabb (legrosszabb esetben , a csúcsok számának függvényében), mint egy Hamilton-ciklust keresni.

Ellenkező irányban a G gráf Hamilton-ciklusának problémája ekvivalens a G gráf egyik v csúcsának (v'-be) másolásával kapott Hamilton-út problémájával egy H gráfban, azaz a v csúcsban. ' ugyanaz lesz a szomszédságában, mint v, és hozzáadunk két elsőfokú segédcsúcsot, amelyek közül az egyik v-hez, a másik pedig v-hez kapcsolódik [2] .

A Hamilton-ciklusprobléma az utazó eladó probléma speciális esete is , amelyet úgy kapunk, hogy két pont közötti minden távolságot egyre állítjuk be, ha szomszédosak, és kettőt egyébként. Az utazó eladó feladat megoldása után ellenőrizze, hogy a teljes távolság egyenlő-e n-nel (ha igen, az útvonal Hamilton-ciklus, ha nincs Hamilton-ciklus, a legrövidebb út hosszabb lesz ennél az értéknél).

Algoritmusok

Vannak n ! különböző csúcssorozatok, amelyek egy adott, n csúcsú gráfban Hamilton-utak lehetnek (és ilyen sok van a teljes gráfban ), így az összes lehetséges sorozatot kipróbáló nyers erő algoritmus nagyon lassú lenne.

Egy korai egzakt algoritmus a Hamilton-ciklus megtalálására irányított gráfban a felsorolási algoritmus volt (Martello algoritmusa) [3] .

Frank Rubin [4] keresési eljárása három osztályba osztja a gráféleket – azokra, amelyeknek az útvonalon kell lenniük, azokra, amelyek nem tartozhatnak az útvonalhoz, és olyan élekre, amelyekről még nem született döntés. A keresés során egy döntési szabályrendszer osztályozza azokat az éleket, amelyekre vonatkozóan nem született döntés, és meghatározza, hogy a keresést leállítsák vagy folytassák. Az algoritmus a gráfot külön-külön feldolgozható komponensekre bontja.

A probléma időbeni megoldásához Bellman, Held és Karp dinamikus programozási algoritmusa használható . Ez a módszer minden S csúcshalmazra és S minden v csúcsára meghatározza , hogy van-e olyan út, amely áthalad S minden csúcsán és v pontban végződik . Minden ( S , v ) párhoz akkor és csak akkor létezik egy útvonal, ha v -nek van egy w szomszédos csúcsa , amelyhez van egy elérési út , amely a már megszerzett dinamikus programozási információból nyerhető [5] [6] .

Andreas Björklund alternatív megközelítést ad a befogadás/kizárás elvét alkalmazva az iterált Hamilton-ciklusok számának csökkentésére, és a ciklusszámlálási probléma megoldható valamely mátrix determinánsának kiszámításával.

Ezzel a módszerrel megmutatta, hogyan lehet időben megoldani a Hamilton-ciklusproblémát tetszőleges, n csúcsú gráfokhoz a Monte Carlo algoritmus segítségével . Bipartit gráfok esetében ez az algoritmus időig javítható [7] .

Maximum 3-as fokú gráfok esetén a pontos visszakövető keresés időben megtalálja a Hamilton-ciklust (ha van ilyen) [8] .

A Hamilton-pályák és ciklusok a SAT megoldó segítségével kereshetők meg .

A Hamilton-pálya- és ciklusproblémák közönséges számítógépeken történő megoldásának bonyolultsága miatt ezeket nem szabványos számítási modellekre tanulmányozták. Például Leonard Adleman megmutatta, hogy a Hamilton-pálya problémákat meg lehet oldani egy DNS-számítógéppel . A kémiai reakciókban rejlő párhuzamosságot felhasználva a probléma több kémiai reakciólépéssel is megoldható, amelyek lineárisan függenek a gráf csúcsainak számától. Ehhez azonban faktorszámú DNS-molekulára van szükség, amely részt vesz a reakcióban [9] .

A Hamilton-probléma optikai megoldását Oltean javasolta [10] . Az ötlet az, hogy optikai kábelekből és nyalábosztókból grafikonszerű struktúrát hozzanak létre, amelyen keresztül egy nyaláb fut át ​​a probléma megoldása érdekében. Ennek a megközelítésnek a gyenge pontja a szükséges energia exponenciális növekedése a csomópontok számától.

Nehézség

A Hamilton-féle ciklus vagy út megtalálásának problémája az FNP . Hasonló eldönthetőségi probléma  annak ellenőrzése, hogy van-e Hamilton-kör vagy út. Karp 21 NP-teljes problémája közül kettő volt az irányított és irányítatlan Hamilton-ciklusproblémák . NP-teljesek maradnak még a maximum 3-as fokú irányítatlan síkgráfoknál is [11] , irányított síkgráfoknál legfeljebb kettő bemeneti és kimeneti félfokkal [12] , irányítatlan síkbeli 3-reguláris bipartit gráfoknál hidak nélkül, 3 összekapcsolt 3 esetén -reguláris bipartit gráfok [13] , négyzetrács részgráfjai [14] és négyzetrács köbös részgráfjai [15] .

A 4 összekapcsolt síkgráfok azonban Tutt eredménye szerint mindig Hamilton-gráfok, és a Hamilton-ciklus megtalálásának problémája ezekben a gráfokban lineáris időben [16] megoldható az úgynevezett Tutt-útvonal kiszámításával. Tutt bizonyította ezt az eredményt azzal, hogy megmutatta, hogy bármely 2-kapcsolatú síkgráf tartalmazza Tutt útvonalát. A Tutt-pályák pedig másodfokú időben számíthatók még 2-összefüggésű síkgráfokra is [17] , amelyek segítségével általánosított síkgráfokban Hamilton-ciklusokat és hosszú ciklusokat találhatunk.

Mindent összevetve továbbra is nyitott kérdés marad, hogy a 3 összekapcsolt, 3 szabályos kétrészes síkgráfoknak mindig tartalmazniuk kell-e Hamilton-ciklust, és ha igen, akkor az ezen gráfok által határolt probléma nem lesz NP-teljes (lásd a " Barnett sejtései " című cikket ").

Azokban a gráfokban, amelyekben minden csúcs páratlan fokú, a kézfogási lemma argumentum azt mutatja, hogy a rögzített élen áthaladó Hamilton-ciklusok száma mindig páros, tehát ha egy Hamilton-ciklus adott, akkor léteznie kell egy másiknak [18] . Ennek a második ciklusnak a megtalálása azonban nem tűnik egyszerű számítási feladatnak. Papadimitriou meghatározta a PPA összetettségi osztályt , hogy összehozza az ehhez hasonló problémákat [19] .

Jegyzetek

  1. ↑ Garey és Johnson 1979 , p. 199-200, A1.3: GT37 - 39.
  2. ↑ gráfelmélet - Redukció a Hamilton-ciklusból a Hamilton-pályára - Matematika veremcsere . Letöltve: 2019. február 18. Az eredetiből archiválva : 2019. április 23.
  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 és 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, Nishizeki, 1989 , p. 187–211.
  17. ↑ Schmid, Schmidt, 2018 .
  18. ↑ Thomason, 1978 , p. 259–268.
  19. ↑ Papadimitriou, 1994 , p. 498–532.

Irodalom