Een complete koppeling bevat ale punten van de graaf. Is een maximale koppeling in een bipartiete graaf ook automatisch compleet? En andersom? Hoe kun je dat bewijzen?
Van de
Docent - dinsdag 11 januari 2005
Antwoord
Aangenomen dat gekoppelde paren disjunkt zijn dan is een volledige koppeling (natuurlijk) maximaal want er kan geen paar meer gevormd worden. Het omgekeerde hoeft niet te gelden: de punten zijn 1, 2, 3, 4, 5 en 6; de lijnen zijn 1-2, 1-4, 1-6, 3-2, 3-6, 5-2, 5-4 en 5-6. De graaf is bipartiet: de verzamelingen van de even en de oneven getallen vormen een tweedeling. De koppeling bestaande uit 1-2 en 5-6 is maximaal maar niet volledig want 3 en 4 zijn niet gekoppeld. Overigens bestaat in een graaf met een oneven aantal punten nooit een volledige koppeling.
