WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\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

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