De digitale vraagbaak voor het wiskundeonderwijs

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

HOME

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

inloggen

colofon

  \require{AMSmath} Printen

Grafen

Beste heer/ mevrouw,
kunt u me misschien helpen of een hint geven op de volgende vraag:
Bewijs dat een boom hoogstens 1 perfecte matching heeft.

Met vriendelijke groeten,
Ha

Ha Ngu
Student universiteit - vrijdag 10 december 2010

Antwoord

Inductie naar het aantal takken: kies een eindpunt, dat heeft precies één buur.
Als er al een matching is moet deze tak daarin meedoen. Haal de tak weg en pas je inductiehypothese toe op de overblijvende graaf.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
dinsdag 14 december 2010



klein |  normaal |  groot

home |  vandaag |  bijzonder |  twitter |  gastenboek |  wie is wie? |  colofon

©2001-2021 WisFaq - versie 3