Minimale Flüsse in Netzwerken < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:31 So 11.12.2005 | | Autor: | Milamber |
Erstmal ein "Hallo" an alle, denn ich bin neu hier und dies ist mein erster Post :)
Mir wurde folgende Aufgabe gestellt, bei der ich noch nicht so recht weiterkomme:
Sei (G,u,s,t) ein Netzwerk. Weiter seien [mm] \delta^+(X) [/mm] und [mm] \delta^+ [/mm] Y
minimale s-t-Schnitte in (G,u). Zeigen Sie, dass [mm] \delta^+(X \cup [/mm] Y) und
[mm] \delta^+(X \cap [/mm] Y) ebenfalls minimale s-t-Schnitte in (G,u) sind.
Nun habe ich mir überlegt, ich könnte die Schnittkapazität für z.B.
[mm] \delta^+(X \cap [/mm] Y) einmal hinschreiben und die Voraussetzung benutzen...
[mm] \summe_{e \in \delta^+(X \cap Y)} [/mm] u(e) =
[mm] \summe_{e \in \delta^+(X)} [/mm] u(e) + [mm] \summe_{e \in \delta^+(Y)} [/mm] u(e)
- [mm] \summe_{e \in \delta^+(X \cup Y)} [/mm] u(e)
- [mm] \summe_{e \in E^+(X, Y)} [/mm] u(e)
- [mm] \summe_{e \in E^+(Y, X)} [/mm] u(e)
Aber nun sehe ich leider nicht, wie ich weiterkomme...
Kann mir da jmd. helfen oder mir evtl. einen anderen Ansatz verraten?
Milamber
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Milamber,
man kann sich fuer [mm] X\cap [/mm] Y das z.B. wie folgt klar machen: Man schaue sich an, dass
von [mm] X\cap [/mm] Y ja etwas nach [mm] V\setminus (X\cup [/mm] Y), etwas nach [mm] Y\setminus [/mm] X und etwas nach
[mm] X\setminus [/mm] Y fliessen kann.
Das von [mm] X\cap [/mm] Y nach [mm] V\setminus (X\cup [/mm] Y) zaehlt man ja bei X bzw. Y auch jeweils mit.
Das von [mm] X\cap [/mm] Y nach [mm] Y\setminus [/mm] X zaehlt bei X auch mit, und das von
[mm] X\cap [/mm] Y nach [mm] X\setminus [/mm] Y ist - fuer X - kleiner oder gleich dem , was aus [mm] X\setminus [/mm] Y wieder rausfliesst - Vorauss.: Nimm einen maximalen Fluss, dann MaxFlow-MinCut.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:25 Mo 12.12.2005 | | Autor: | Milamber |
Super, genau so etwas habe ich gebraucht. Ich habe den Beweis gerade mal skizziert und ich glaube, ich habs hinbekommen. Vielen Dank!
Milamber
|
|
|
|
