WisFaq!

\require{AMSmath} geprint op donderdag 28 maart 2024

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 Nguyen
10-12-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
14-12-2010


© 2001-2024 WisFaq
WisFaq - de digitale vraagbaak voor het wiskunde onderwijs - http://www.wisfaq.nl

#63787 - Bewijzen - Student universiteit