De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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
Vragen naar aanleiding van dit antwoord? Klik rechts..!
donderdag 13 januari 2005



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3