Page 2 - Mathelo Grafentheorie hoofdstuk 1
P. 2
Grafentheorie
1 Grafentheorie: inleiding
1.1 Een wereld van netwerken
Een blik op de kaart van de metrolijnen (en tramlijnen) van Brussel toont ons dat wiskundige objecten
overal aanwezig zijn in ons dagelijks leven. Zo’n schematisch weergave van de metrolijnen en tramlijnen
samen met de haltes noemt men in de wiskunde een graaf.
De ligging van de metrolijnen en haltes worden hierbij niet geografisch correct getekend. Ook de
afstanden tussen de haltes stemmen niet overeen met de werkelijke afstanden. De stations die in
werkelijkheid het meest uit mekaar liggen zijn Schuman en Merode met 1,2 km. De haltes Joséphine-
Charlotte et Gribaumont, met slechts 350 meter liggen in werkelijkheid het dichtst bij elkaar. De getallen
op de kaart stellen in dit geval de wandeltijd voor in minuten.
Bij dit soort kaarten is het voor de reiziger enkel van belang om de opstapplaats en de eindbestemming
te kiezen en een duidelijk beeld te krijgen van de verschillende metrolijnen.
Een graaf in de wiskunde is ongeveer hetgeen we in het dagelijks leven een netwerk noemen. Een graaf
bestaat uit een aantal punten die men knopen noemt en verbindingen die men bogen (kanten of lijnen)
noemt. Indien je treinstations beschouwt als knopen dan zijn de treinsporen de bogen.
Een netwerk van vrienden op een sociaal netwerk zoals facebook vormt ook een graaf. De knopen zijn
t
de personen. Tussen twee personen A en B loopt er een verbinding indien zij met elkaar bevriend zijn. e
n
Een rioleringssysteem, een wegennet, een computernetwerk en uiteraard het internet zijn andere .
voorbeelden van netwerken die men kan voorstellen met een graaf. o l
e
h
t
a
m
.
w
w
w
© 2021 Ivan De Winne ivan@mathelo.net 1
