Nando 4 D-FINALITEIT 5 UUR – DISCRETE WISKUNDE EN LOGICA
08 Grafen
Inhoud Instap 1 Grafen rondom ons 2 Wandelingen in een graaf 3 Minimaal opspannende bomen 4 Kortste paden 5 Het handelsreizigersprobleem 6 Graafkleuring Signaaloefeningen Differentiatietraject Studiewijzer
wat je al kunt – Je kan problemen oplossen met boomdiagrammen.
in de kijker Je kan met behulp van een schematische voorstelling (graaf) en een algoritme praktische problemen uit de dagelijkse
wat je leert in deze module
praktijk oplossen.
– een graaf gebruiken als model of schematische
wiskundetaal
voorstelling – graaf
– pad
wordt de betekenis van de knopen, de bogen en de buren
– knoop van een graaf
– cykel
van de knopen uitleggen
– in een concrete situatie die door een graaf beschreven
– boog van een graaf
– spoor
– een graaf die bij een concrete situatie behoort, opstellen
– samenhangende graaf
– circuit
– het bestaan van specifieke wandelingen opsporen die alle
– orde van een graaf
– eulertoer
– grootte van een graaf
– eulergraaf
– nabuurschap van een
– hamiltoncykel
bogen juist één keer doorlopen – het algoritme van Kruskal of Prim toepassen om de minimaal opspannende boom in een gewogen graaf te bepalen – het algoritme van Dijkstra toepassen om het kortste pad
knoop
– hamiltongraaf
– graad van een knoop
– boom
– planaire graaf
– algoritme van Prim
– gewogen graaf
– algoritme van Kruskal
– het handelsreizigersprobleem linken met grafen
– reguliere graaf
– algoritme van Dijkstra
– de betekenis van graafkleuring begrijpen en dit toepassen
– volledige graaf
– handelsreizigersprobleem
– multigraaf
– graafkleuring
in een gewogen graaf te bepalen
in concrete situaties
– wandeling
1