Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\require{AMSmath}

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
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.

kphart
donderdag 13 januari 2005

©2001-2024 WisFaq