Stel: je maakt op vakantie een rondreis door tien landen. Je wilt zo kort mogelijk onderweg zijn. In welke volgorde kun je de landen dan het beste bezoeken? Lees en puzzel mee met het Young Scientist Vakantieboek en maak kans op een gratis exemplaar!

Vakantieboek
Bestel het Young Scientist Vakantieboek in onze webshop!

De kortste route vinden langs een aantal landen of steden. Het lijkt simpel, maar wiskundigen breken zich al eeuwen het hoofd over wat ze het handelsreizigersprobleem noemen. Er is geen formule waarmee je simpel kunt uitrekenen wat de kortste route is. De enige manier is om computers een heleboel routes te laten uitrekenen en daaruit de kortste weg te kiezen.

In het Young Scientist Vakantieboek vind je een eenvoudigere versie van dit probleem, die je zonder computer kunt oplossen. Je maakt een reis langs alle tien de gebieden die in het boek staan beschreven. Je begint in Maastricht, op de grens van Nederland en België, en eindigt helemaal op Mars. Wat is de kortste route waarbij je elk gebied precies één keer bezoekt en elke stippellijn hooguit één keer volgt?

Gaan breinchips die onze gedachten koppelen aan machines de mens verbeteren?
LEES OOK

Gaan breinchips die onze gedachten koppelen aan machines de mens verbeteren?

Hersenimplantaten die mensen met een verlamming de mogelijkheid geven om computers te bedienen met hun gedachten, ontwikkelen zich snel.

puzzel vakantieboe
Klik op het plaatje voor een grotere versie.

Graaf

Je kunt de puzzel oplossen door allerlei routes vanaf Maastricht te proberen, totdat je de kortste hebt. Maar hoe weet je eigenlijk dat er een route is die langs alle steden gaat?

6n-graf.svg
Graaf met hamiltonpad.

Dat is een vraag die zelfs wiskundigen niet helemaal kunnen beantwoorden, maar ze kunnen je er wel bij helpen. Je kunt de routekaart zien als een netwerk van punten en lijnen. Wiskundigen zo’n netwerk een ‘graaf’. Een route die elk punt van de graaf precies één keer passeert, heet een Hamiltonpad.

220px-Tree_graph.svg
Graaf zonder Hamiltonpad.

Het is onmogelijk om meteen te weten of een graaf een Hamiltonpad heeft, maar je kunt het soms wel meteen zien als dat niet zo is. De graaf mag hooguit twee punten hebben met maar één lijn: het begin- en eindpunt van je reis. Bij de andere punten moeten minstens twee lijnen samenkomen. Je moet immers elke stad in, maar ook weer uit!

In onze reis door het Young Scientist Vakantieboek is Mars het enige gebied waar maar één lijn komt. Er zou dus een Hamiltonpad van Maastricht naar Mars kunnen zijn. Kun je nu een route vinden? Zo ja, bereken dan de totale lengte van die route met deze tabel:

Van Naar Afstand in kilometer
Nederland/België (Maastricht) Verenigd Koninkrijk (Londen) 412
Nederland/België (Maastricht) Frankrijk (Parijs) 326
Nederland/België (Maastricht) Duitsland (Berlijn) 670
Verenigd Koninkrijk (Londen) Frankrijk (Parijs) 343
Frankrijk (Parijs) Duitsland (Berlijn) 878
Frankrijk (Parijs) Zwitserland/Oostenrijk (Innsbruck) 695
Frankrijk (Parijs) Italië (Rome) 1105
Frankrijk (Parijs) Spanje/Portugal (Guarda) 1195
Duitsland (Berlijn) Zwitserland/Oostenrijk (Innsbruck) 602
Zwitserland/Oostenrijk (Innsbruck) Italië (Rome) 603
Zwitserland/Oostenrijk (Innsbruck) Griekenland (Athene) 1440
Italië (Rome) Griekenland (Athene) 1051
Italië (Rome) Antarctica (Station McMurdo) 15.850
Spanje/Portugal (Guarda) Antarctica (Station McMurdo) 15.856
Duitsland (Berlijn) Mars 55.000.000

Koningsbergen

Tot slot gaan we op zoek naar niet de kortste, maar de langste route tussen de tien gebieden. Je mag de steden nu meerdere keren bezoeken, maar nog steeds mag je elke stippellijn maar één keer volgen. Wat is de grootste afstand die je kunt afleggen? Is er een route waarbij je alle steden bezoekt?

Konigsberg_bridges
Kaart van Koningsbergen met de zeven bruggen.

Bij deze vraag kunnen wiskundigen gelukkig wel helpen. Al in het jaar 1736 bedacht Leonhard Euler een manier om te zien of een graaf een route heeft waarbij je elke lijn precies één keer passeert. Je moet dan kijken naar het aantal lijnen dat bij elk punt samenkomt, en of die aantallen even of oneven zijn. Als er nul of twee punten zijn met een oneven aantal lijnen, is er zo’n route (een Eulerpad). Als er één, drie of meer punten zijn met een oneven aantal lijnen, is er geen Eulerpad.

Königsberg_graph.svg
Graaf die de zeven bruggen van Koningsbergen laat zien.

Euler nam zelf als voorbeeld de stad Koningsbergen in Pruisen, een land dat niet meer bestaat. Koningsbergen had zeven bruggen. Je kunt de kaart van de stad voorstellen als een graaf met vier punten en zeven lijnen. Dan zie je meteen dat in elk punt drie lijnen bijeenkomen. Er is dus geen Eulerpad!

Kun je nu bedenken of er een route is van Maastricht naar Mars die langs alle stippellijnen loopt? Zo ja, welke route? En hoeveel kilometer leg je dan af?

Mail de kortste en de langste route inclusief het aantal kilometer naar info@newscientist.nl en maak kans op een gratis exemplaar van het Young Scientist Vakantieboek!

puzzel vakantieboe
Klik op het plaatje voor een grotere versie.

Altijd op de hoogte blijven van het laatste wetenschapsnieuws? Meld je nu aan voor de New Scientist nieuwsbrief.

Lees verder: