Welcome, reader! According to Antony Hegarty in this second decade of the new century our future is determined. What will it be? Stays all the same and do we sink away in the mud or is something new coming up? In this blog I try to follow new cultural developments.

Welkom, lezer! Volgens Antony Hegarty leven we in bijzondere tijden. In dit tweede decennium van de eenentwintigste eeuw worden de lijnen uitgezet naar de toekomst. Wat wordt het? Blijft alles zoals het is en zakken we langzaam weg in het moeras van zelfgenoegzaamheid of gloort er ergens iets nieuws aan de horizon? In dit blog volg ik de ontwikkelingen op de voet. Als u op de hoogte wilt blijven, kunt u zich ook aanmelden als volger. Schrijven is een avontuur en bloggen is dat zeker. Met vriendelijke groet, Rein Swart.

Laat ik zeggen dat literaire kritiek voor mij geen kritiek is, zolang zij geen kritiek is op het leven zelf. Rudy Cornets de Groot.

Do not go gentle into that good night, Old age should burn and rage at close of day; Rage, rage against the dying of the light. Dylan Thomas.

Het is juist de roman die laat zien dat het leven geen roman is. Bas Heijne.

In het begin was het Woord, het Woord was bij God en het Woord was God. Johannes.



donderdag 23 juni 2016

Lex Schrijver over Kleuren, roosteren en grafen, Universiteit van Amsterdam, 18 juni 2016


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 plaatsen