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

[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

[Prof. Karsten Weihe]

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.

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\).

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".

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]

Ja, vielen Dank, jetzt ist es klarer.