Page 6 - Mathelo Grafentheorie hoofdstuk 1

Grafentheorie

Besluit:
Hieruit blijkt, dat als we de graaf zo willen doorlopen, dat we elk der bogen slechts eenmaal gebruiken,
er bij elke knoop een even aantal bogen moet samenkomen (behalve in de startknoop of eindknoop).
Aangezien in geen enkel knooppunt een even aantal bogen samenkomt is het onmogelijk een
wandeling door Koningsbergen te organiseren, waarbij elk der bruggen slechts éénmaal doorlopen
wordt.

1.3 Eerste begrippen over grafen

1.3.1 Knopen en bogen

Het is niet moeilijk om je een voorstelling te maken van een graaf (meervoud grafen).

Interactieve GeoGebra versie dia deze link https://www.geogebra.org/m/sshufwsz
Als figuur bestaat een graaf uit een aantal knopen (de getekende punten) en bogen (de verbindingen
tussen de punten). Meestal worden deze verbindingen getekend als een lijnstuk, maar dit is niet
noodzakelijk. Men mag ook krommen als verbindingen gebruiken en de knopen een naam geven.
Wel belangrijk bij grafen is het feit of twee knopen al dan niet met elkaar verbonden zijn.

Opmerking 1: isomorfe grafen
Merk op dat grafentheorie geen meetkunde is. De plaats van de knopen en de vorm en lengte van de
bogen zijn van geen enkel belang. Hieronder twee voorstellingen van dezelfde graaf. Men noemt grafen
die er verschillend uitzien maar toch dezelfde zijn, zoals in het voorbeeld hieronder, isomorf.

t
e
n
Bepaal voor deze grafen het aantal knopen en bogen. .
o l
e
Opmerking 2: drie verschillende grafen h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 5