--- Begin Message ---
- From: "Markus Dunkel" <markusdunkel@xxxxxxxxxx>
- To: "Philipp Kirchner" <mail@xxxxxxxxxxxxxxxxxx>, <sbothe@xxxxxx>
- Date: Mon, 13 Jan 2003 18:07:15 +0100
Hab ne grobe Idee für die Aufgabe 1)b). Wahrscheinlich ist sie falsch, aber immerhin eine Idee...:) Annahme: Jedes nicht-erweiterbare Matching hat weniger als halb so viele Kanten wie ein maximales Matching. Für ein beliebiges maximlaes Matching M_max in G gilt: Es existiert kein M-augmentierender Pfad. D.h. für einen Pfad P sind die Endknoten nicht M-frei, also im Matching enthalten. Sei P= v_0, v_1, v_2, ... , v_n-1, v_n Dann gilt (v_0, v_1) \in M, (v_1, v_2) \notin M, ... , (v_n-1, v_n) \in M. Entfernt man auf P nun mehr als die Hälfte der Kanten aus dem maximalen Matching, um ein nicht-erweiterbares Matching zu erhalten, so liegen mindestens drei benachbarte Kanten nicht im Matching. Davon kann man nun die mittlere Kante auswählen, um das nicht-erweiterbare Matching zu erweitern. Widerspruch! q.e.d. (???????????) Naja, ich weiß ja nicht... das mit dem P is'n bisschen komisch, aber vielleicht is'es ja doch richtig...? mfg Markus
--- End Message ---
