kard.max, inklusionsmaxMatch. < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Hallo,
Sei G=(V,E) ein beliebiger zusammenhängender Graph.
- kardinalitätsmaximales Matching M: Für alle Matchings M' ist |M|>|M'|
- inklusionsmaximaley Matching M: Für alle Kanten [mm] e\in E\setminus [/mm] M ist [mm] M\subset\{e\} [/mm] kein Matching
zu zeigen ist jetzt, dass für jedes inklusionsmaximale Matching M und jedes kardinalitätsmaximale Matching M' gilt: [mm] 2|M|\geq|M'|
[/mm]
Leider fehlt mir dafür jegliche Idee oder Intuition. Kann mir da irgendjemand nen Tipp geben oder weiterhelfen?
Danke! 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:23 Mi 04.07.2012 | | Autor: | Teufel |
Hi!
Sei $M'$ ein kardinalitätsmaximales Matching (Maximum Matching). Dann ist die zentrale Beobachtung die folgende: Nimmst du eine Kante $e$ in ein Matching $M$ auf, so kannst du dir höchstens ein weiteres Matching verbauen, was vorher dagewesen wäre.
(Beispiel: Nimm den Graphen mit den Knoten 1,2,3,4 und den Kanten (1,2), (3,4). Dann wäre [mm] M'=\{(1,2),(3,4)\} [/mm] ein Maximal Matching. Fängst du aber ungeschickt an und nimmst (2,3) in dein Matching M auf, so hast du dir die Chance auf eine weitere Kante verbaut.)
Im Klartext heißt das dann folgendes: Weil ein Maximum Matching $M'$ existiert, kannst du also maximal $m:=|M'|$ Kanten in M bekommen.
Sei $M$ anfangs leer. Wir bauen $M$ nun schrittweise auf. Nimmt man die 1. Kante auf, so macht man höchstens eine weitere Kante kaputt, die man vorher noch hätte aufnehmen können. Damit gibt es aber trotzdem noch (mindestens) $m-2$ weitere Kandidaten für Kanten für dein Matching $M$ im Graphen. Nach Aufnahme der 2. Kante gibt es noch (mindestens) $m-4$ weitere Kandidaten. u.s.w.
Den Rest bekommst du sicher hin!
|
|
|
|
