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,
HaHa Nguyen
10-12-2010
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
#63787 - Bewijzen - Student universiteit