Matching < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:09 Sa 04.03.2006 | | Autor: | Tyr7 |
| Aufgabe | Der Algorithmus:
Ausgehend von einem Wald F, der nur aus exponierten Knoten besteht, wählen wie einen geraden Knoten u [mm] \in [/mm] V(F) und betrachten einen Nachbarn v [mm] \in [/mm] N(u) in G. WIr unterscheiden drei Fälle:
i) v [mm] \not\in [/mm] V(F), insbesondere ist dann v nicht exponiert. Füge die Kante (u, v) sowie die zu v inzidente Matchingskante zu F hinzu.
ii) v [mm] \in [/mm] V(F) gerade und in einer anderen Zusammenhangskomponente als u, dann bildet P(u),(u,v),P(v) einen augmentierenden Weg
iii) v [mm] \in [/mm] V(F), gerade und in der selben Zusammenhangskomponente wie u: sei x der erste Knoten in P(u) [mm] \cap [/mm] P(v) von u aus gesehen. Dann ist x ebenfalls ein gerader Knoten, da x entweder die Wurzel oder Grad mindestens drei hat. Dann bilden die Anfangsstücke von P(u) und P(v) bis x zusammen mit (u,v) eine Blüte, die wir schrumpfen.
Wenn keiner dieser Fälle eintritt, hat jeder Knoten in V(F) nur ungerade Knoten als Nachbarn. In diesem Falle hat das Matching maximale Kardinalität |
Hallo zusammen,
das ist jetzt die zweite Version meiner Frage, da nach dem Lesen eines Buches von Distel paar Sachen klar geworden sind :)
Nur leider nicht das wichtigste... Wie erstelle ich so einen alternierenden wald, so dass die Bedingungen, die an den Wald gestellt werden, stimmen?
Dazu mal ein einfaches Beispiel:
a b c d
o-----o-----o-----o
Das ist der Graph, maximales Matching sieht ja so aus g______u-----------g_______u
wobei u für ungerade Knoten steht, g für gerade...
_ Matching Kante
- Nichtmatching Kante
Wie ich es mache:
am Anfang sind alle Knoten exponiert:
a
b
c
d
Dann einen beliebigen Knoten, der nicht exponiert und gerade ist, aussuchen, also z.B. b
Nachbar suchen, also c, ebenfalls nicht exponiert
a
b------c
d
dann d ausgewählt
a
d------c____b
und a
a-----b_____c------d
Das Problem ist, dass d ungerade ist, aber nach den Regeln, haben ungerade Knoten den Grad 2, was hier nicht stimmt.
der Wald müsste so aussehen:
a-------b______c
d
damit es den Regeln entspricht.
Aber wie komme ich aus so einem Wald dazu, ein maximales Matching zu berechnen? Irgendwie kann ich hier nicht so viel sehen, wie in meiner Version....
Und noch wichtiger: wie baue ich so einen Wald auf?
Noch eins:
Wie kann der Fall i) eintreten, dass v [mm] \not\in [/mm] V(F) ist wenn der Wald am Anfang aus exponierten Knoten besteht (also alle) und später die Knoten nur verschoben werden. Nach meiner Meinung sind zu allen Zeitpunkten alle Knoten von G in F drin.
Für jede Hilfe bin ich sehr dankbar!
Viele Grüße
Tyr
|
|
| |
|
Hallo und guten Morgen,
also der Algorithmus von Edmonds haelt ja in jedem Schritt ein Matching M und einen M-alternierenden Wald F,
so dass also die Wurzeln der Bäume von F (=Zush.Komp.) nicht in M sind (falls alle [mm] v\in [/mm] V in Matching-Kanten sind, ist
das Matching perfekt). Zu geg. Matching M, das noch nicht alle Knoten ueberdeckt, kann man F konstruieren:
Starte mit einem Knoten v, der noch nicht durch M ueberdeckt wird. Ausgehend von solch einem Knoten wird der Wald F
solange konstruiert, bis M vergroessert werden kann oder dies nicht mehr moeglich ist. Die Konstruktion hast Du schon beschrieben:
Falls es einen Nachbarn von v gibt, der in keiner Matching-Kante ist: Nimm die Kante hinzu zu M und starte neu mit einem nun noch nicht
ueberdeckten Knoten.
Sonst mache sozusagen eine ''Alternierender-Pfad''-Suche von v aus.
An Deinem Bsp:
a b c d
o-----o-----o-----o
Starte mit [mm] M=\emptyset.
[/mm]
Waehle zB b und als ersten Nachbarn c, dann fuege [mm] \{b,c\} [/mm] zu M hinzu:
[mm] \in [/mm] M
o-----o=====o-----o
Nun nimm a als noch nicht ueberdeckten Knoten,
Nachbarn b, dann so weiter, bis
der alternierende Pfad a-b-c-d gefunden ist.
Dann ersetze
o-----o=====o-----o
durch
o=====o-----o=====o
und dann terminiere (es gibt keinen Knoten mehr, der nicht von M ueberdeckt ist).
Vorerst viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:08 Mo 06.03.2006 | | Autor: | Tyr7 |
Hallo und guten Morgen,
Meine Frage bezieht sich hauptsächlich auf diesen Wald...
> Sonst mache sozusagen eine ''Alternierender-Pfad''-Suche
> von v aus.
Diese Suche mache ich doch anhand von dem alternierenden Wald, den ich aufbaue?
> Nun nimm a als noch nicht ueberdeckten Knoten,
> Nachbarn b, dann so weiter, bis
> der alternierende Pfad a-b-c-d gefunden ist.
Wenn aber dieser Pfad aus vier Knoten in dem Wald ist, dann entspricht er nicht der Definition von einem alternierenden Wald, d.h. dass jeder ungerade Knoten Grad 2 also auch einen Nachfolger hat. Ich habe bei d aber keine Nachfolger mehr...
Wie würde der Wald aussehen in dem letzten Schritt, bevor ich die Augmentierung durchführe und die Kanten {a,b} und {c,d} als Matchingkanten setze?
Irgendwie schaffe ich es nicht diesen Wald so aufzubauen, so dass er den Regeln entspricht.
Vielen Dank und viele Grüße
Tyr
|
|
|
| |
|
Hallo nochmal,
das ist dann die Ausnahme, dass es keinen freien Knoten mehr gibt.
Und da wird der Wald ja auch nicht mehr geaendert.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:29 Mo 06.03.2006 | | Autor: | Tyr7 |
Hallo und herzlichen Dank :)
achso... Ich dachte, dass ich jetzt den Wald mit Gewalt in die richtige Form bringen muss... Aber wenn Ausnahmen erlaubt sind, wenn es nicht anders geht, da kann ich weiter machen.
Ich versuche mich jetzt mal an paar komplizierteren Beispielen, da jetzt alles etwas klarer wurde :)
Viele Grüße
Tyr
|
|
|
|
