Hamiltonpaden en hamiltoncykels uitgelegd

Teken vijf punten in een kring, verbind elk met zijn twee buren, en je kunt rond door elk punt één keer lopen en thuiskomen: een hamiltoncykel. Voeg een paar kanten toe of haal er een paar weg en de vraag wordt verrassend moeilijk. Of een graaf zo'n cykel heeft, is een van de bekendste problemen die geen computer nog snel voor elke graaf kan beantwoorden.

Een platgeslagen dodecaëder met zijn 20 hoekpunten gemerkt met medeklinkers en één hamiltoncykel door alle hoekpunten in een heldere lijn, met een rode stippellijn waar een zoektocht terugkeerde
Een platgeslagen dodecaëder met zijn 20 hoekpunten gemerkt met medeklinkers en één hamiltoncykel door alle hoekpunten in een heldere lijn, met een rode stippellijn waar een zoektocht terugkeerde

Elke knoop één keer

Een graaf is een verzameling punten, de knopen, verbonden door lijnen, de kanten. Een hamiltonpad loopt over kanten en bezoekt elke knoop precies één keer; een hamiltoncykel keert bovendien terug naar waar hij begon, dus hij heeft evenveel kanten als knopen. Een graaf met een hamiltoncykel heet hamiltoniaans. Een voorgestelde route controleren is makkelijk: tel de knopen en bekijk elke stap. Er een vinden, of bewijzen dat er geen is, is het moeilijke deel, want het aantal volgordes waarin de knopen bezocht zouden kunnen worden groeit als n!, bij 20 knopen al 2,4 × 10¹⁸.

Hamiltons icosische spel

William Rowan Hamilton, de Ierse wiskundige die de quaternionen ontdekte, bedacht het icosische spel in 1857. Het bord toonde een in het vlak platgeslagen dodecaëder, met zijn 20 hoekpunten gemerkt door medeklinkers, en de hoofdopgave was pinnen met de nummers 1 tot 20 zo op de hoekpunten te zetten dat opeenvolgende nummers, en 20 en 1, door kanten verbonden zijn. Hamilton verkocht de rechten voor 25 pond aan de Londense speelgoedmaker John Jaques and Son, die het in 1859 uitbracht; het verkocht slecht. De puzzel heeft 30 oplossingen, als je een cykel één keer telt ongeacht begin en richting. De vraag zelf was niet nieuw: Thomas Kirkman had in een artikel dat hij in 1855 aan de Royal Society stuurde gevraagd welke veelvlakken een cykel door al hun hoekpunten hebben, en er een getoond dat die niet heeft.

Paardensprongen

Een paardensprong beweegt een schaakpaard zo dat het op elk veld precies één keer landt: een hamiltonpad in de graaf waarvan de knopen de velden zijn en de kanten de paardenzetten. Een gesloten rondgang eindigt op een paardensprong van het begin, dus een hamiltoncykel. Schakers stelden zulke opgaven ruim duizend jaar geleden al, en Euler bestudeerde ze in een artikel van 1759. In 1823 stelde H. C. von Warnsdorff voor altijd naar het veld met de minste vervolgzetten te gaan; deze eenvoudige regel voltooit meestal een rondgang over een 8 × 8-bord zonder terug te gaan. Een paard wisselt altijd van veldkleur, dus een gesloten rondgang heeft evenveel lichte als donkere velden nodig, wat borden met een oneven aantal velden uitsluit. Allen Schwenk toonde in 1991 precies aan welke rechthoekige borden een gesloten rondgang hebben; onder de vierkante elk bord met een even zijde van 6 of meer. Het gewone schaakbord heeft 13.267.364.410.532 gesloten rondgangen, in 1997 geteld door Brendan McKay.

Grafen zonder hamiltoncykel

De snelste bewijzen dat er geen cykel is, zijn telargumenten. Als de knopen met twee kleuren te kleuren zijn zodat elke kant verschillende kleuren verbindt, wisselt een cykel af en heeft hij van elke kleur evenveel knopen nodig; een 5 × 5-rooster heeft er 13 van de ene en 12 van de andere, dus het heeft geen hamiltoncykel. Een snijknoop, waarvan het weghalen de graaf opdeelt, zou twee keer gepasseerd moeten worden, en een knoop van graad 1 helemaal niet. Sommige grafen ontsnappen aan al zulke argumenten. De Petersen-graaf, in 1898 gepubliceerd door Julius Petersen, heeft 10 knopen van graad 3 en geen hamiltoncykel, en toch levert het weghalen van welke knoop ook een graaf op die er wel een heeft; het is de kleinste zulke hypohamiltoniaanse graaf. De Herschel-graaf, genoemd naar Alexander Stewart Herschel, die in 1862 over het icosische spel schreef, heeft 11 knopen en 18 kanten en is de graaf van een veelvlak met negen vierhoekige vlakken. Geen veelvlak met minder hoekpunten mist een hamiltoncykel. In 1884 vermoedde Peter Guthrie Tait dat elk veelvlak met drie ribben in elk hoekpunt er een heeft; W. T. Tutte vond in 1946 een tegenvoorbeeld met 46 knopen.

Voorwaarden die er een garanderen

Heeft een graaf veel kanten, dan is een hamiltoncykel zeker. Gabriel Dirac bewees in 1952 dat een graaf met n ≥ 3 knopen waarin elke knoop graad minstens n/2 heeft er een bezit, en Øystein Ore verzwakte de voorwaarde in 1960: het is genoeg dat twee niet-verbonden knopen altijd graden met som minstens n hebben. Beide voorwaarden gelden maar in één richting. Een eenvoudige ring van 100 knopen heeft overal graad 2, ver onder 50, en is toch een hamiltoncykel. Zo ziet het er in het algemeen uit: er zijn voldoende voorwaarden en er zijn redenen voor falen, en daartussen ligt een groot gebied van grafen waarover alleen een zoektocht kan beslissen.

Waarom geen snelle test bekend is

Beslissen of een graaf een hamiltoncykel heeft is NP-volledig; het was een van de 21 problemen op de lijst van Richard Karp uit 1972. Een methode die dit voor elke graaf snel oploste, zou duizenden andere problemen ook snel oplossen en de vraag P tegen NP beslechten. Het contrast met eulerpaden, die elke kant één keer gebruiken, is opvallend: Euler liet in 1736 zien dat het tellen van de knopen van oneven graad die vraag meteen beslecht. De beste exacte methoden voor hamiltoncykels kosten nog steeds exponentiële tijd. Dynamisch programmeren over alle deelverzamelingen van knopen, in 1962 gevonden door Richard Bellman en door Michael Held en Richard Karp, kost ongeveer n² × 2ⁿ stappen, en de gerandomiseerde methode van Andreas Björklund uit 2010 ongeveer 1,657ⁿ. In de praktijk behandelt backtracking met goed snoeien grafen van enkele tientallen knopen, en het handelsreizigersprobleem, dat de kortste hamiltoncykel zoekt, is de gewogen versie van dezelfde vraag.

Graycodes en de hyperkubus

Schrijf de getallen 0 tot 7 als codes van 3 bits en verbind twee codes als ze precies in één bit verschillen: het resultaat is de graaf van een kubus. Een hamiltoncykel erdoorheen, bijvoorbeeld 000, 001, 011, 010, 110, 111, 101, 100, somt alle acht codes zo op dat elke code in één enkele bit van de vorige verschilt. Zo'n lijst is een graycode, genoemd naar Frank Gray van Bell Labs, die hem beschreef in een in 1947 ingediend octrooi. Elke hyperkubus heeft er een: schrijf de codes met één bit minder, dan dezelfde lijst achterstevoren, en zet een 0 voor de eerste helft en een 1 voor de tweede. Draaigevers gebruiken graycodes zodat een aflezing tussen twee standen nooit meer dan één stap fout is. De kubus heeft 6 hamiltoncykels en de 4-bits hyperkubus 1.344.

Ga het zelf na

Open de hamiltonpad-verkenner om Hamiltons puzzel zelf te proberen, met stippelringen die tonen waar je heen kunt, of ga naar Zoeken en kijk hoe backtracking werkt: het pad groeit, rode streepjes markeren waar het terugkeert, en de balken tellen de knopen per padlengte. Schakel de doodlopende-weg-controle, de samenhangcontrole en de volgorde van Warnsdorff in en uit, vergelijk hoeveel knopen elke nodig heeft, tel alle cykels van een kleine graaf, of teken je eigen graaf en kijk welke van de snelle tests gelden.

Veelgestelde vragen

Is een graaf met een eulercircuit ook hamiltoniaans, of andersom?

Geen van beide volgt uit het andere. De vlinderdas, twee driehoeken met één gemeenschappelijke knoop, heeft een eulercircuit omdat elke graad even is, maar geen hamiltoncykel, omdat de gedeelde knoop twee keer gepasseerd zou moeten worden. De volledige graaf K₄ heeft hamiltoncykels, maar alle vier knopen hebben graad 3, dus hij heeft geen eulercircuit.

Kan een computer niet gewoon elke volgorde proberen?

Alleen bij kleine grafen. Er zijn n! volgordes van n knopen, bij 20 ongeveer 2,4 × 10¹⁸. Backtracking doet het veel beter, omdat het alleen kanten volgt en een deelpad opgeeft zodra het vastloopt: het vindt alle 30 cykels van de dodecaëder met 20 knopen in ongeveer 1.400 stappen. Maar bij sommige grafen groeit het aantal deelpaden toch exponentieel, en er is geen methode bekend die dit voor elke graaf vermijdt.

Is het hamiltonpad-probleem makkelijker dan het cykel-probleem?

Nee, beide zijn NP-volledig. Elk is in het andere om te zetten: voeg een nieuwe knoop toe die met elke oude verbonden is, en de oude graaf heeft precies dan een hamiltonpad als de nieuwe een hamiltoncykel heeft. Omgekeerd wordt een cykel-probleem een pad-probleem door een kopie van een knoop toe te voegen, met dezelfde buren, en een nieuwe eindknoop aan de knoop en nog een aan zijn kopie te hangen.

Waarom moet een paardensprong op een 5 × 5-bord op een hoekkleur beginnen?

Van de 25 velden hebben er 13 de kleur van de hoeken en 12 de andere, en een paard wisselt bij elke zet van kleur. Een rondgang over 25 velden wisselt de kleuren af, dus hij begint en eindigt op de kleur met de meeste velden. De app vindt alle 1.728 open rondgangen van het 5 × 5-bord, 864 als een rondgang en zijn omkering voor één tellen, en elke begint en eindigt op een veld in de hoekkleur.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Open de hamiltonpad-verkenner