Maximale Flüsse < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:29 Mo 06.02.2006 | | Autor: | Tyr |
| Aufgabe | Lemma: Seien D ein gerichteter Graph und f ein Fluß, sowie X, Y, Z [mm] \subseteq [/mm] V. Dann gilt:
i) f(X.X) = 0
ii) f(X.Y) = -f(X.Y)
iii) f(X [mm] \cup [/mm] Y.Z) = f(X.Z) + f(Y.Z) für X [mm] \cap [/mm] Y = 0
iv) |f| = f(s.V) = f(V.t)
Beweis zu iv) |f| = f(s.V) = f(V.V) - f(V \ s.V) = f(V.V \ s) = f(V.t) + [mm] \summe_{v \in V ohne (s,t)}^{} [/mm] f(V.v) = f(V.t) |
Erklärung: s ist die Quelle und t die Senke.
Wo fängt hier jetzt der eigentliche Beweis an? Also das Ganze ist mir schon irgendwie klar, dass es so ist (alles was aus der Quelle kommt, landet in der Senke und das ist der Wert des Flusses), aber verstehe nicht, warum das ein Beweis ist.
Vielen Dank
Tyr
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich habe es hinbekommen... :)
Also eine Antwort nicht mehr notwenig... Ist nur etwas mit den Variablen rumspielen, wenn man die Regeln dafür hat.
|
|
| |
|
Hallo Tyr,
gut, wenn Du selber die Aufgabe loesen konntest. Du haettest die Loesung ruhig als
Antwort auch hier schreiben koennen, das kann vielleicht anderen helfen.
Deswegen kurz was zur Loesung:
Falls [mm] \{s,t\}\cap X=\emptyset, [/mm]
so erhält man aus der Flusserhaltung fuer alle [mm] v\in V\setminus\{s,t\}
[/mm]
[mm] f(X,X)=\sum_{(u,v)\in E\cap X\times X}f(e)
[/mm]
= [mm] \sum_{u\in X}\sum_{v\in X,(u,v)\in E}f(u,v) [/mm]
= [mm] \sum_{u\in X} (\sum_{(u,v)\in E}f(u,v)\:\: -\sum_{v\in V\setminus X, (u,v)\in E}f(u,v))
[/mm]
= [mm] \sum_{u\in X} f(u,V)\:\: -\sum_{u\in X} f(u,V\setminus [/mm] X)
= [mm] \sum_{u\in X} f(V,u)\:\: -\sum_{u\in X}f(u,V\setminus [/mm] X)
= [mm] \sum_{u\in X} (f(V\setminus X,u)+f(X,u))\:\: -\sum_{u\in X}f(u,V\setminus [/mm] X)
= [mm] f(V\setminus X,X)-f(X,V\setminus [/mm] X)
genau dann, wenn f(X,V)=f(V,X) und dies gilt wg. Flusserhaltung.
Wenn nun zB [mm] s\in [/mm] X und [mm] t\not\in [/mm] X gilt, so kann man [mm] X'=X\setminus\{s\} [/mm] betrachten
und benutzen, dass
val (f) = f(s,V)-f(V,s) = [mm] f(X,V\setminus X)-f(V\setminus [/mm] X,X)
sowie obiges Ergebnis angewandt auf X'.
(iii) folgt meiner Ansicht nach direkt aus der Definition, und (iV) gilt fuer den Fall, dass kein Fluss in s hinein geht (zB, wenn gar keine Kante nach s hinein geht).
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:52 Mi 08.02.2006 | | Autor: | Tyr7 |
Hallo,
So weit bin ich nicht gegangen :)
Habe nur zu der iv) Aussage paar Formeln rumgedreht, bis ich das erwünschte Resultat hatte:
dazu habe ich die iii) erweitert:
iii) f(X [mm] \cup [/mm] Y.Z) = f(X.Z) + f(Y.Z) mit: f(Z.X \ Y) = f(Z.X) - f(Z.Y)
Natürlich gelten auch die umgekehrten Operation (wenn man das so sagen kann), wie aus [mm] \cup [/mm] mach -> \ so wird in der Formel statt plus -> minus.
Beweis für iv)
paar Hilfssachen (im Grunde ganz einfach, nur draufkommen muss man):
V \ (V \ s) = s
V \ s = V \ {s,t} [mm] \cup [/mm] {t}
*) [mm] \summe_{v \in V}^{} [/mm] f(u, v) = 0 für alle u [mm] \in [/mm] V \ {s, t}
nach dieser Regel ergibt f(V.V \ {s.t}) = 0 (ist ja nur anders geschrieben)
|f |=f(s.V) = f(V \ (V \ s).V) = f(V.V) f(V \ s.V) = f(V.V \ s) = f(V.V \ {s.t} [mm] \cup [/mm] {t}) = f(V.V \ {s.t})+ f(V.t). (Vorletzter Schritt Regel *))
=> f(V.t), also das gesuchte Ergebnis
Viele Grüße
Tyr
|
|
|
|
