Kantendisjunkte Wege < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:11 Sa 25.02.2006 | | Autor: | Tyr7 |
| Aufgabe | Satz:
Für eine Menge W = W1 [mm] \cup [/mm] W2 ... Wk von kantendisjunkten (s,t) Wegen sind folgende Aussagen äquivalent:
i) k ist maximal
ii) DW enthält keinen augmentierenden Weg
iii) es existiert ein (s,t) Schnitt mit |A(S,T)| = k
Beweis zu ii) --> iii)
Setze S = (v [mm] \in [/mm] V | es gibt einen augmentierenden Weg in DW). Per Annahme ist (S,T) = (S, V \ S) ein (s,t) Schnitt und für je zwei Knoten u [mm] \in [/mm] S und v [mm] \in [/mm] T gilt (u,v) [mm] \not\in [/mm] AW, da sonst v [mm] \in [/mm] S gelten würde. Damit liegt jede Kante (u,v) [mm] \in [/mm] A mit u [mm] \in [/mm] S und v [mm] \in [/mm] T in einem Weg Wi, da andernfalls (u, v) [mm] \in [/mm] AW. Wenn Wi zwei solche Kanten enthält, so muss Wi auch eine Kante enthalten, die von einem Knoten x [mm] \in [/mm] T zu einem Knoten y [mm] \in [/mm] S führt. Dann ist aber (x, y) [mm] \in [/mm] AW. Widerspruch. Also ist k = |A(S,T)|
|
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
habe mir diesen Beweis jetzt die ganze Zeit angeschaut und denke, dass es endlich verstanden habe, aber würde mich freuen falls es jemand bestätigen könnte, dass mein Überlegung richtig ist. Oder korrigieren falls nicht.
Dazu erstmal paar Erklärungen:
W = W1 [mm] \cup [/mm] W2 ... Wk sein die Kantenmenge von kantendisjunkten Wegen. Wir definieren einen Hilfsgraphen DW=(V, AW) wie folgt:
(u,v) [mm] \in [/mm] Aw, falls [mm] \begin{cases} (u, v) \in A \backslash W \\ (v,u) \in W \end{cases}
[/mm]
Der Hilfsgraph enthält somit alte, noch nicht benutzte, und umorientierte benutzte Kanten.
Jetzt zu dem Beweis:
Also ich möchte zeigen, dass |A(S,T)| genau k ist, wenn es keinen augmentierenden Weg in DW gibt.
Dafür möchte ich ausschliessen, dass ein Weg Wi sozusagen zwei unabhängige Wege (sagen wir W1 und W2) benutzt. Das könnte passieren wenn W1 von S nach T führt, dann ein anderer wieder zurückgeht von T nach S und der W2 wieder von S nach T geht. Denn dann hätte ich k-1 Wege aber der Schnitt |A(S,T)| bleibt gleich. Somit hätte ich k < |A(S,T)|. Das kann aber nicht passieren, da ich in diesem Fall aber einen augmentierenden Weg hätte, der zurück geht (der (x,y) Weg) und das ist gegen die Annahme, dass es keinen solchen Weg gibt.
Ist das soweit richtig? Ansonsten verstehe ich nicht, was "Wenn Wi zwei solche Kanten enthält" bedeuten soll...
Vielen Dank und Viele Grüße
Tyr
|
|
| |
|
Hallo und guten Morgen,
mit dem geschriebenen Beweis von [mm] (ii)\to [/mm] (iii) bin ich fast einverstanden:
Also wir nehmen S wie geschrieben:
[mm] S=\{v\in V\: |\: es\: gibt\: augmentierenden\: Weg\: von s\: nach\: v\}
[/mm]
Dann ist [mm] t\not\in S,s\in [/mm] S
und (S,T) mit [mm] T:=V\setminus [/mm] S ist (s,t)-separierender Schnitt.
Richtig: Jede Kante [mm] (u,v)\in [/mm] A mit [mm] u\in [/mm] S, [mm] v\in [/mm] T liegt in einem der [mm] W_i.
[/mm]
Zum Argument, dass jedes [mm] W_i [/mm] hoechstens eine Kante im Schnitt hat:
Annahme, zwei Kanten von [mm] W_i [/mm] waeren im Schnitt - und jetzt kommt das, wo in der geschriebenen Loesung
ein kleiner Dreher ist-, dann gaebe es eine Rueckwaertskante
[mm] (u,v)\in W_i, u\in [/mm] T, [mm] v\in [/mm] S, wir nehmen an, die Kante (v,u) sei in keinem [mm] W_j [/mm] mit [mm] j\neq [/mm] i.
Dann waere aber [mm] (v,u)\in [/mm] AW, und wegen [mm] v\in [/mm] S muesste dann [mm] u\in [/mm] S gelten - Widerspruch.
Also: zum einen war da ein notationeller Dreher, zum anderen muss man so argumentieren wie hier.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:52 Di 28.02.2006 | | Autor: | Tyr7 |
Hallo Mathias,
vielen Dank :) Wiedermal ein kleines Aha Erlebnis...
Viele Grüße
Tyr
|
|
|
|
