Hoe vervoer je circusdieren zonder dat ze elkaar opeten?
Hoe werkt een navigatiesysteem?
Hoe vind je de beste route door een pretpark?
En hoe verhuis je al het geld van Dagobert Duck?
Dit zijn geen alledaagse vragen. Ze lijken misschien lastig om te beantwoorden. Deze problemen zijn echter goed op te lossen met grafen. Daar worden geen edellieden mee bedoeld, of een manier om een kuil te maken (dat schrijf je dan ook anders). Het gaat om wiskundige grafen. Zoals wel vaker in de wiskunde versimpelt een graaf een moeilijk probleem en worden alle overbodige details achterwege gelaten.
In dit Wisschrift ga je leren wat een graaf is en wat je er allemaal mee kunt doen. En natuurlijk krijg je ook de antwoorden op alle bovenstaande vragen.
Auteurs: Mignon Engel en Joris Rigter
Voorbeeldopdrachten
Een wandeling door het pretpark. De kronkels in de paden zijn maar verwarrend. Er is een plattegrond te maken waar wel alle belangrijke gegevens op staan, maar waarbij verder zoveel mogelijk onnodige details zijn weggelaten. Deze plattegrond noemen we een graaf. De attracties vormen de punten van de graaf.
Een voorbeeld van een graaf.
Manus Brulboei is een bekende zanger van levensliederen. Hij moet het hele land door om optredens te geven. Met een graaf kun je hem helpen de kortste weg te vinden ban bijvoorbeeld Rotterdam naar Groningen.
Hoeveel paardensprongen zijn er nodig om de witte en de zwarte paarden op het bord van plaats te laten wisselen? Je kunt dit oplossen door te probere, maar ook door een graaf te maken.