In één lijn
Oneven knopen
Getrokken takken
Manieren om hem te trekken

    • 0 oneven knopen: een circuit, van elke knoop terug naar die knoop
    • 2 oneven knopen: een pad van de ene naar de andere
    • 4 of meer: onmogelijk in één lijn

    Methode

    Meer over eulerpaden en eulercircuits

    Eulerpad-zoeker

    Kunt u het huis van Sinterklaas tekenen zonder uw potlood op te tillen en zonder een lijn dubbel te gaan? Dat kan, maar alleen als u in een van de twee onderhoeken begint, en vanuit elk daarvan zijn er 44 manieren. De reden is de graad van een knoop, het aantal lijnen dat daar samenkomt: telkens als het potlood door een knoop gaat, gebruikt het er twee van zijn lijnen. Leonhard Euler vond deze regel in 1736 met de zeven bruggen van Koningsbergen. Trek zelf een figuur na, zie waar u vastloopt en waarom, vraag een tip, of kijk hoe een algoritme hem tekent. Kies een figuur en trek hem na: tik op een knoop om te beginnen en daarna op de takken of de volgende knopen op volgorde, of sleep van knoop naar knoop. Elke tak mag maar één keer. Terug neemt een stap terug, Tip toont de volgende veilige tak en Oplossen speelt het algoritme van Fleury of dat van Hierholzer stap voor stap af. Oneven knopen zijn gevuld en het bolletje bij elke knoop is zijn graad. Onder Tekenen voegt een tik op een lege plek een knoop toe en verbindt een tik op twee knopen ze, nog een keer voor een tweede tak; sleep een knoop om hem te verplaatsen. Wissen verwijdert knopen en takken. Zijn meer dan twee knopen oneven, dan zet Toevoegen de takken erbij waarmee de figuur wel te trekken is.

    Hoe het werkt

    1. Kies een figuur, zoals de zeven bruggen van Koningsbergen, het huis van Sinterklaas of een ster, of teken onder Tekenen uw eigen figuur, met zo veel takken tussen twee knopen als u wilt.
    2. Tik op een knoop om te beginnen en daarna op de takken of knopen op volgorde, of sleep van knoop naar knoop. Loopt u vast, dan zegt de statusregel waarom; Terug neemt een stap terug en Tip toont een veilige tak.
    3. Lees de graadregel onder de figuur, voeg aan een onmogelijke figuur de voorgestelde takken toe, of druk op Oplossen om het algoritme van Fleury of dat van Hierholzer hem stap voor stap te zien tekenen.

    Waarom de oneven knopen beslissen

    Een lijn die door een knoop gaat, komt over de ene lijn binnen en gaat over de andere verder, dus gebruikt zij de lijnen bij die knoop twee aan twee. Alleen waar de lijn begint of eindigt kan er een lijn zonder partner overblijven. Een knoop met een oneven aantal lijnen moet dus het begin of het einde zijn. Zonder oneven knoop eindigt de lijn waar zij begon: een eulercircuit. Met twee loopt zij van de ene naar de andere: een eulerpad. Met vier of meer zijn er te veel uiteinden voor één lijn, en k oneven knopen vragen k/2 lijnen. Koningsbergen had vier stukken land, met vijf, drie, drie en drie bruggen: alle vier oneven, dus geen wandeling kon elke brug één keer oversteken. Eén nieuwe brug tussen twee ervan had de wandeling mogelijk gemaakt.

    De algoritmen van Fleury en Hierholzer

    Weten dat een figuur te tekenen is, is niet hetzelfde als hem tekenen: een onvoorzichtige lijn kan zichzelf afsnijden van de lijnen die zij nog nodig heeft. Het algoritme van Fleury uit 1883 voorkomt dat met één regel: steek nooit een brug over, een lijn waarvan het weghalen de overgebleven lijnen in twee stukken zou splitsen, tenzij er geen andere lijn is. Het algoritme van Hierholzer, uit een artikel dat in 1873 verscheen, is sneller: loop waarheen u wilt tot u vastloopt, wat alleen bij de start kan gebeuren, en loop dan vanaf een knoop op de route die nog vrije lijnen heeft nog een gesloten lus, en voeg die in de route in. De tijd groeit evenredig met het aantal takken, en zo vinden computers eulerpaden.

    Veelgestelde vragen

    Wat is het verschil tussen een eulerpad en een eulercircuit?

    Allebei gebruiken ze elke tak van een graaf precies één keer. Een eulercircuit eindigt waar het begon; een eulerpad eindigt ergens anders. Een samenhangende graaf heeft een circuit als elke knoop een even graad heeft, en een pad als precies twee knopen een oneven graad hebben; het pad loopt dan van de ene naar de andere.

    Waarom kunnen de zeven bruggen van Koningsbergen niet elk één keer worden overgestoken?

    Teken elk stuk land als een knoop en elke brug als een tak. Het eiland Kneiphof had vijf bruggen en de andere drie stukken land elk drie, dus alle vier de knopen zijn oneven. Een wandeling kan alleen bij een oneven knoop beginnen of eindigen, en vier zijn er te veel. Eén extra brug tussen twee ervan laat twee oneven knopen over, en de wandeling wordt mogelijk.

    Op hoeveel manieren kun je het huis van Sinterklaas tekenen?

    44 vanuit elk van de twee onderhoeken, samen 88, als een andere volgorde of richting als een andere manier telt. Vanuit elke andere knoop lukt het niet, omdat de onderhoeken de enige twee met een oneven aantal lijnen zijn. De app telt de manieren van kleine figuren op deze wijze.

    Wat is een brug in een graaf?

    Een tak waarvan het weghalen een samenhangende graaf in twee stukken splitst. Het algoritme van Fleury steekt nooit een brug van de overgebleven takken over zolang het een andere keuze heeft, want dan zou een deel van de figuur achterblijven. In deze app krijgt een lijn die vastloopt na een te vroeg overgestoken brug te horen welke stap dat was.

    Kunnen er meer takken tussen twee knopen lopen?

    Ja. Een graaf met parallelle takken heet een multigraaf, en Koningsbergen heeft er een nodig: twee bruggen verbonden de Kneiphof met elke oever. Tik onder Tekenen nog eens op twee knopen om er nog een tak tussen te zetten, tot vier. De graadregel werkt precies zo en telt elke tak mee.

    Klaar om het te proberen?

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

    Ga naar Editor