[erledigt] Folie 116 (Beweis ex. Nachbarschaft bei Matching)

Moderator: Optimierungsalgorithmen

MrGumby
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 16. Apr 2013 15:07

[erledigt] Folie 116 (Beweis ex. Nachbarschaft bei Matching)

Beitrag von MrGumby »

Hallo,

bei Folie 116 (Beweis der exakten Nachbarschaft bei Matching) steht beim dritten Aufzählungspunkt \(|(M_1\triangle p)|\ >\ |M_1|\). Soweit ich das verstanden habe, soll doch p der verbessernde Pfad sein, mithilfe dessen ich aus \(M_1\ M_2\) gewinnen kann. Warum wird hier dann die symmetrische Differenz gebildet? Gehe ich richtig in der Annahme, dass gemeint ist, dass "p auf \(M_1\) angewendet wird". Also das was hier: https://de.wikipedia.org/wiki/Matching_ ... sverfahren mit \(\bigoplus\) bezeichnet wird? Und ist dann \(M_1\bigoplus p = M_2\)?

Danke
Zuletzt geändert von MrGumby am 11. Nov 2015 15:25, insgesamt 1-mal geändert.

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Folie 116 (Beweis exakte Nachbarschaft bei Matching)

Beitrag von Prof. Karsten Weihe »

MrGumby hat geschrieben: bei Folie 116 (Beweis der exakten Nachbarschaft bei Matching) steht beim dritten Aufzählungspunkt \(|(M_1\triangle p)|\ >\ |M_1|\). Soweit ich das verstanden habe, soll doch p der verbessernde Pfad sein, mithilfe dessen ich aus \(M_1\ M_2\) gewinnen kann.
Ja, ist so gedacht.
MrGumby hat geschrieben: Warum wird hier dann die symmetrische Differenz gebildet? Gehe ich richtig in der Annahme, dass gemeint ist, dass "p auf \(M_1\) angewendet wird".
Wir wollen ja \(M_1\) dadurch verändern, dass entlang \(p\) die ungematchten Kanten gematcht und die gematchten Kanten ungematcht werden. Ich nehme an, das meinen Sie mit "p auf \(M_1\) angewendet". Welche Kanten sind im resultierenden Matching enthalten: einerseits die Kanten von \(M_1\), die nicht auf \(p\) liegen, denn bei denen ändert sich nichts; andererseits die Kanten von \(p\), die vorher ungematcht waren, also nicht zu \(M_1\) gehören. In Kurzform: einerseits \(M_1\setminus p\), andererseits \(p\setminus M_1\). Beide Mengen zusammen ergeben genau \(M_1\triangle p\).
MrGumby hat geschrieben: Also das was hier: https://de.wikipedia.org/wiki/Matching_ ... sverfahren mit \(\bigoplus\) bezeichnet wird?
An der Formel mit \(\bigoplus\) an besagter Fundstelle hängt eine Fußnote: "\(\bigoplus\) notiert die symmetrische Differenz". :)
MrGumby hat geschrieben: Und ist dann \(M_1\bigoplus p = M_2\)?
Nein: \(M_1\) und \(M_2\) sind zwei beliebige Matchings mit \(|M_1|<|M_2|\), das heißt, \(M_1\) und \(M_2\) unterscheiden sich in der Regel um weit mehr als nur einen einzelnen Pfad. Wir wollen in diesem Beweis ja nicht von \(M_1\) zu \(M_2\) kommen, sondern wir wollen "nur" zeigen, dass ein augmentierender Pfad \(p\) für \(M_1\) existiert. Dafür haben wir \(M_2\) in Gedanken hergenommen, aber eigentlich interessiert uns \(M_2\) nicht. Wenn Sie so wollen ist \(M_1\bigoplus p\) ein erster Schritt auf dem (uns nicht interessierenden) Gesamtweg von \(M_1\) nach \(M_2\).

Klarer geworden?

KW

MrGumby
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 16. Apr 2013 15:07

Re: Folie 116 (Beweis exakte Nachbarschaft bei Matching)

Beitrag von MrGumby »

Ja, vielen Dank, jetzt ist es klarer.

Antworten

Zurück zu „Optimierungsalgorithmen“