Hamiltonvägar och hamiltoncykler förklarade

Rita fem prickar i en ring, koppla varje till sina två grannar, och du kan gå runt genom varje prick en gång och komma hem: en hamiltoncykel. Lägg till några kanter eller ta bort några, och frågan blir förvånansvärt svår. Om en graf har en sådan cykel är ett av de mest kända problem som ingen dator ännu kan besvara snabbt för varje graf.

En utplattad dodekaeder med sina 20 hörn märkta med konsonanter och en hamiltoncykel genom dem alla ritad med en ljus linje, med en streckad röd kant där en sökning vände om
En utplattad dodekaeder med sina 20 hörn märkta med konsonanter och en hamiltoncykel genom dem alla ritad med en ljus linje, med en streckad röd kant där en sökning vände om

Varje nod en gång

En graf är en mängd punkter, noderna, sammanbundna av linjer, kanterna. En hamiltonväg går längs kanter och besöker varje nod exakt en gång; en hamiltoncykel återvänder dessutom dit den började, så den har lika många kanter som noder. En graf med en hamiltoncykel kallas hamiltonsk. Att kontrollera en föreslagen rutt är lätt: räkna noderna och se på varje steg. Att hitta en, eller visa att det inte finns någon, är den svåra delen, för antalet ordningar som noderna kan besökas i växer som n!, redan 2,4 × 10¹⁸ för 20 noder.

Hamiltons ikosiska spel

William Rowan Hamilton, den irländske matematiker som upptäckte kvaternionerna, uppfann det ikosiska spelet 1857. Brädan visade en dodekaeder utplattad i planet, med sina 20 hörn märkta med konsonanter, och huvuduppgiften var att sätta pinnar numrerade 1 till 20 på hörnen så att på varandra följande tal, och 20 och 1, är förbundna med kanter. Hamilton sålde rättigheterna för 25 pund till den Londonbaserade leksakstillverkaren John Jaques and Son, som gav ut det 1859; det sålde dåligt. Pusslet har 30 lösningar, om en cykel räknas en gång oavsett start och riktning. Frågan i sig var inte ny: Thomas Kirkman hade i en uppsats som sändes till Royal Society 1855 frågat vilka polyedrar som har en cykel genom alla sina hörn, och visat en som saknar sådan.

Springarrundturer

En springarrundtur flyttar en schackspringare så att den landar på varje ruta exakt en gång: en hamiltonväg i den graf vars noder är rutorna och vars kanter är springardragen. En sluten rundtur slutar ett springardrag från sin start, alltså en hamiltoncykel. Schackspelare ställde sådana uppgifter för mer än tusen år sedan, och Euler undersökte dem i en uppsats från 1759. År 1823 föreslog H. C. von Warnsdorff att alltid gå till rutan med minst fortsatta drag; denna enkla regel fullbordar oftast en rundtur på ett 8 × 8-bräde utan att gå tillbaka. En springare byter alltid rutfärg, så en sluten rundtur behöver lika många ljusa som mörka rutor, vilket utesluter bräden med ett udda antal rutor. Allen Schwenk visade 1991 exakt vilka rektangulära bräden som har en sluten rundtur; bland de kvadratiska har varje med en jämn sida om 6 eller mer det. Det vanliga schackbrädet har 13 267 364 410 532 slutna rundturer, räknade av Brendan McKay 1997.

Grafer utan hamiltoncykel

De snabbaste bevisen för att det inte finns någon cykel är räkneargument. Om noderna kan färgas med två färger så att varje kant kopplar ihop olika färger, växlar en cykel och behöver lika många noder av varje färg; ett rutnät 5 × 5 har 13 av den ena och 12 av den andra, så det har ingen hamiltoncykel. En artikulationsnod, vars borttagande delar grafen, skulle behöva passeras två gånger, och en nod med gradtal 1 kan inte passeras alls. Vissa grafer undgår alla sådana argument. Petersengrafen, publicerad av Julius Petersen 1898, har 10 noder med gradtal 3 och ingen hamiltoncykel, och ändå lämnar borttagandet av vilken nod som helst en graf som har en; den är den minsta sådana hypohamiltonska grafen. Herschelgrafen, uppkallad efter Alexander Stewart Herschel, som skrev om det ikosiska spelet 1862, har 11 noder och 18 kanter och är grafen för en polyeder med nio fyrsidiga ytor. Ingen polyeder med färre hörn saknar en hamiltoncykel. År 1884 förmodade Peter Guthrie Tait att varje polyeder med tre kanter i varje hörn har en; W. T. Tutte hittade 1946 ett motexempel med 46 noder.

Villkor som garanterar en

Har en graf många kanter är en hamiltoncykel säker. Gabriel Dirac bevisade 1952 att en graf med n ≥ 3 noder där varje nod har gradtal minst n/2 har en, och Øystein Ore försvagade villkoret 1960: det räcker att två noder som inte är ihopkopplade alltid har gradtal med summa minst n. Båda villkoren gäller bara åt ett håll. En enkel ring av 100 noder har överallt gradtal 2, långt under 50, och är ändå en hamiltoncykel. Så ser bilden ut i allmänhet: det finns tillräckliga villkor och det finns skäl till misslyckande, och däremellan ligger ett stort område av grafer som bara en sökning kan avgöra.

Varför inget snabbt test är känt

Att avgöra om en graf har en hamiltoncykel är NP-fullständigt; det var ett av de 21 problemen på Richard Karps lista från 1972. En metod som löste det snabbt för varje graf skulle lösa tusentals andra problem snabbt också och avgöra frågan P mot NP. Kontrasten mot eulervägar, som använder varje kant en gång, är slående: Euler visade 1736 att en räkning av noderna med udda gradtal avgör den frågan direkt. De bästa exakta metoderna för hamiltoncykler tar fortfarande exponentiell tid. Dynamisk programmering över alla delmängder av noder, funnen av Richard Bellman och av Michael Held och Richard Karp 1962, kräver omkring n² × 2ⁿ steg, och Andreas Björklunds randomiserade metod från 2010 omkring 1,657ⁿ. I praktiken klarar backtracking med god beskärning grafer med några tiotal noder, och handelsresandeproblemet, som söker den kortaste hamiltoncykeln, är den viktade versionen av samma fråga.

Gray-koder och hyperkuben

Skriv talen 0 till 7 som 3-bitarskoder och koppla ihop två koder när de skiljer sig på exakt en bit: resultatet är grafen för en kub. En hamiltoncykel genom den, till exempel 000, 001, 011, 010, 110, 111, 101, 100, räknar upp alla åtta koder så att varje skiljer sig från den föregående på en enda bit. En sådan lista är en Gray-kod, uppkallad efter Frank Gray vid Bell Labs, som beskrev den i ett patent inlämnat 1947. Varje hyperkub har en: skriv koderna med en bit färre, sedan samma lista baklänges, och sätt en 0 före den första halvan och en 1 före den andra. Vinkelgivare använder Gray-koder så att en avläsning mellan två lägen aldrig är mer än ett steg fel. Kuben har 6 hamiltoncykler och 4-bitarshyperkuben 1 344.

Utforska själv

Öppna hamiltonvägsutforskaren för att pröva Hamiltons pussel själv, med streckade ringar som visar vart du kan gå, eller byt till Sökning och se backtracking arbeta: vägen växer, röda streck markerar var den vänder om, och staplarna räknar noderna per väglängd. Slå på och av återvändsgrändskontrollen, sammanhangskontrollen och Warnsdorffs ordning, jämför hur många noder var och en behöver, räkna alla cykler i en liten graf, eller rita din egen graf och se vilka av snabbtesterna som gäller.

Ofta ställda frågor

Är en graf med en eulerkrets också hamiltonsk, eller tvärtom?

Ingetdera följer av det andra. Flugan, två trianglar med en gemensam nod, har en eulerkrets eftersom varje gradtal är jämnt, men ingen hamiltoncykel, eftersom den gemensamma noden skulle behöva passeras två gånger. Den fullständiga grafen K₄ har hamiltoncykler, men alla fyra noder har gradtal 3, så den har ingen eulerkrets.

Kan inte en dator bara pröva alla ordningar?

Bara för små grafer. Det finns n! ordningar av n noder, omkring 2,4 × 10¹⁸ för 20. Backtracking klarar det mycket bättre, eftersom den bara följer kanter och ger upp en delväg så snart den kör fast: den hittar alla 30 cykler i dodekaedern med 20 noder på omkring 1 400 steg. Men för vissa grafer växer antalet delvägar ändå exponentiellt, och ingen metod är känd som undviker detta för varje graf.

Är hamiltonvägsproblemet lättare än cykelproblemet?

Nej, båda är NP-fullständiga. Vart och ett kan översättas till det andra: lägg till en ny nod kopplad till varje gammal, och den gamla grafen har en hamiltonväg precis när den nya har en hamiltoncykel. Åt andra hållet blir ett cykelproblem ett vägproblem genom att lägga till en kopia av en nod, med samma grannar, och en ny ändnod kopplad till noden och en till kopian.

Varför måste en springarrundtur på ett 5 × 5-bräde börja på hörnfärgen?

Av de 25 rutorna har 13 hörnens färg och 12 den andra, och en springare byter färg vid varje drag. En rundtur över 25 rutor växlar färgerna, så den börjar och slutar på den färg som har flest rutor. Appen hittar alla 1 728 öppna rundturer på 5 × 5-brädet, 864 om en rundtur och dess omvändning räknas som en, och varje börjar och slutar på en ruta i hörnfärgen.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna hamiltonvägsutforskaren