Eulerpaden en eulercircuits uitgelegd

Sommige figuren zijn in één lijn te tekenen, zonder het potlood op te tillen en zonder een lijn dubbel te gaan, en andere niet, hoe lang u het ook probeert. Proberen hoeft niet: tel de lijnen bij elke hoek. Hebben hoogstens twee hoeken een oneven aantal lijnen, dan is de figuur te tekenen, en bij die hoeken moet de lijn beginnen en eindigen. Leonhard Euler vond deze regel in 1736 en legde er de grondslag mee voor de grafentheorie.

De zeven bruggen van Koningsbergen getekend als graaf: vier stukken land als knopen, alle vier met een oneven aantal bruggen, aan weerszijden van een rivier
De zeven bruggen van Koningsbergen getekend als graaf: vier stukken land als knopen, alle vier met een oneven aantal bruggen, aan weerszijden van een rivier

De zeven bruggen van Koningsbergen

De Pruisische stad Koningsbergen, nu Kaliningrad, lag aan beide oevers van de rivier de Pregel en op twee eilanden daarin, de Kneiphof en de Lomse. Zeven bruggen verbonden de vier delen: twee van de Kneiphof naar elke oever, één tussen de twee eilanden en één van de Lomse naar elke oever. De inwoners vroegen zich af of een wandeling elke brug precies één keer kon oversteken. Euler antwoordde in een verhandeling die hij in 1735 aan de academie in Sint-Petersburg voorlegde en die in 1741 werd gedrukt: dat kan niet. Zijn beslissende stap was alles weg te laten behalve de stadsdelen en de bruggen ertussen, en dat is precies wat een graaf doet: een knoop voor elk stuk land en een tak voor elke brug, met twee takken waar twee bruggen dezelfde plekken verbinden.

Portret van Leonhard Euler
Portret van Leonhard Euler
Portrait of Leonhard Euler
Portrait of Leonhard Euler

De graadregel

De graad van een knoop is het aantal takken dat erop uitkomt. Een lijn die door een knoop gaat, komt over een tak binnen en gaat over een andere naar buiten, dus gebruikt zij de takken van die knoop in paren. Alleen de eerste en de laatste knoop van de lijn kunnen een tak zonder partner houden. Een knoop met een oneven graad moet dus het begin of het einde van de lijn zijn. De Kneiphof had vijf bruggen en de andere drie delen elk drie: vier oneven knopen, twee te veel. In het algemeen heeft een samenhangende graaf een eulercircuit, een lijn die eindigt waar zij begon, als elke graad even is, en een eulerpad als precies twee graden oneven zijn, van de ene naar de andere. Het aantal oneven knopen is nooit één, of een ander oneven getal: elke tak telt 2 op bij de som van alle graden, dus die som is even. Ook dat zag Euler al, en het heet nu het handdruklemma.

Waarom de regel genoeg is

Euler liet zien dat een figuur met meer dan twee oneven knopen niet te tekenen is, en beweerde zonder bewijs dat elke andere samenhangende figuur dat wel is. Het bewijs kwam van Carl Hierholzer, een Duitse wiskundige die in 1871 jong stierf; zijn artikel verscheen in 1873. Begin bij een oneven knoop als die er is, anders waar u wilt, en loop over ongebruikte takken zolang het kan. Omdat elke andere knoop een even graad heeft, kunt u alleen bij de eindknoop vastlopen. Blijven er takken over, dan raken sommige de route die u al hebt, want de figuur is samenhangend. Loop vanaf zo'n knoop opnieuw tot u vastloopt, wat nu weer bij die knoop gebeurt, en voeg de lus daar in de route in. Herhaal tot er geen tak meer over is. Het bewijs is tegelijk het snelste algoritme: elke tak wordt een vast aantal keren bekeken.

Het algoritme van Fleury: verbrand uw bruggen niet

Een lijn kan ook op een figuur die wel te tekenen is stuklopen. Neem twee driehoeken die door één tak verbonden zijn en begin bij een hoek van de eerste: gaat u naar de tweede driehoek voordat de eerste klaar is, dan komt u nooit meer terug. De verbindende tak is een brug: hem weghalen splitst de figuur in tweeën. Het algoritme van Fleury uit 1883 geeft één regel: neem bij elke knoop een tak die geen brug is van de takken die nog over zijn, tenzij er geen andere is. Wie dat volgt, komt altijd klaar. Op brug testen kost tijd, dus het algoritme van Fleury is langzamer dan dat van Hierholzer, maar het is het algoritme dat u met een potlood kunt volgen, en de tip in de app gebruikt het.

Een figuur repareren

Een figuur met k oneven knopen vraagt k/2 lijnen. Om hem in één lijn te tekenen voegt u takken toe die oneven knopen twee aan twee verbinden: elke nieuwe tak maakt twee oneven knopen even. Met k/2 − 1 takken blijven er twee oneven knopen over en krijgt u een pad; met k/2 blijft er geen over en krijgt u een circuit. Eén extra brug in Koningsbergen, tussen twee willekeurige van de vier delen, had de wandeling mogelijk gemaakt, en twee hadden een rondje mogelijk gemaakt. De geschiedenis deed iets dergelijks: twee bruggen gingen in de Tweede Wereldoorlog verloren en twee werden vervangen door een moderne weg, en de vijf bruggen die nu op de oude plekken staan zijn elk één keer over te steken, van het ene eiland naar het andere.

De manieren tellen

Het huis van Sinterklaas, een vierkant met beide diagonalen en een dak, is de Duitse kinderversie van de puzzel: „Das ist das Haus vom Ni-ko-laus” heeft acht lettergrepen, één per streep. De twee onderhoeken zijn de enige oneven knopen, en vanuit elk ervan zijn er precies 44 manieren om hem te tekenen, samen 88. Voor gerichte grafen is er een formule voor het aantal eulercircuits, de BEST-stelling, genoemd naar de Bruijn, van Aardenne-Ehrenfest, Smith en Tutte. Voor gewone grafen is zo'n formule niet bekend, en tellen wordt in het algemeen als moeilijk beschouwd, dus telt de app kleine figuren door elke manier te proberen en stappen over te slaan die de figuur in tweeën zouden snijden.

Waar eulerpaden worden gebruikt

Een sneeuwschuiver, een veegwagen of een postbode wil elke straat één keer doen en terugkomen. Heeft elk kruispunt een even aantal straten, dan volstaat een eulercircuit; anders moeten sommige straten twee keer worden gereden, en de goedkoopste daarvoor kiezen is het Chinese-postbodeprobleem, in 1962 gesteld door Meigu Guan. Een pennenplotter of een lasersnijder wint tijd door zo veel mogelijk lijnen te trekken zonder op te tillen. Bij het sequencen van genomen worden miljoenen korte stukjes DNA aan elkaar gelegd door een eulerpad te zoeken in een De Bruijn-graaf, waarin elk stukje een tak is. En dezelfde regel vertelt welke lijntekeningen in een puzzelboekje het proberen waard zijn.

Zelf proberen

Open de eulerpad-zoeker om zelf twaalf figuren na te trekken, van Koningsbergen in 1736 en vandaag tot sterren, geneste vierkanten en een kubus, of teken uw eigen figuren met parallelle takken. De oneven knopen zijn gevuld, elke knoop toont zijn graad, en de graadregel onder de figuur zegt wat mogelijk is en welke takken de figuur zouden repareren. Loopt u vast, dan zegt de app of u bij de verkeerde knoop begon of te vroeg een brug overstak, en bij welke stap. Tip geeft een veilige tak, en Oplossen tekent de figuur met het algoritme van Fleury, met de brugtest erbij, of met dat van Hierholzer, met elke ingevoegde deelroute.

Veelgestelde vragen

Is een eulerpad hetzelfde als een hamiltonpad?

Nee. Een eulerpad gebruikt elke tak één keer en mag een knoop vaker bezoeken; een hamiltonpad bezoekt elke knoop één keer en hoeft niet elke tak te gebruiken. Of een graaf een eulerpad heeft, is meteen duidelijk door de oneven knopen te tellen, maar voor hamiltonpaden is geen snelle test bekend, en er een vinden is een van de klassieke moeilijke problemen van de informatica.

Geldt de graadregel ook als twee knopen door meer dan één tak verbonden zijn?

Ja. Elke tak telt mee voor de graad van beide uiteinden, of er nu nog een tak dezelfde twee knopen verbindt of niet. Koningsbergen is zo'n multigraaf, met twee bruggen van de Kneiphof naar elke oever. Een tak van een knoop naar zichzelf, een lus, telt 2 op bij zijn graad en verandert nooit of hij oneven is.

En bij eenrichtingsstraten?

In een gerichte graaf heeft elke tak een richting, en de regel vergelijkt de takken die een knoop in gaan met die er uit gaan. Er is een eulercircuit als bij elke knoop evenveel takken binnenkomen als er uitgaan en de takken samenhangen, en een eulerpad als één knoop één tak meer uit dan in heeft, één knoop één meer in dan uit, en alle andere in evenwicht zijn. Het pad loopt dan van de eerste naar de tweede.

Kan er een figuur met precies één oneven knoop bestaan?

Nee. De graden van alle knopen samen zijn twee keer het aantal takken, want elke tak heeft twee uiteinden. Die som is even, dus moet het aantal oneven graden erin ook even zijn: 0, 2, 4 enzovoort, nooit 1 of 3.

Klaar om het te proberen?

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

De eulerpad-zoeker openen