WisFaq!

Koppelingen van een graaf

Hallo,

Ik heb een lastige vraag.

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 Velde
11-1-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.

kphart
13-1-2005