Grafen

Stijn Cambie, Wouter van Doorn en Sam Mattheus Inleiding Paul Erdös (1913-1996) wordt met zijn 1525 papers als een van de grootste, of minstens meest gepassioneerde wiskundigen ooit gezien. Hij stelde dan ook heel veel vragen die hem fascineerden, vele nog steeds onopgelost, nu zelfs bijna 30 jaar na zijn dood. In de recente jaren

Ik geef les in de academische lerarenopleiding aan de Universiteit Antwerpen. Eén thema dat tijdens onze lessen binnen de vakdidactiek wiskunde aan bod komt, is het activeren van leerlingen. Tijdens lessen moet de denkactiviteit bij de leerlingen zelf liggen. We gaan na aan welke voorwaarden een werkvorm moet voldoen om diepgaand en inzichtelijk leren op gang te brengen. Elke werkvorm draagt immers de mogelijkheid in zich om actief leren te bevorderen, net zoals elke werkvorm ook kan blijven steken op het niveau van bezigheidstherapie. Onze studenten experimenteren tijdens oefenlessen, stagelessen of lessen die ze als leraar in opleiding (LIO) geven…

3Blue1Brown https://www.youtube.com/watch?v=YtkIWDE36qU Strong law of small numbers De formule [latex]F_n=2^{2^n}+1[/latex] geeft priemgetallen voor natuurlijke getallen [latex]n \le 4[/latex]. Fermat verwachtte dat de rij [latex]F_n[/latex] zou blijven doorlopen met priemgetallen. Toen Euler in 1732 bewees dat [latex]F_5[/latex] geen priemgetal is, werd de droom rond de priemgetallen van Fermat in de kiem gesmoord. De formule [latex]G_n=n^2-n+41[/latex] echter houdt het iets langer vol. Voor alle gehele getallen [latex]n ≤ 40[/latex] geeft ze een priemgetal. Pas bij 41 houdt het op. Vanaf dan wisselen priemgetallen met samengestelde getallen af. Dit zijn twee voorbeelden waarvan de evaluaties voor kleine gehele getallen ons op het verkeerde…

Het lemma van Sperner is een resultaat dat de kracht van de grafentheorie als didactisch onderwerp opnieuw laat zien: met minimale kennis van grafen leid je een bewijs af met een diep resultaat. Het lemma kan bewezen worden met sterkere leerlingen in de 2[latex]^\text{e}[/latex] of 3[latex]^\text{e}[/latex] graad, die niet terugdeinzen voor een streepje abstractie. Het lemma is de discrete variant van de stelling van Brouwer en legt zo een link tussen continue en discrete wiskunde. Een graaf [latex]G=(V,E)[/latex] bestaat uit twee eindige verzamelingen [latex]V[/latex] en [latex]E[/latex]. De elementen van [latex]V[/latex] worden knopen genoemd, en die van [latex]E[/latex] bogen. Elke boog…

Instant Insanity is de naam van een puzzel die bestaat uit vier kubussen waarvan elk zijvlak rood (R), blauw (B), groen (G) of wit (W) is. In de figuur hieronder zie je een foto van een uitgave van de speelgoedproducent Parker Brothers uit 1967 die nog in de originele verpakking zit. De tekst die op de verpakking staat, is veelbelovend: 'Be calm ... You may never, ever see them this way again'. [caption id="attachment_32777" align="aligncenter" width="441"] Figuur 1 Be calm ... ... You may never, ever see them this way again. (Bron: https://www.ebay.com/itm/392938423661)[/caption] Het doel van het spel is om…

In deze coronatijd overstelpen de media ons met uitgebreid cijfermateriaal. Zelden werd het belang van wiskunde zo duidelijk onderstreept voor de hele maatschappij. Toch loopt de itnerpretatie van dit materiaal nogal eens fout. In deze loep doen we een bescheiden poging om helderheid te brengen in dit kluwen van informatie. We zoomen in op drie Covid-gerelateerde thema's die bruikbaar zijn in de lessen wiskunde. We brengen de beruchte contactbubbels in verband met grafentheorie. Vervolgens bespreken we een item in verband met kansrekening in het kadeer van teststrategieën voor Covid-19. In het laatste deel focussen we op een uitgewerkte onderzoeksopdracht over de discrete versie van heet beruchte SIR-model. We leveren in deze loep materiaal voor in de klas en achtergrond om te kunnen vertellen elk jaar.

Bruno Teheux, À la recherche des chemins les plus courts Losanges 46 (2019), 45-54 De auteur van dit artikel is onderzoeker aan de ‘Mathematics Research Unit’ van de universiteit van Luxemburg. Het artikel gaat over grafentheorie en het algoritme van de Nederlander Edsger Wybe Dijkstra (20ste eeuw) om de kortste routes te vinden in een graaf. Dit algoritme bepaalt de kortste routes vertrekkend van een gegeven knoop naar elke andere knoop (afzonderlijk; het gaat niet over een route die alle knopen moet aandoen zoals bij het handelsreizigersprobleem). De puzzel van de witte en zwarte bollen Het spectaculaire is dat Teheux dit…

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.

Pythagoras, wiskundetijdschrift voor jongeren, 59/1, 6-8 Het tijdschrift Pythagoras is sterk in korte artikels die lange namijmeringen teweeg brengen. Zo ook deze bijdrage, die met twee bolletjes gemarkeerd is (middelmatige moeilijkheidsgraad). Het klassieke handelreizigersprobleem Het handelsreizigersprobleem (Eng: travelling salesman problem) is een klassieker. Bij dit probleem is een aantal steden gegeven samen met de onderlinge afstanden tussen deze steden. Gevraagd is de kortste route te vinden die alle steden aandoet en eindigt waar het begonnen is. Het handelsreizigersprobleem wordt vaak als voorbeeld genomen van een probleem waarvoor (nog) geen ''snel' algoritme bestaat. Om met zekerheid de kortste handelsroute langs [latex]n[/latex]…

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