Puzzel en win: vind de kortste route langs tien vakantielanden

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!

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?

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?

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.

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:

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?

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.

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!

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

Lees verder:

• Ga mee op reis met het Young Scientist Vakantieboek!
• Knijpen in een papje
• Hommels blijken efficiënte routeplanners