eulergraaf

Een graaf bestaat uit ‘knopen’ die wel of niet verbonden zijn door ‘bogen’. De grafentheorie, ontstaan met de bruggen van Koningsbergen in de 18de eeuw, is nu overal aanwezig als wiskundig model voor het internet, sociale netwerken, routeplanners... en doet binnenkort ook haar intrede in de eindtermen wiskunde voor de tweede graad. We laten in deze loep zien hoe leerlingen met grafen (zullen) kunnen redeneren, puzzelen en bewijzen zonder veel voorkennis of algebraïsche hindernissen. Ze leren ook diverse situaties modelleren in een zelfde taal van knopen en bogen. Bij de meeste ‘echte’ toepassingen gaat het om reusachtige grafen en zijn er systematische algoritmen nodig om hierin bv. kortste wegen te vinden, of om alle knopen efficiënt met elkaar te verbinden. Exemplarisch laten we de leerlingen kennis maken met het algoritmisch denken dat hiervoor nodig is.

In de achttiende eeuw had de Russische stad Koningsbergen (vanaf 1946 omgedoopt tot Kaliningrad) gelegen aan de monding van de Pregel, zeven bruggen zoals te zien is op figuur 1. Het klassieke probleem van Koningsbergen verwijst naar deze bruggen. Dit probleem gaat als volgt: Is het mogelijk om een wandeling door Koningsbergen te maken, precies