| Sökning | Noder | Resultat |
|---|---|---|
| Enkel backtracking | – | – |
| Warnsdorffs ordning | – | – |
| Återvändsgränds- och sammanhangskontroll | – | – |
| Alla tre | – | – |
Hamiltonvägsutforskare
År 1857 uppfann William Rowan Hamilton ett pussel: vandra längs kanterna på en dodekaeder så att du passerar vart och ett av dess 20 hörn exakt en gång och slutar där du började. En sådan rutt kallas i dag en hamiltoncykel. Den är lätt att kontrollera och i allmänhet svår att hitta. Rita en själv på Hamiltons dodekaeder, på ett schackbräde eller på en graf du ritar, eller se en backtracking-sökning jaga en, räkna återvändsgränderna den hamnar i, och se hur mycket några enkla kontroller kortar sökningen. Välj en graf och ett mål: en cykel som återvänder till sin start, eller en väg. Rita: klicka på en nod för att börja och sedan på en granne i taget; streckade ringar visar vart du kan gå. Ett klick på den sista noden, Bakåt eller Ångra tar ett steg tillbaka, och Tips nämner ett nästa steg som fortfarande går att fullfölja. Sökning: med Kör eller Steg löper en backtracking-sökning, som lägger till noder tills den kör fast och sedan går tillbaka; röda streck visar återgångarna och staplarna räknar noderna per väglängd. Före starten väljer ett klick på en nod var den börjar. Rutorna slår på och av beskärningen, Jämför kör samma sökning med och utan, och Räkna alla räknar varje cykel eller väg i en liten graf. Redigera: klicka för att lägga till en nod, klicka på två noder för att koppla ihop eller skilja dem, dra för att flytta en, och Ta bort tar bort den valda noden.
Hur det fungerar
- Välj en graf, till exempel Hamiltons dodekaeder, Petersengrafen eller en springarrundtur, eller rita din egen under Redigera, och välj en cykel eller en väg som mål.
- Klicka under Rita på en nod för att börja och sedan på den ena grannen efter den andra. Bakåt och Ångra tar ett steg tillbaka, och Tips visar ett nästa steg som fortfarande går att fullfölja.
- Tryck under Sökning på Kör eller Steg för att se backtracking leta efter en rutt, slå på och av beskärningen, och tryck på Jämför för att se hur många noder varje variant behöver.
Hamilton mot Euler
En eulerväg använder varje kant en gång; en hamiltonväg besöker varje nod en gång. Det låter likartat men beter sig mycket olika. Om en sammanhängande graf har en eulerväg avgörs genom att räkna noderna med udda gradtal, som Euler visade 1736: den har en när det finns noll eller två. För hamiltonvägar känner man ingen sådan regel. Att avgöra om en graf har en hamiltoncykel är NP-fullständigt, ett av de 21 problemen på Richard Karps lista från 1972, så en snabb metod för det skulle ge snabba metoder för tusentals andra svåra problem. Vad som finns är villkor som avgör vissa grafer. Diracs sats från 1952 garanterar en hamiltoncykel när varje nod har gradtal minst n/2, och Ores från 1960 när två noder som inte är ihopkopplade alltid har gradtal med summa minst n; en nod med gradtal 1, en artikulationsnod eller två färgklasser av olika storlek utesluter en.
Så arbetar sökningen
Backtracking bygger vägen en nod i taget och tar, när den kör fast, tillbaka det sista steget och prövar nästa granne. Den hittar alltid en hamiltoncykel om det finns en, men antalet delvägar kan växa exponentiellt. På rutnätet 5 × 5, som inte har någon hamiltoncykel, utforskar enkel backtracking 153 745 noder innan den är säker. Två kontroller stoppar hopplösa vägar tidigt: en obesökt nod med färre än två lediga grannar får inte längre plats i en cykel, och när de obesökta noderna faller isär i skilda delar kan ingen enda väg täcka dem. Med båda tar samma bevis 1 761 noder. Warnsdorffs regel från 1823, som först prövar grannen med minst fortsatta drag, hittar en springarrundtur på 8 × 8 från ett hörn på 64 drag utan en enda återvändsgränd.
Ofta ställda frågor
Vad är skillnaden mellan en hamiltonväg och en hamiltoncykel?
En hamiltonväg besöker varje nod i en graf exakt en gång. En hamiltoncykel gör samma sak och återvänder sedan via en kant till där den började, så den kan börja i vilken som helst av sina noder. Varje graf med en hamiltoncykel har en hamiltonväg (utelämna en kant i cykeln), men inte tvärtom: Petersengrafen har hamiltonvägar och ingen hamiltoncykel.
Har dodekaedern en hamiltoncykel?
Ja, 30 stycken, om varje cykel räknas en gång oavsett start och riktning. Hamilton gjorde 1857 det ikosiska spelet av det, en bräda med de 20 hörnen av en utplattad dodekaeder märkta med konsonanter, och sålde rättigheterna för 25 pund till den Londonbaserade leksakstillverkaren John Jaques and Son. Räkna alla hittar de 30 cyklerna på omkring 1 400 noder.
Varför har ett rutnät 5 × 5 ingen hamiltoncykel?
Färga de 25 punkterna som ett schackbräde: 13 får den ena färgen och 12 den andra, och varje steg går till den andra färgen. En cykel växlar färg hela varvet, så den behöver lika många av vardera, vilket 13 och 12 inte ger. Samma argument gäller för varje rutnät med ett udda antal punkter, för en springare på ett 5 × 5- eller 7 × 7-bräde (en springare byter alltid rutfärg) och för Herschelgrafen, vars två klasser har 6 och 5 noder. En hamiltonväg är fortfarande möjlig: den börjar och slutar på den större färgen.
Hur hittar Warnsdorffs regel en springarrundtur?
H. C. von Warnsdorff föreslog 1823 att alltid flytta springaren till den ruta varifrån den har minst fortsatta drag. Rutor nära kanterna och hörnen, som lätt skärs av, besöks därmed tidigt, medan springaren fortfarande kommer åt dem. Regeln är en tumregel, inte en garanti, och lika fall måste brytas på något sätt, men på ett 8 × 8-bräde fullbordar den oftast en rundtur utan att gå tillbaka. Tillsammans med backtracking, som i den här appen, hittar den öppna rundturer från 5 × 5 och uppåt och slutna rundturer på 6 × 6- och 8 × 8-brädet.
Hur många hamiltoncykler har en fullständig graf?
(n − 1)!/2 för n ≥ 3. Håll startnoden fast; de övriga n − 1 kan följa i vilken ordning som helst, och varje cykel räknas två gånger, en gång per riktning. K₆ har 5!/2 = 60 och K₁₀ har 181 440. Det är de rundresor en handelsresande måste välja mellan, och därför upphör det så snabbt att vara möjligt att pröva dem alla.
Redo att prova det?
Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.
Gå till Editor