Onderliggende structuren leggen aard van de werkelijkheid
bloot
De ouderdag 2016 van de Natuurwetenschappelijke
Studentenvereniging Amsterdam bevatte naast het door mij reeds verslagen
hoorcollege Wat is vacuüm? van
theoretisch fysicus Jan de Boer ook een wiskundecollege van Lex Schrijver, dat
minder ver gaat, maar niet minder boeiend was. Schrijver ging in het college Kleuren, roosteren en grafen in op de
grafentheorie, een manier om punten en lijnen tussen punten in een grafiek
onder te brengen, waarmee men de kortste afstanden kan bepalen, hetgeen
gebruikt wordt in een tomtom of door de NS.
Onze kennis over grafen hebben we te danken aan Edsger
Dijkstra die in 1959 het kortste pad algoritme beschreef. Al dertig jaar
daarvoor formuleerde de Hongaarse schrijver Frigyes Karinthy in zijn verhaal Chains de theorie van de zes graden van
separatie, waarin hij stelt dat er hooguit zes punten lopen tussen iedere
verbinding. Dat geldt ook voor personen. Dus iedereen is op een veel nauwere
manier met elkaar verbonden dan men denkt.
Schrijver illustreert het concept van Karinthy aan de hand
van een grafiek, waarin zes personen voorkomen die elkaar wel of niet kennen.
Ook het probleem van Sam Lloyd die in een logistieke puzzel vraagt hoe twee
treinen op enkelspoor elkaar kunnen passeren terwijl er maar een korte
uitwijkmogelijkheid is (zie tekening), valt met de grafentheorie op te lossen.
Schrijver gaat verder met het probleem van het kleuren van
landkaarten, waarbij landen verschillende kleuren krijgen die natuurlijk niet
mogen samenvallen met buurlanden. De graaftheorie leert dat men aan vier
kleuren genoeg heeft om een landkaart te maken. Dit werd in 1976 bewezen met de
vierkleurenstelling.
Het maken van lesroosters kan ook heel goed met de
grafentheorie. Schrijver deelt formulieren uit waarin de ouders zeven docenten
in vier uur aan zes klassen moeten koppelen. Hoewel ik er op de sudoku manier
aardig snel uit kwam, is zoiets niet meer mogelijk als de roosters
ingewikkelder worden. Dan vormt het maken van het graaf en het inkleuren van de
verschillende lijnen een betere methode. Schrijver laat zien hoe men
verschillende lijnen die geen kleur kunnen krijgen omdat de punten niet
verbonden mogen worden met dezelfde kleuren, toch met elkaar kan verbinden,
namelijk door kleuren om te wisselen. Dit procedé werd al in 1916 bewezen en
beschreven door de Hongaar König, maar niemand had dat gezien.
Later in een werkcollege waarin een aantal wiskundige problemen
werden voorgelegd, leerde ik van mijn zoon om het probleem om getallen te
vinden tussen 10 en 99 die vier keer zo groot zijn als de twee cijfers bij
elkaar opgeteld worden, op te lossen door middel van een formule, waarbij de
getallen voorgesteld worden met a en b. Na het vinden van de oplossing kon ik
me voorstellen hoeveel voldoening een studie wiskunde kan geven.
Hier
een pdf van Schrijver over het onderwerp onder de titel Grafen: Kleuren en Routeren, waarin het op p. 19 gaat over de
oplossing van Euler van het zgn. Koningsberger bruggenprobleem, waarbij men een
stadswandeling maakt die slechts een keer over alle bruggen gaat, hier
mijn verslag van het natuurkunde college van Jan de Boer, hier
een aantal grappige maar ook leerzame puzzels van Sam Lloyd.
Geen opmerkingen:
Een reactie posten