Page 5 - Mathelo Grafentheorie hoofdstuk 1

Grafentheorie

1.2.2 Het prille begin van de grafentheorie: abstractie van het probleem

De Zwitserse wiskundige Leonard Euler vereenvoudigde de plattegrond van Koningsbergen door elk
stadsdeel voor te stellen door een punt (knoop) A, B, C en D en elke brug door een boog (een verbinding
tussen de knopen).

Hierdoor kan men het probleem van de 7 bruggen van Koningsbergen weergeven met een abstract
schema, een zogenaamde graaf. Omdat er tussen de knopen meerdere bogen zijn noemt men dit een
multigraaf. Alleen de essentiële elementen worden nog weergegeven zonder de achtergrond van het
stadsplan. Men noemt dit een wiskundig model dat toelaat om gelijkaardige situaties met dezelfde bril
van de grafentheorie te onderzoeken.

Interactieve GeoGebra versie via deze link https://www.geogebra.org/m/v282yfnh
Deze graaf heeft vier knopen (de stadsdelen) en zeven bogen (de bruggen).

Formulering van het 7 bruggenprobleem met grafen.
Is het mogelijk de graaf zo te doorlopen, dat daarbij elke boog slechts éénmaal gepasseerd wordt?

Beginnen we bijvoorbeeld bij de knoop A, dan moet daar een ,,inkomende boog”, maar ook een t
e
,,uitgaande boog” zijn. Telkens als we via één van de bogen in een knoop aankomen, moet daar weer
n
behalve de ,,inkomende” ook een ,,uitgaande boog” zijn. .
o
Het aantal bogen dat in een knoop toekomt (of uit dit knooppunt vertrekt) noemt men de graad van l
e
deze knoop in een graaf. h
t
Noteer de graad van de knopen van deze graaf. a
m
Knoop A B C D .
w
Graad 4 3 3 3 w
w
Zijn deze graden even of oneven?

© 2021 Ivan De Winne ivan@mathelo.net 4