zwei maximale Matchings < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:52 Mi 24.01.2007 | | Autor: | Bastiane |
| Aufgabe | | Zeige: seien M,N zwei maximale Matchings in einem Graphen G. Dann gilt: [mm] $|M|\le [/mm] 2|N|$. |
Hallo zusammen!
Ich würde obige Aufgabe gerne alleine lösen, nur fehlt mir irgendwie der Ansatz. Ich habe mal mit ein paar Graphen rumprobiert, aber ich bekomme zwei maximale Matchings überhaupt nur hin, die sich in der Anzahl um höchstens eine Kante unterscheiden. Vielleicht hat auch jemand ein Beispiel, wo das mehr als eine Kante ist?
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
Hallo liebe Bastiane,
schau Dir doch mal [mm] M\cup [/mm] N an: es gibt gemeinsame Kanten, und wie sieht dann genau [mm] M\Delta [/mm] N=_{def.} [mm] (M\setminus N)\cup (N\setminus [/mm] M) aus ?
Wg. Maximalität von N, M kann man ja zB keine Kante von M nehmen , um damit N noch zu vergrößern.
Frohes Schaffen und lieben Gruss !
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:02 Do 25.01.2007 | | Autor: | Bastiane |
Lieber Mathias!
Leider hilft mir das nicht. Ich kann mir das nicht vorstellen. Hab' zwar jetzt Beispiele, wo sich die Matchings um mehr als eine Kante unterscheiden, sogar ein Beispiel, wo der Extremfall mit doppelt so vielen Kanten eintritt, aber allgemein kann ich mir das nicht vorstellen.
Kannst du mir noch einen Tipp geben?
Viele Grüße
Bastiane
|
|
|
| |
|
Liebe Chris,
allso nochmal: Wir nehmen M und N, zwei maximale Matchings. Die haben im allgemeinen einen Schnitt [mm] M\cap [/mm] N, und dann können wir die symmetrische Differenz [mm] M\Delta [/mm] N betrachten, die, wie wir ja jetzt schon wissen, aus alternierenden Kreisen und alternierenden Pfaden besteht. M kann ja jetzt nur dadurch mehr Kanten haben als N, dass es in der symm. Differenz alternierende Pfade gibt, deren beide Endkanten aus M sind, denn pro solchen Pfad hat M eine Kante mehr als N.
Das liefert bestenfalls nen Faktor 2, um den M größer sein kann als N, und zwar dann, wenn [mm] M\cap N=\emptyset [/mm] und jede Komponente von [mm] M\Delta [/mm] N ein alternierender Pfad der Länge 3 mit Endkanten aus M ist.
Vielleicht hab ich da jetzt im vergleich zu Deiner Frage die Rollen von M und N vertauscht, aber ansonsten sollte es das sein, nicht wahr ?
Beispiele sind nicht immer hilfreich, oft sieht man vor lauter konkretem Beispiel die Essenz dahinter nicht.
Lieben Gruss,
Mathias
|
|
|
|
