Baum höchstens ein perfektes Matching |
| 17.09.2016, 11:11 | MrBurns1988 | Auf diesen Beitrag antworten » |
| Baum höchstens ein perfektes Matching Die Aufgabe lautet: Zeigen Sie, dass ein Baum T=[V,E] höchstens ein perfektes Matching besitzen kann. Danke schon im Voraus. |
||
| 17.09.2016, 13:25 | Huggy | Auf diesen Beitrag antworten » |
| RE: Baum höchstens ein perfektes Matching Das sollte sich über eine sukzessive Reduktion der Baumtiefe zeigen lassen. Es sei M die Kantenmenge des Matchings. Nun betrachte man die Endknoten des Baums. Wenn es ein perfektes Matching gibt, müssen die zu den Endknoten führenden Kanten in M enthalten sein. Dann darf ein unmittelbar über einem Endknoten stehender Knoten nur einen Ast haben, sonst wäre das Matching nicht perfekt. Damit ist die in M enthalten Menge der zu Endknoten führenden Kanten eindeutig bestimmt, falls es ein perfektes Matching des Baumes gibt. Jeder unmittelbar über einem Endknoten stehende Knoten ist mit einer Kante mit einem unmittelbar darüber stehenden Knoten verbunden. Diese Kante kann nicht in M enthalten sein, sonst wäre das Matching nicht perfekt. Wenn es also ein perfektes Matching des Baums gibt, dann muss der um die Endknoten und um die unmittelbar darüber liegenden Knoten reduzierte Baum ein eindeutiges perfektes Matching besitzen, falls er ein perfektes Matching besitzt. Damit hat man die Baumtiefe um mindestens 2 reduziert. Dies fortgesetzt ist die Eindeutigkeit eines eventuellen perfekten Matchings nur noch für die minimale Baumtiefe zu zeigen. |
||
|
|
