Page 17 - Mathelo Grafentheorie hoofdstuk 1

Grafentheorie

INHOUD LEERWERKBOEK GRAFENTHEORIE

HS 1 Het zevenbruggenprobleem van Koningsbergen
Inleidende begrippen; knopen en bogen, graad van een knoop.
Toepassingen: Tweedelingsgrafen, vrienden op feestje, huwelijkstelling Hall...

HS 2 Eulergrafen
Huisjes tekenen, Eulersporen en Eulercircuits, stellingen, stappenplan.
Toepassingen: het Chinese postbode probleem.

HS 3 Kleuren van grafen
Kleuren van landkaarten, historiek, puzzelplezier.
Graafkleuringen, planaire grafen...
Greedy algoritme voor het kleuren van grafen.

HS 4 Hamiltongrafen
Van Platonisch veelvlak naar Hamiltongraaf.
Een reis rond de wereld met het icosean Game.
Verschil tussen Eulergrafen en Hamiltongrafen.
Eigenschappen Hamiltongrafen.
Criteria: stelling van Dirac, Ore... Formule van Euler.

HS 5 Het handelsreizigersprobleem TSP
Praktisch onoplosbare problemen.
Hamiltoncykels.
De TSP-wedloop
Heuristieken: beste-buur, invoegen...

HS 6 Bomen
Minimaal opspannende boom.
Algoritme van Prim en Kruskal.

HS 7 Kortste route
Brute force algoritme, dichtste buur algoritme.
Algoritme van Dijkstra.
Aansluitend bij elk hoofdstuk een reeks oefeningen en vraagstukken voor leerlingen.
Verbetersleutels voor de leraars. Collectie interactieve GeoGebrabestanden
t
De overige hoofdstukken van het lesmateriaal “Grafentheorie” is beschikbaar voor deelnemers aan de e
n
webcursus “Grafentheorie” die wordt aangeboden via de Mathelo leeromgeving. .
o
l
e
h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 16