Pad
Verkende knopen
Hamiltoncykel
Hamiltonpad

Modus

    Doel

    Meer over hamiltonpaden en hamiltoncykels

    Hamiltonpad-verkenner

    In 1857 bedacht William Rowan Hamilton een puzzel: loop over de ribben van een dodecaëder zodat je elk van zijn 20 hoekpunten precies één keer aandoet en eindigt waar je begon. Zo'n route heet nu een hamiltoncykel. Hij is makkelijk te controleren en in het algemeen moeilijk te vinden. Teken er zelf een na op Hamiltons dodecaëder, op een schaakbord of op een graaf die je tekent, of kijk hoe een backtracking-zoektocht er een najaagt, tel de doodlopende wegen waarin ze belandt en zie hoeveel een paar eenvoudige controles de zoektocht inkorten. Kies een graaf en een doel: een cykel die naar zijn begin terugkeert, of een pad. Natekenen: klik op een knoop om te beginnen en daarna telkens op een buur; stippellijnen tonen waar je heen kunt. Een klik op de laatste knoop, Terug of Ongedaan maken zet een stap terug, en Hint noemt een volgende stap die nog tot het einde leidt. Zoeken: met Start of Stap loopt een backtracking-zoektocht, die knopen aanhangt tot het vastloopt en dan terugkeert; rode streepjes tonen de terugstappen en de balken tellen de knopen per padlengte. Vóór de start kiest een klik op een knoop waar hij begint. De vakjes schakelen het snoeien in en uit, Vergelijken laat dezelfde zoektocht met en zonder lopen, en Alles tellen telt elke cykel of elk pad van een kleine graaf. Bewerken: klik om een knoop toe te voegen, klik op twee knopen om ze te verbinden of te scheiden, sleep om er een te verplaatsen, en Verwijderen haalt de gekozen knoop weg.

    Hoe het werkt

    1. Kies een graaf, zoals Hamiltons dodecaëder, de Petersen-graaf of een paardensprong, of teken je eigen graaf in Bewerken, en kies als doel een cykel of een pad.
    2. Klik in Natekenen op een knoop om te beginnen en daarna op de ene buur na de andere. Terug en Ongedaan maken zetten een stap terug, en Hint toont een volgende stap die nog tot het einde leidt.
    3. Druk in Zoeken op Start of Stap om backtracking naar een route te zien zoeken, schakel het snoeien in en uit, en druk op Vergelijken om te zien hoeveel knopen elke versie nodig heeft.

    Hamilton tegenover Euler

    Een eulerpad gebruikt elke kant één keer; een hamiltonpad bezoekt elke knoop één keer. Dat klinkt vergelijkbaar maar gedraagt zich heel anders. Of een samenhangende graaf een eulerpad heeft, wordt beslist door de knopen van oneven graad te tellen, zoals Euler in 1736 liet zien: hij heeft er een als er geen of twee zijn. Voor hamiltonpaden is zo'n regel niet bekend. Beslissen of een graaf een hamiltoncykel heeft is NP-volledig, een van de 21 problemen op de lijst van Richard Karp uit 1972, dus een snelle methode daarvoor zou snelle methoden geven voor duizenden andere moeilijke problemen. Wat er wel is, zijn voorwaarden die sommige grafen beslissen. De stelling van Dirac uit 1952 garandeert een hamiltoncykel als elke knoop graad minstens n/2 heeft, en die van Ore uit 1960 als twee niet-verbonden knopen altijd graden met som minstens n hebben; een knoop van graad 1, een snijknoop of twee kleurklassen van verschillende grootte sluiten er een uit.

    Hoe het zoeken werkt

    Backtracking bouwt het pad knoop voor knoop op en neemt, als het vastloopt, de laatste stap terug en probeert de volgende buur. Het vindt altijd een hamiltoncykel als die er is, maar het aantal deelpaden kan exponentieel groeien. Op het 5 × 5-rooster, dat geen hamiltoncykel heeft, verkent gewone backtracking 153.745 knopen voordat het zeker is. Twee controles stoppen kansloze paden vroeg: een onbezochte knoop met minder dan twee vrije buren past niet meer in een cykel, en als de onbezochte knopen in losse delen uiteenvallen, kan geen enkel pad ze dekken. Met beide kost hetzelfde bewijs 1.761 knopen. De regel van Warnsdorff uit 1823, die eerst de buur met de minste vervolgzetten probeert, vindt een paardensprong op 8 × 8 vanuit een hoek in 64 zetten zonder ook maar één doodlopende weg.

    Veelgestelde vragen

    Wat is het verschil tussen een hamiltonpad en een hamiltoncykel?

    Een hamiltonpad bezoekt elke knoop van een graaf precies één keer. Een hamiltoncykel doet hetzelfde en keert dan via één kant meer terug naar waar hij begon, dus hij kan bij elk van zijn knopen beginnen. Elke graaf met een hamiltoncykel heeft een hamiltonpad (laat één kant van de cykel weg), maar niet andersom: de Petersen-graaf heeft hamiltonpaden en geen hamiltoncykel.

    Heeft de dodecaëder een hamiltoncykel?

    Ja, 30 stuks, als je elke cykel één keer telt ongeacht begin en richting. Hamilton maakte er in 1857 het icosische spel van, een bord met de 20 hoekpunten van een platgeslagen dodecaëder gemerkt met medeklinkers, en verkocht de rechten voor 25 pond aan de Londense speelgoedmaker John Jaques and Son. Alles tellen vindt de 30 cykels in ongeveer 1.400 knopen.

    Waarom heeft een 5 × 5-rooster geen hamiltoncykel?

    Kleur de 25 punten als een schaakbord: 13 krijgen de ene kleur en 12 de andere, en elke stap gaat naar de andere kleur. Een cykel wisselt de kleuren de hele ronde door, dus hij heeft er van beide evenveel nodig, wat 13 en 12 niet geven. Hetzelfde argument geldt voor elk rooster met een oneven aantal punten, voor een paard op een 5 × 5- of 7 × 7-bord (een paard wisselt altijd van veldkleur) en voor de Herschel-graaf, waarvan de twee klassen 6 en 5 knopen hebben. Een hamiltonpad blijft mogelijk: het begint en eindigt op de grootste kleur.

    Hoe vindt de regel van Warnsdorff een paardensprong?

    H. C. von Warnsdorff stelde in 1823 voor het paard altijd naar het veld te zetten vanwaar het de minste vervolgzetten heeft. Velden bij de randen en hoeken, die makkelijk worden afgesneden, komen zo vroeg aan de beurt, zolang het paard er nog bij kan. De regel is een vuistregel, geen garantie, en gelijke gevallen moeten op de een of andere manier worden gebroken, maar op een 8 × 8-bord voltooit ze meestal een rondgang zonder terug te gaan. Samen met backtracking, zoals in deze app, vindt ze open rondgangen vanaf 5 × 5 en gesloten rondgangen op het 6 × 6- en het 8 × 8-bord.

    Hoeveel hamiltoncykels heeft een volledige graaf?

    (n − 1)!/2 voor n ≥ 3. Leg de beginknoop vast; de andere n − 1 kunnen in willekeurige volgorde volgen, en elke cykel wordt twee keer geteld, één keer per richting. K₆ heeft 5!/2 = 60 en K₁₀ heeft 181.440. Dat zijn de rondreizen waaruit een handelsreiziger moet kiezen, en daarom houdt het uitproberen van allemaal zo snel op mogelijk te zijn.

    Klaar om het te proberen?

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

    Ga naar Editor