Page 16 - Mathelo Grafentheorie hoofdstuk 1

Grafentheorie

Toemaatje: de huwelijkheidsstelling van Hall

Tweedelingsgrafen worden o.a. gebruikt bij matchingproblemen.

Stel er is een groepje personen moeten aan elkaar gekoppeld worden. Er zijn evenveel mannen als
vrouwen. De vrouwen hebben allemaal een lijstje gemaakt van de mannen die ze leuk genoeg vinden en
de mannen zijn met iedere vrouw tevreden. Is er dan een koppeling mogelijk waarbij de wensen van de
vrouwen gerespecteerd worden?
De vraag: Is het mogelijk om de zes vrouwen te koppelen aan de zes partners?

In sommige situaties is het makkelijk om na te gaan dat er geen matching mogelijk is. Indien er een
vrouw is die geen enkele partner leuk vindt of indien er twee vrouwen zijn die enkel en alleen dezelfde
partner willen.
In 1930 bewees Filip Hall een stelling die een nodige en voldoende voorwaarde geeft voor het bestaan
van een oplossing indien k vrouwen met k verschillende mannen willen trouwen.
Hierbij wordt gebruik gemaakt van tweedelingsgrafen.

In het jongerentijdschrift Pythagoras werd in januari 2009 een interessant artikel gepubliceerd over de
huwelijkheidsstelling van Hall
http://www.wiskundemeisjes.nl/wp-content/uploads/2009/09/hallpyth.pdf

t
e
n
.
o
l
e
h
t
a
m
.
w

w
w

© 2021 Ivan De Winne ivan@mathelo.net 15