Page 11 - Mathelo Grafentheorie hoofdstuk 1

Grafentheorie

1.4.2 Tweedelingsgrafen (bipartiete grafen)

Voorbeeld: speed dating
Bij de start van het schooljaar organiseert de klastitularis een speeddating in de klas om de leerlingen
met elkaar te laten kennismaken.
De klas wordt in twee groepen verdeeld, 5 jongens en 6 meisjes.

Hoeveel mogelijkheden zijn er indien elke jongen met elk meisje een kort gesprek moet voeren?
Interactieve versie met GeoGebra via deze link https://www.geogebra.org/m/rtgfwwuz

Een tweedelinsgraaf (bipartiete graaf) is een graaf waarbij men de knopen in twee groepen kan
verdelen zodanig dat elke boog van de graaf een knoop van de ene groep verbindt met een knoop van
de andere groep. Er mogen geen bogen zijn tussen twee knopen van dezelfde groep.

Bij een volledige tweedelingsgraaf (volledige bipartiete graaf) zijn alle knopen van de ene groep
verbonden met alle knopen van de andere groep.

Om de twee groepen van een tweedelingsgraaf aan te duiden kan je ofwel twee kleuren gebruiken of de
groepen aanduiden met kringen of kruisjes.
Opmerking
Het is niet altijd zo eenvoudig om een duidelijke voorstelling van een tweedelingsgraaf te maken waarbij
de twee groepen zichtbaar van elkaar gescheiden zijn.

Dit zijn drie verschillende voorstellingen van dezelfde tweedelingsgraaf.

Interactieve GeoGebra versie via de link https://www.geogebra.org/m/ks56rg8k

t
Oefening e
n
Zijn de volgende grafen tweedelingsgrafen? .
o
l
e
h
t
a
m
.
w
w
w
Interactieve GeoGebra versie via de link https://www.geogebra.org/m/gpkvzuyr

© 2021 Ivan De Winne ivan@mathelo.net 10