Profielwerkstuk Grafentheorie

Omschrijving
Hierboven zie je een plattegrond van de TU/e. Een bezoeker kan met deze plattegrond waarschijnlijk snel zien hoe hij zo snel mogelijk bij een bepaald gebouw komt. Maar ook kun je met dit plaatje uitzoeken of er voor een bezoeker een wandeling bestaat waarbij je paden precies een keer doorloopt. 

In de wiskunde maak je meestal geen gebruik van dit soort plattegronden maar maak je gebruik van een zogenaamde graaf. Een graaf bestaat uit punten en  lijnen. In het TU/e-voorbeeld zijn de wegen de lijnen en de punten waar wegen samenkomen de punten. Punten noem je ook wel knopen of knooppunten. Als je op zoek bent naar de kortste weg tussen twee punten dan moet je ook nog alle onderlinge afstanden weten.

In dit voorbeeld is een kortste weg tussen twee punten misschien niet eens zo moeilijk te vinden. Met een beetje proberen vind je waarschijnlijk snel die weg. Dat verandert bij een grote graaf. Denk bijvoorbeeld aan het internet. Dat is een gigantisch groot voorbeeld van een graaf. De files op de miljoenen computers zijn de punten (ook een pagina is een file), de links tussen de ene file naar de andere file kun je zien als een lijn. Maar ook bij kleine grafen kan het niet meevallen om een kortste weg te vinden. Zie je hieronder de kortste weg van A naar G? En zie je een rondwandeling die start in A?

Voor wie?
Leerlingen met het profiel NT of NG.

Beginkennis
Er is geen speciale voorkennis vereist.  

Wat wordt er van je verwacht?
In de eerste plaats bestudeer je de reader "Kun je me de kortste weg vertellen?" en maak je alle opgaven in deze reader. De bundel eindigt met een aantal suggesties voor verdere studie. In overleg met je begeleidende docent kies je er daar een uit. Vervolgens ga je op zoek naar informatie over je gekozen onderwerp. De gevonden informatie bestudeer je en presenteer je in een geschikte vorm.

Studiemateriaal
De reader Kun je me de kortste weg vertellen? (in pdf-formaat, 1.1MB) en antwoorden van de opgaven (in pdf-formaat, 142 KB).

Links
Enkele links (naar links) rondom grafentheorie: