Het geheim van de smid
Over de doorloopbaarheid van grafen


Animatie van alle mogelijke huisjes, overgenomen van wikipedia (huis met een kruis)

De vraag is: kun je het huisje in één keer tekenen zonder je pen op te tillen? Als dat kan is de graaf doorloopbaar. Het huisje kan op vele manieren in één keer getekend worden als je het goede startpunt kiest. Je moet links- of rechtsonder beginnen. Begin je links, dan eindig je rechts. Of andersom.


Leerlingwerk van Niels, groep 8

Een les over grafen

Een graaf is (meestal) een tweedimensionaal plaatje. Het lijkt op of is soms een plattegrond.
De graaf bestaat uit knooppunten en verbindingslijnen. Die verbindingen kunnen recht of krom zijn.
De les is geschikt voor groep 7-8 (en topklassen).

Stap 1 - het huisje

Een voorbeeld van een eenvoudige graaf is het huisje. Leerlingen gaan hier mee aan het werk.

Stap 2 - een touw

Een touw met een knoop erin op de grond met allerlei overlappingen kun je ook als een graaf beschouwen. Je ziet de knooppunten en de verbindingen.
Deze graaf blijkt vanaf elk punt in alle richtingen doorloopbaar.

Stap 3 - de Koningsberger bruggen

Euler, een beroemde wiskundige, loste het probleem in 1736 op. Dat was het begin van de grafentheorie, nu een belangrijk vak in het oplossen van allerlei verbindingsproblemen op het gebied van routes en schakelingen.
Voor leerlingen van de basisschool een kennismaking met een nieuw vakgebied dat ook in het voortgezet onderwijs een rol speelt.

Verwijzingen
  |  Over deze lessen  |  Meer lessen  |  © Universiteit Utrecht  |  123 views  |