Eulerroutes

© h.hofstede (h.hofstede@hogeland.nl)

Routes in een Graaf.

Een route (ook wel pad genoemd) in een graaf is....... nou eigenlijk precies wat je je erbij voor zou stellen! Als de knooppunten steden zijn en de verbindingslijnen de wegen ertussen, dan is een route precies wat je je in het dagelijks leven ook als route voor zou stellen. Alleen is er één voorwaarde: elke verbindingslijn mag maar één keer voorkomen in een route (Als dat niet zo is, dan spreken we van een wandeling)

Wiskundig gezien is dat trouwens een waardeloze prut-uitleg.

Oké dan... ik ben er niet een erg grote voorstander van, maar laat ik voor één keer maar eens een formele wiskundige aanpak gebruiken. Daar komt íe.... (voor het gemak ga ik even uit van een ongerichte graaf).

Een ongerichte graaf bestaat uit een eindige verzameling K plus een verzameling V bestaande uit deelverzamelingen van twee elementen van K.

Heb je het door? Die verzameling K zijn de knooppunten, en die verzameling V zijn de verbindingslijnen.

Het graafje in het voorbeeld hiernaast is weer te geven door:
K = {a, b, c, d} V = {(a, c), (a, b), (b, c), (c, d)}

Een route is dan een geordende serie elementen uit V waarvoor geldt dat twee opeenvolgende elementen steeds een zelfde knooppunt bevatten, en waarin elk element hoogstens één keer voorkomt.
In de graaf hiernaast zou je de route (d, c)(c, a)(a, b)(b, c) kunnen maken.

Nou goed, snel terug naar de normale wereld.

Eerst nog even een paar termen:

•

de lengte van een route is het aantal knooppunten dat er in voorkomt.

•

een cykel is een route met hetzelfde beginpunt als eindpunt (heet ook wel "circuit" of "gesloten pad")

•

een graaf is samenhangend als er vanuit elk knooppunt een route bestaat naar elk ander knooppunt.

•

een Eulerroute is een route waarin elke verbindingslijn van de graaf precies één keer voorkomt.

•

een Eulercykel is een gesloten Eulerroute (dus met hetzelfde begin- en eindpunt).

De Eulerroutes/cykels gaan we eerst maar eens nader onderzoeken.....

Eulerroutes.

Eulerroutes, die ken je misschien al wel!

Kijk maar naar het huisje met het kruis erin hiernaast. De vraag daarbij is "Kun je dit tekenen zonder je potlood van papier te halen waarbij elke lijn precies één keer getrokken wordt?"

Zo'n route, waarbij dus elke verbindingslijn precies één keer gebruikt wordt, heet een Eulerroute.

Bij het huisje hiernaast kan dat inderdaad (click er maar op....) op meerdere manieren.

Nou kun je heel snel beredeneren of het mogelijk is zo'n route te vinden door het volgende te bedenken:

"elke keer dat je een knooppunt passeert voegt dat
twee nieuwe verbindingslijnen aan het knooppunt toe"

Logisch toch? Je bent via de ene lijn bij het knooppunt aangekomen en vertrekt via de andere weer. Dat zijn dus bij elke passage twee lijnen extra. Maar dat betekent dat bij alle knooppunten een EVEN AANTAL verbindingslijnen moeten samenkomen (dus dat alle knooppunten een even graad moet hebben).

Alle?......

Nou, er zijn twee uitzonderingen. Het punt waar je bent begonnen en het punt waar je eindigt hebben een oneven aantal verbindingslijnen, immers daar ben je één keer begonnen (of geëindigd) en verder gaf elke doorkomst twee extra lijnen.
Dus voor het bestaan van een Eulerroute mogen er precies twee knooppunten oneven graad hebben, de rest moet even graad hebben. Die twee met oneven graad zijn dan meteen beginpunt en eindpunt van de route.

Voor een Eulercykel heeft ook het begin/eindpunt een even graad: je bent er begonnen + geëindigd, en elke andere doorkomst gaf twee verbindingslijnen extra.
Een graaf met een Eulercykel heet een Eulergraaf.

Een samenhangende graaf is een Eulergraaf als alle knooppunten een even graad hebben.

Ik hoop dat je nu inziet dat ik dat strikt genomen nog niet bewezen heb. Ik heb alleen nog maar laten zien dat deze voorwaarde NODIG is voor het bestaan van een Eulercykel. Nog niet DAT die cykel dan ook altijd bestaat...... (Dus dat die voorwaarde ook VOLDOENDE is).

(Verder moest de graaf natuurlijk samenhangend zijn omdat anders zeker niet alle punten zijn te bereiken.)

Overigens kwam Euler op het idee dankzij zijn wekelijkse wandelingen door Königsberg.

Hiernaast kun je daar meer over lezen....

Het Fleury- Algoritme.

Het Fleury-algoritme is een manier om, als aan één van beide voorwaarden van hierboven is voldaan, ook daadwerkelijk zo'n Euler-route/cykel te maken.

De regels voor het maken van zo'n route zijn als volgt:

Kies een beginpunt, rekening houdend met de graad van de knooppunten (zoals hierboven omschreven, dus beginnen bij één van beide oneven punten als die er zijn).

Kies vanaf dat punt een willekeurige verbindingslijn naar een volgend punt, waarbij je op één voorwaarde moet letten:

de graaf moet samenhangend blijven als deze verbindingslijn verdwijnt

(In vaktermen: je mag geen lijnsnede van de overblijvende graaf kiezen)

Verwijder de gekozen verbindingslijn, en ga vanaf het nieuwe knooppunt weer naar stap 2.

Nou, dat levert zeker een Eulerroute op!
Hier heb je een voorbeeldje van hoe het werkt.

Het Fleury-algoritme werkt prima, maar het heeft een groot nadeel. Je kunt je voorstellen dat we graag een computerprogramma zouden schrijven om zo'n Eulerroute te vinden. Bij erg grote grafen is het met de hand namelijk nogal veel werk.....
Maar een computer heeft veel moeite om te ontdekken/berekenen wanneer een graaf nou samenhangend blijft en wanneer niet! Daar is ook wel weer een algoritme voor (Tarjan's algoritme), maar om dat elke keer toe te moeten passen kost nogal veel tijd....
Er is een betere oplossing:

Het Hierholzer-Algoritme.

Het Hierholzer algoritme werkt wat sneller.
Het gaat als volgt:

Kies een begin-knooppunt (volgens de regels van even/oneven hierboven) en maak een willekeurig rondje (cykel) langs een aantal ander knooppunten. (Dat lukt altijd want de knooppunten hebben allemaal even graad).

Kies nu vanaf een knooppunt van dit rondje waar nog ongebruikte verbindingslijnen aan zitten weer een nieuw rondje (dat lukt ook, want de overgebleven knooppunten hebben even graad).
Voeg dit rondje toe aan het vorige ("Insert")

Herhaal stap 2 tot er geen ongebruikte verbindingslijnen meer zijn.

Een voorbeeldje met dezelfde graaf:

OPGAVEN

Vijf Kamer Puzzel

Hier zie je een plattegrond van 5 kamers met 16 deuren.
Kun je een wandeling maken waarbij je elke deur precies één keer passeert?

Als dat zo is, laat dan zo'n wandeling zien.
Als dat niet zo is, toon dan aan waarom dat niet kan.

Hier zijn er nog drie.
Leg van de figuren waar geen wandeling mogelijk is uit, welke deur je zou kunnen dichtmetselen zodat er wel een wandeling mogelijk wordt.

Als alle knooppunten van een graaf graad minstens 2 hebben dan bevat die graaf een cykel.
Toon dat aan.

Hieronder zie je alle dominostenen met alle nummers van (0,0) tot en met (6,6)

Bij domino mogen stenen aan elkaar liggen als aangrenzende vlakken hetzelfde aantal ogen hebben.
Kun je één lange rij van al deze dominostenen maken?