\require{AMSmath}

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
dinsdag 14 december 2010

©2001-2024 WisFaq