Opinion

Grafentheorie voor dummies

Grafen, ofwel netwerken, vormen een hoekje van de wiskunde waar het stikt van de toepassingen. Peter Higgins is erin geslaagd een toegankelijke en behoorlijk diepgaande inleiding in het vakgebied te schrijven.

Een boek over grafen kan natuurlijk niet zonder de vermaarde Koningsberger bruggen. Kon Immanuel Kant, de beroemde filosoof die dagelijks klokke vier een wandelingetje ging maken, alle bruggen van de stad precies één keer aandoen? De intuïtie zei van niet, maar het was een Zwitser, Leonhard Euler, die het wiskundige bewijs leverde dat zulks onmogelijk was en daarmee een van de grondleggers van de grafentheorie werd, ofwel de wiskunde die zich bezighoudt met knooppunten en verbindingen daartussen.

Peter Higgins, hoogleraar wiskunde aan de Universiteit van Essex en uitvinder van de cirkelsudoku, pakt het degelijk en tegelijkertijd speels aan. Zijn boek ‘Nets, puzzles and postmen’ is opgebouwd in min of meer dezelfde hoofdstukken zoals je in een studieboek verwachten zou, maar hij brengt de theorie met meer flair aan de hand van voorbeelden. Het is een bekend trucje: waar een lesboek de abstracte theorie presenteert en dan een bekend voorbeeld geeft ter illustratie, redeneert de popularisator vanuit het voorbeeld naar de theorie toe. Het vakmanschap van Higgins maakt dat de overgang zo goed als ongemerkt gaat.

Zo zit je te lezen over de wandelingetjes van Kant, zo zijn de eilanden in de rivier geabstraheerd naar I1 en I2, en krijg je het bewijs van Euler voor de kiezen. Nee, dat is geen moeilijke wiskunde, althans niet als je aan een TU gearriveerd bent, maar dan zit je ook pas in het inleidende hoofdstuk. Tien pagina’s verderop gaat het over Hamilton-cycli: kun je een wandeling maken waarbij je alle knooppunten eenmaal aandoet? Die vraag is al heel wat moeilijker te beantwoorden dan het bruggenprobleem, waarbij je alle verbindingen maar een keer mag aandoen.

De volgende stap is het vier-kleurenprobleem: is het mogelijk een willekeurige wereldkaart in te kleuren met vier kleuren, zodanig dat geen landen met dezelfde kleur een gemeenschappelijke grens hebben? Wanneer je ieder land als een knooppunt ziet en een grens als een verbinding, wordt dit probleem ook een graaf, maar dan wel eentje met beperkingen. Zo gaat het steeds verder: telkens een nieuwe eigenschap aan de graaf toevoegen en de wiskundige gevolgen ervan uit de doeken doen.

Dan komt de postbode uit de titel. Die moet in een gegeven netwerk ten minste alle verbindingen (straten) aandoen. Een route vinden is niet zo’n kunst, maar wat is de meest efficiënte? En wat als hij met de auto is en sommige straten eenrichtingverkeer kennen? De volgende stap is dat niet iedere verbinding gelijkwaardig is. Sommige straten zijn nu eenmaal langer dan andere, dus de postbode wil die in elk geval niet twee keer hoeven doen. De vraag dringt zich op wat de kortste route is.

Hier gaat het boek rap in de richting van het zogeheten P-NP probleem. Dit is een van de grootste openstaande vragen van de hedendaagse wiskunde. Wie het oplost kan er een miljoen dollar mee verdienen. Hoe groter het netwerk, hoe ingewikkelder het wordt om de kortste route te berekenen. Het aantal potentiële oplossingen groeit namelijk exponentieel met elke extra straat. De methode om de vraag op te lossen hoeft echter niet per se exponentieel mee te groeien. Maar hoe snel dan wel? Die vraag is niet opgelost . maar wel heel relevant, bijvoorbeeld om internetverkeer efficiënt te routeren.

Higgins praat het allemaal met gemak aan elkaar, terwijl hij tegen het einde toch bij wiskunde is aangeland die het middelbare-schoolniveau ontstijgt. Een ware vondst is het laatste hoofdstuk ‘For connoisseurs’. Daarin loopt Higgins alle onderwerpen nog eens langs en geeft wiskundige verdieping, formules op universitair niveau niet schuwend. Welbeschouwd doet hij hier hetzelfde wat andere auteurs met een of meer appendices oplossen, maar door de toevoegingen kort te houden en ze samen ‘hoofdstuk’ te noemen, betrekt hij ze toch meer bij het boek. Een simpel trucje, maar het werkt wel.

Samenvattend: Peter Higgins heeft een boek over grafen geschreven dat zich op drie niveaus laat lezen. Er zijn leuke raadsels voor liefhebbers, gevolgd door uitleg die overgeslagen kan worden door degenen die het graag oppervlakkig houden. Voor extra verdieping is er het laatste hoofdstuk. Dit is absoluut wel eens slechter gedaan.

Peter Higgins, ‘Nets, puzzles and postmen; an exploration of mathematical connections’. Oxford University Press, pp. 248, 22 euro.

Een boek over grafen kan natuurlijk niet zonder de vermaarde Koningsberger bruggen. Kon Immanuel Kant, de beroemde filosoof die dagelijks klokke vier een wandelingetje ging maken, alle bruggen van de stad precies één keer aandoen? De intuïtie zei van niet, maar het was een Zwitser, Leonhard Euler, die het wiskundige bewijs leverde dat zulks onmogelijk was en daarmee een van de grondleggers van de grafentheorie werd, ofwel de wiskunde die zich bezighoudt met knooppunten en verbindingen daartussen.

Peter Higgins, hoogleraar wiskunde aan de Universiteit van Essex en uitvinder van de cirkelsudoku, pakt het degelijk en tegelijkertijd speels aan. Zijn boek ‘Nets, puzzles and postmen’ is opgebouwd in min of meer dezelfde hoofdstukken zoals je in een studieboek verwachten zou, maar hij brengt de theorie met meer flair aan de hand van voorbeelden. Het is een bekend trucje: waar een lesboek de abstracte theorie presenteert en dan een bekend voorbeeld geeft ter illustratie, redeneert de popularisator vanuit het voorbeeld naar de theorie toe. Het vakmanschap van Higgins maakt dat de overgang zo goed als ongemerkt gaat.

Zo zit je te lezen over de wandelingetjes van Kant, zo zijn de eilanden in de rivier geabstraheerd naar I1 en I2, en krijg je het bewijs van Euler voor de kiezen. Nee, dat is geen moeilijke wiskunde, althans niet als je aan een TU gearriveerd bent, maar dan zit je ook pas in het inleidende hoofdstuk. Tien pagina’s verderop gaat het over Hamilton-cycli: kun je een wandeling maken waarbij je alle knooppunten eenmaal aandoet? Die vraag is al heel wat moeilijker te beantwoorden dan het bruggenprobleem, waarbij je alle verbindingen maar een keer mag aandoen.

De volgende stap is het vier-kleurenprobleem: is het mogelijk een willekeurige wereldkaart in te kleuren met vier kleuren, zodanig dat geen landen met dezelfde kleur een gemeenschappelijke grens hebben? Wanneer je ieder land als een knooppunt ziet en een grens als een verbinding, wordt dit probleem ook een graaf, maar dan wel eentje met beperkingen. Zo gaat het steeds verder: telkens een nieuwe eigenschap aan de graaf toevoegen en de wiskundige gevolgen ervan uit de doeken doen.

Dan komt de postbode uit de titel. Die moet in een gegeven netwerk ten minste alle verbindingen (straten) aandoen. Een route vinden is niet zo’n kunst, maar wat is de meest efficiënte? En wat als hij met de auto is en sommige straten eenrichtingverkeer kennen? De volgende stap is dat niet iedere verbinding gelijkwaardig is. Sommige straten zijn nu eenmaal langer dan andere, dus de postbode wil die in elk geval niet twee keer hoeven doen. De vraag dringt zich op wat de kortste route is.

Hier gaat het boek rap in de richting van het zogeheten P-NP probleem. Dit is een van de grootste openstaande vragen van de hedendaagse wiskunde. Wie het oplost kan er een miljoen dollar mee verdienen. Hoe groter het netwerk, hoe ingewikkelder het wordt om de kortste route te berekenen. Het aantal potentiële oplossingen groeit namelijk exponentieel met elke extra straat. De methode om de vraag op te lossen hoeft echter niet per se exponentieel mee te groeien. Maar hoe snel dan wel? Die vraag is niet opgelost . maar wel heel relevant, bijvoorbeeld om internetverkeer efficiënt te routeren.

Higgins praat het allemaal met gemak aan elkaar, terwijl hij tegen het einde toch bij wiskunde is aangeland die het middelbare-schoolniveau ontstijgt. Een ware vondst is het laatste hoofdstuk ‘For connoisseurs’. Daarin loopt Higgins alle onderwerpen nog eens langs en geeft wiskundige verdieping, formules op universitair niveau niet schuwend. Welbeschouwd doet hij hier hetzelfde wat andere auteurs met een of meer appendices oplossen, maar door de toevoegingen kort te houden en ze samen ‘hoofdstuk’ te noemen, betrekt hij ze toch meer bij het boek. Een simpel trucje, maar het werkt wel.

Samenvattend: Peter Higgins heeft een boek over grafen geschreven dat zich op drie niveaus laat lezen. Er zijn leuke raadsels voor liefhebbers, gevolgd door uitleg die overgeslagen kan worden door degenen die het graag oppervlakkig houden. Voor extra verdieping is er het laatste hoofdstuk. Dit is absoluut wel eens slechter gedaan.

Peter Higgins, ‘Nets, puzzles and postmen; an exploration of mathematical connections’. Oxford University Press, pp. 248, 22 euro.

Editor Redactie

Do you have a question or comment about this article?

delta@tudelft.nl

Comments are closed.