Hamiltons vägproblem

Inom det matematiska området för grafteorin är Hamiltons vägproblem och Hamiltons cykelproblem problem med att avgöra om en Hamiltonsk bana (en bana i en oriktad eller riktad graf som besöker varje vertex exakt en gång) eller en Hamiltonsk cykel finns i en given graf ( oavsett om det är riktat eller oriktat ). Båda problemen är NP-kompletta .

Hamiltonska cykelproblemet är ett specialfall av resandeförsäljarproblemet , som erhålls genom att ställa in avståndet mellan två städer till en om de ligger intill och två annars, och verifiera att den totala tillryggalagda sträckan är lika med n (i så fall är rutten en Hamilton-bana; om det inte finns någon Hamilton-bana blir den kortaste vägen längre).

Minskning mellan stigproblemet och cykelproblemet

Problemen med att hitta en Hamiltonsk väg och en Hamiltonsk cykel kan relateras till följande:

I en riktning kan det Hamiltonska vägproblemet för grafen G relateras till det Hamiltonska cykelproblemet i en graf H som erhålls från G genom att lägga till en ny universell vertex x , som kopplar x till alla hörn av G . Att hitta en Hamiltonsk väg kan alltså inte vara nämnvärt långsammare (i värsta fall som en funktion av antalet hörn) än att hitta en Hamiltonsk cykel.
I den andra riktningen är det Hamiltonska cykelproblemet för en graf G ekvivalent med det Hamiltonska vägproblemet i grafen H som erhålls genom att addera terminala ( grad -ett) hörn s och t anslutna till en vertex v av G och till v', en kluven kopia av v som ger v' samma grannskap som v . Hamiltonbanan i H som löper genom hörn $svx-\cdots -yv'-t$ motsvarar den Hamiltonska cykeln i G som löper genom $vx-\cdots -y(-v)$ .

Algoritmer

Det finns n ! olika sekvenser av hörn som kan vara Hamiltonska banor i en given n -vertex-graf (och finns i en komplett graf ), så en brute force-sökningsalgoritm som testar alla möjliga sekvenser skulle vara mycket långsam. En tidig exakt algoritm för att hitta en Hamiltonsk cykel på en riktad graf var Martellos uppräkningsalgoritm. En sökprocedur av Frank Rubin delar in grafens kanter i tre klasser: de som måste vara i banan, de som inte kan vara i banan och osäkra. När sökningen fortskrider klassificerar en uppsättning beslutsregler de obestämda kanterna och bestämmer om sökningen ska stoppas eller fortsätta. Algoritmen delar in grafen i komponenter som kan lösas separat. Dessutom kan en dynamisk programmeringsalgoritm av Bellman, Held och Karp användas för att lösa problemet i tid O( n ² 2 ⁿ ). I denna metod bestämmer man, för varje uppsättning S av hörn och varje hörn v i S , om det finns en väg som täcker exakt hörnen i S och slutar vid v . För varje val av S och v finns en väg för ( S , v ) om och endast om v har en granne w så att en väg finns för ( S − v , w ), som kan slås upp från redan beräknad information i det dynamiska programmet.

Andreas Björklund tillhandahöll ett alternativt tillvägagångssätt med användning av inklusions-exkluderingsprincipen för att reducera problemet med att räkna antalet Hamilton-cykler till ett enklare räkneproblem, att räkna cykelöverdrag, som kan lösas genom att beräkna vissa matrisdeterminanter. Med denna metod visade han hur man löser Hamiltons cykelproblem i godtyckliga n -vertexgrafer med en Monte Carlo-algoritm i tiden O(1,657 ⁿ ); för tvådelade grafer kan denna algoritm förbättras ytterligare till tiden o (1,415 ⁿ ).

För grafer med maximal grad tre kan en noggrann bakåtsökning hitta en Hamiltonsk cykel (om en sådan finns) i tiden O(1,251 ⁿ ).

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

På grund av svårigheten att lösa Hamiltons väg- och cykelproblem på konventionella datorer har de också studerats i okonventionella datormodeller. Leonard Adleman visade till exempel att Hamiltons vägproblem kan lösas med en DNA-dator . Genom att utnyttja parallellismen som är inneboende i kemiska reaktioner kan problemet lösas genom att använda ett antal kemiska reaktionssteg som är linjära i antalet hörn i grafen; det kräver dock ett faktoriellt antal DNA-molekyler för att delta i reaktionen.

En optisk lösning på Hamilton-problemet har också föreslagits. Tanken är att skapa en grafliknande struktur gjord av optiska kablar och stråldelare som korsas av ljus för att konstruera en lösning på problemet. Den svaga punkten med detta tillvägagångssätt är den erforderliga mängden energi som är exponentiell i antalet noder.

Komplexitet

Problemet med att hitta en Hamiltonsk cykel eller väg är i FNP ; det analoga beslutsproblemet är att testa om det finns en Hamiltonsk cykel eller bana. De riktade och oriktade Hamilton-cykelproblemen var två av Karps 21 NP-kompletta problem . De förblir NP-kompletta även för speciella typer av grafer, såsom:

tvådelade grafer ,
oriktade plana grafer av maximal grad tre,
riktade plana grafer med indegree och outdegree högst två,
brolösa oriktade plana 3- regelbundna tvådelade grafer ,
3-anslutna 3-regelbundna tvådelade grafer,
subgrafer av kvadratrutnätsgrafen ,
kubiska subgrafer av den kvadratiska rutnätsgrafen.

Men för vissa speciella klasser av grafer kan problemet lösas i polynomtid:

4-kopplade plana grafer är alltid Hamiltonska genom ett resultat på grund av Tutte , och beräkningsuppgiften att hitta en Hamiltonsk cykel i dessa grafer kan utföras i linjär tid genom att beräkna en så kallad Tutte-bana.
Tutte bevisade detta resultat genom att visa att varje 2-kopplad plan graf innehåller en Tutte-bana. Tuttebanor i sin tur kan beräknas i kvadratisk tid även för 2-kopplade plana grafer, som kan användas för att hitta Hamiltonska cykler och långa cykler i generaliseringar av plana grafer.

Om man sätter alla dessa villkor tillsammans, förblir det öppet om 3-kopplade 3-regelbundna tvådelade plana grafer alltid måste innehålla en Hamiltonsk cykel, i vilket fall problemet begränsat till dessa grafer inte kunde vara NP-komplett; se Barnettes gissning .

I grafer där alla hörn har udda grad, visar ett argument relaterat till handskakningslemma att antalet Hamilton-cykler genom en fast kant alltid är jämnt, så om en Hamilton-cykel ges, måste en andra också finnas. Att hitta denna andra cykel verkar dock inte vara en lätt beräkningsuppgift. Papadimitriou definierade komplexitetsklassen PPA för att kapsla in problem som detta.

Media relaterade till Hamiltons vägproblem på Wikimedia Commons