Opzet Profielwerkstuk
Grafentheorie
Omschrijving
Hieronder zie je een plattegrond van de TU-Eindhoven. 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 dit soort plattegronden maar maak je gebruik van een zogenaamde graaf. Een graaf bestaat uit punten en lijnen. In het TUE-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 gericht 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 NG&NT
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?"
Enkele links (naar links) rondom grafentheorie