Hamiltons vägproblem

Det Hamiltonska vägproblemet och det Hamiltonska cykelproblemet  är problem med att avgöra om det finns en Hamiltonsk väg eller en Hamiltonsk cykel i en given graf ( riktad eller oriktad ). Båda problemen är NP-kompletta [1] .

Samband mellan problem på Hamiltons väg och Hamiltons cykel

Det finns ett enkelt förhållande mellan problemen med att hitta en Hamiltonsk väg och att hitta en Hamiltonsk cykel. I en riktning är problemet med en Hamiltonsk väg för en graf ekvivalent med problemet med en Hamiltonsk cykel i en graf H som erhålls från en graf G genom att lägga till en ny vertex och koppla den till alla hörn i grafen G. en Hamiltonsk bana kan inte vara betydligt långsammare (i värsta fall, , som en funktion av antalet hörn) än att leta efter en Hamiltonsk cykel.

I motsatt riktning är problemet med en Hamiltonsk cykel för en graf G ekvivalent med problemet med en Hamiltonsk bana i en graf H som erhålls genom att kopiera en vertex v av grafen G (till v'), det vill säga vertex v ' kommer att ha samma grannskap som v, och adderar två extra hörn av grad ett, varav den ena är kopplad till v och den andra till v' [2] .

Hamiltonska cykelproblemet är också ett specialfall av resandeförsäljarproblemet , som erhålls genom att sätta alla avstånd mellan två punkter till en om de ligger intill och två annars. Efter att ha löst problemet med resande försäljare, kontrollera att det totala avståndet är lika med n (i så fall är rutten en Hamiltonsk cykel, om det inte finns någon Hamiltonsk cykel blir den kortaste vägen längre än detta värde).

Algoritmer

Det finns n ! olika sekvenser av hörn, som kan vara Hamiltonska banor i en given graf med n hörn (och det finns så många i hela grafen ), så att en brute-force- algoritm som försöker alla möjliga sekvenser skulle vara mycket långsam.

En tidig exakt algoritm för att hitta en Hamiltonsk cykel i en riktad graf var uppräkningsalgoritmen (Martellos algoritm) [3] .

Sökproceduren för Frank Rubin [4] delar in grafkanterna i tre klasser - de som måste vara på banan, de som inte kan tillhöra banan och kanterna för vilka inget beslut har fattats. Under sökningen klassificerar en uppsättning beslutsregler de kanter för vilka inget beslut har fattats och bestämmer om sökningen ska stoppas eller fortsätta. Algoritmen delar upp grafen i komponenter som kan bearbetas separat.

För att lösa problemet i tid kan den dynamiska programmeringsalgoritmen för Bellman, Held och Karp användas . Denna metod bestämmer, för varje uppsättning S av hörn och varje hörn v av S , om det finns en väg som passerar genom alla hörn av S och slutar vid v . För varje par ( S , v ) existerar en väg om och endast om v har en angränsande vertex w så att det finns en väg för , som kan erhållas från den dynamiska programmeringsinformationen som redan erhållits [5] [6] .

Andreas Björklund ger ett alternativt tillvägagångssätt med användning av inkluderings-/exkluderingsprincipen för att minska antalet Hamiltonska cykler som itereras över, och cykelräkningsproblemet kan lösas genom att beräkna determinanten för någon matris.

Med denna metod visade han hur man löser Hamiltons cykelproblem för godtyckliga grafer med n hörn med Monte Carlo-algoritmen i tid . För tvådelade grafer kan denna algoritm förbättras fram till tiden [7] .

För grafer med maximal grad tre, kan en noggrann backtracking -sökning hitta en Hamiltonsk cykel (om en sådan finns) i tid [8] .

Hamiltonska stigar och cykler kan hittas med hjälp av SAT-lösaren .

På grund av komplexiteten i att lösa Hamiltons väg- och cykelproblem på vanliga datorer, studerades de för icke-standardiserade beräkningsmodeller. Leonard Adleman visade till exempel att Hamiltons vägproblem kunde lösas med en DNA-dator . Med hjälp av parallellismen som är inneboende i kemiska reaktioner kan problemet lösas med hjälp av flera steg av kemiska reaktioner som beror linjärt på antalet grafens hörn. Detta kräver dock ett faktoriellt antal DNA-molekyler som är involverade i reaktionen [9] .

Den optiska lösningen av Hamilton-problemet föreslogs av Oltean [10] . Tanken är att skapa en grafliknande struktur av optiska kablar och stråldelare, genom vilken en stråle körs för att lösa problemet. Den svaga punkten med detta tillvägagångssätt är den exponentiella tillväxten av den erforderliga energin från antalet noder.

Svårighet

Problemet med att hitta en Hamiltonsk cykel eller väg är FNP . Ett liknande avgörbarhetsproblem  är att kontrollera om det finns en Hamiltonsk cykel eller stig. Riktade och oriktade Hamiltonska cykelproblem var två av Karps 21 NP-kompletta problem . De förblir NP-kompletta även för oriktade plana grafer med maximal grad tre [11] , för riktade plana grafer med ingångs- och utgångshalvgrad högst två [12] , för oriktade plana 3-regelbundna tvådelade grafer utan bryggor, för 3-anslutna 3 -regelbundna tvådelade grafer [13] , subgrafer av ett kvadratiskt gitter [14] och för kubiska subgrafer av ett kvadratiskt gitter [15] .

4-kopplade plana grafer är dock alltid Hamiltonska, enligt Tutts resultat, och problemet med att hitta en Hamiltonsk cykel i dessa grafer kan göras i linjär tid [16] genom att beräkna den så kallade Tuttbanan. Tutt bevisade detta resultat genom att visa att vilken 2-kopplad plan graf som helst innehåller Tutts väg. Tuttbanor kan i sin tur beräknas i kvadratisk tid även för 2-kopplade plana grafer [17] , som kan användas för att hitta Hamiltonska cykler och långa cykler i generaliserade plana grafer.

Sammantaget förblir det en öppen fråga om 3-kopplade 3-regelbundna tvådelade plana grafer alltid måste innehålla en Hamiltonsk cykel, och i så fall kommer problemet som begränsas av dessa grafer inte att vara NP-komplett (se artikeln " Barnett's Conjecture ").

I grafer där alla hörn är av udda grad, visar handskakningslemmaargumentet att antalet Hamilton-cykler genom en fast kant alltid är jämnt, så att om en Hamilton-cykel är given, måste en annan existera [18] . Men att hitta denna andra cykel ser inte ut som en enkel beräkningsuppgift. Papadimitriou definierade komplexitetsklassen PPA för att sammanföra problem som denna [19] .

Anteckningar

  1. ↑ Garey och Johnson 1979 , sid. 199-200, A1.3: GT37 - 39.
  2. ↑ graf teori - Reduktion från Hamiltons cykel till Hamiltonsk väg - Matematik Stack Exchange . Hämtad 18 februari 2019. Arkiverad från originalet 23 april 2019.
  3. ↑ Martello, 1983 , sid. 131–138.
  4. ↑ Rubin, 1974 , sid. 576–80.
  5. ↑ Bellman, 1962 , sid. 61–63.
  6. ↑ Held, Karp, 1962 , sid. 196–210.
  7. ↑ Björklund, 2010 , sid. 173–182.
  8. ↑ Iwama, Nakashima, 2007 , sid. 108–117.
  9. ↑ Adleman, 1994 , sid. 1021–1024.
  10. ↑ Oltean, 2006 , sid. 217–227.
  11. ↑ Garey, Johnson & Stockmeyer, 1974 , sid. 47–63.
  12. ↑ Plesńik, 1979 , sid. 199–201.
  13. ↑ Akiyama, Nishizeki, Saito, 1980-1981 , sid. 73–76.
  14. ↑ Itai, Papadimitriou, Szwarcfiter, 1982 , sid. 676–686.
  15. ↑ Buro, 2000 , sid. 250–261.
  16. ↑ Chiba, Nishizeki, 1989 , sid. 187–211.
  17. ↑ Schmid, Schmidt, 2018 .
  18. ↑ Thomason, 1978 , sid. 259–268.
  19. ↑ Papadimitriou, 1994 , sid. 498–532.

Litteratur