Matching- Beweis über Dualität < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 22:40 Mo 06.03.2006 | | Autor: | Tyr7 |
| Aufgabe | Jeder gerade Knoten in V(F) hat nur ungerade Knoten als Nachbarn. In diesem Fall bleibt zu zeigen, dass das Matching maximale Kardinalität hat, Wir argumentieren über eine Dualitätsaussage.
Dazu sei X [mm] \subseteq [/mm] V eine Teilmenge von Knoten und O(X) die Anzahl der Zusammenhangskomponenten von G \ X, die eine ungerade ANzahl von Knoten haben
Lemma:
Sei M ein Matching in G=(V,E) und X [mm] \subseteq [/mm] V. Dann gilt 2|M| [mm] \le [/mm] |V| - (O(X) - X) |
Hallo Zusammen,
es handelt sich hier um die Fortsetzung des Edmonds Algorithmus (siehe vorheriger Post), um den Fall, dass man den Wald nicht mehr vergrößern kann. Also der Fall, wo keine der drei Bedingungen erfüllt ist.
Ein Beispiel:
a b d e
\ / \ /
c f
\ /
\ /
x
M= {(c,b), (f,e)}
Der Wald:
a---c===b
d---f===e
x
Wie die Formel zustande kommt ist mir klar, aber die eigentliche Frage bezieht sich auf die Dualität und wieso die Behauptung, dass das Matching maximal ist, damit bewiesen ist.
Eine Idee:
ich kenne die Dualität als sowas:
ein primales Problem soll maximiert werden <-> duales Problem soll minimiert werden
Die optimale Lösung des einen Problems ist auch optimal für das andere Problem.
Jetzt hier: das Matching soll maximiert werden.
Also was kann ich minimieren, damit das Matching maximiert wird?
Nach langem Überlegen kamm ich auf die Idee, dass die Anzahl der Bäume in dem Wald minimiert werden sollte. Denn wenn ich nur einen Baum habe, so ist mein Matching perfekt oder fast perfekt. (Ich setze mal voraus, dass ich den Wald betrachten kann und nicht G, da in Bezug auf das Matching sind ja beide gleichwertig. Dabei habe ich alle Pfade in meinem Wald wieder drin.)
Die Anzahl der Bäume in dem Wald entspricht auch dem O(X) wenn ich für X= [mm] \emptyset [/mm] setze. Das geht ja auch, da die Bäume in dem Wald alle eine ungerade Anzahl von Knoten haben (abgesehen von den Ausnahmen).
Das würde soweit passen, denn perfektes Matching ist wenn 2|M| = |V|. Da ich (O(X) - |X|) von |V| abziehe, wird mein Matching kleiner, je größer O(X) ist, also auch je mehr Bäume ich habe.
Was mich nur stört, ist das |X| in der Klammer. Ich kann theoretisch das X beinahe frei manipulieren (indem ich zu X ganz viele Knoten hinzufüge, ohne dass die einzelnen Bäume verschwinden, z. B X={c,b,f,e}), so dass es auch größer als O(X) wird, damit hätte ich zum Schluss 2|M| > |V|, was ja nicht sein darf...
Wo liegt jetzt der Fehler? Bin ich total falsch bei meiner Überlegung?
Oder anders: wo ist hier die Dualität versteckt? Wieso ist es ein Beweis für die Maximalität des Matchings?
Vielen Dank udn viele Grüße
Tyr
|
|
| |
|
Hallo und guten Morgen,
nochmal als Warming Up:
Gegeben ein Graph G und ein Matching M in G, dann heisst ein Wald F ein ''alternierender Wald'' fuer M in G, falls
- jede Komponente T von F genau einen Knoten [mm] r_T [/mm] enthaelt, der nicht in einer Kante von M ist (Wurzel),
- V(F) enthaelt alle Knoten, die nicht von M ueberdeckt sind
- (v heisst gerade, falls v geraden Abstand zur Wurzel der Komponente hat, in der v liegt, ungerade, wenn der Abstand ungerade ist)
- Alle ungeraden Knoten haben Grad 2 in F
- der Pfad von jedem Knoten [mm] v\in [/mm] V(F) zur Wurzel seiner Komponente ist M-alternierend.
Nun betrachten wir also den Fall, dass jeder gerade Knoten in F nur ungerade Knoten von F als Nachbarn hat.
Jeder gerade Knoten (bis auf die Wurzeln) ist ja in einer Matchingkante enthalten, der ersten Kante auf dem Pfad von ihm zur Wurzel der
Komponente, in der er liegt.
Um nun die Aussage
2 [mm] |M|\leq |V|-(O(X)-|X|)\:\:\: (\star)
[/mm]
ausnutzen zu koennen, muessen wir also fuer diesen Fall ein X angeben, so dass
Gleichheit in [mm] (\star) [/mm] gilt.
... Fortsetzung folgt....
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Di 21.03.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
