Ich glaube, hier gibt es direkt zwei sprachbasierte Missverständnisse, wobei das eine aus dem anderen folgt:
Daraus, dass (s,V\s) nicht der saturierte Schnitt ist, haben Sie zuerst geschlossen, dass dann (V\t,t) der Schnitt sein muss
Nein, die Idee war bei mir, dass, wenn (s,V\s) ein saturierter Schnitt wäre und es noch einen saturierten Schnitt irgendwo im Graphen gäbe (schließt sich ja nicht aus, beispielsweise in einem großen Graphen, bei dem jede Kante saturiert ist, gäbe es häufig eine große Menge an validen saturierten Schnitten), man eventuell alle Kanten des Residualgraphen umdrehen könnte um den saturierten Schnitt mit maximalem S (und minimalem T) zu bekommen. Inzwischen ist mir jedoch auch klar, dass das im Sinne der Aufgabenstellung jedoch nicht gefordert ist, da es ja zum Beweis der Optimalität langt, wenn es in jedem Schritt (und damit auch im letzten Schritt) irgendeinen saturierten Schnitt gibt.
und daraus, dass es beide nicht unbedingt sein müssen, schließen sie jetzt, dass es in gewissen Fällen gar keinen gibt?
Hier liegt das Problem darin, dass Sie auf die Frage "D.h. es ist korrekt, wenn der saturierte Schnitt im Falle, dass die Gesamtkapazität der aus s herausgehenden Kanten größer ist als die Gesamtkapazität der in t hineingehenden Kanten, einfach bei (s,V\s) bleibt?" mit nein geantwortet haben (was auch korrekt ist ohne meine folgende Ergänzung, bei der ich dachte, ich hätte sie erwähnt, aber wohl dann doch vergessen hatte). Ich meinte jedoch den Fall, dass es auch einen gültigen Fluss von s nach t gibt, der der ausgehenden Gesamtkapazität aus s entspricht. In diesem Fall würde der Algorithmus nie nach s zurück pushen und damit wäre (s,V\s) immer der gefundene saturierte Schnitt.
Wegen des Neins kam ich dann auf die Fehlinterpretation Ihrer Aussage "Der Schnitt minimaler Kapazität muss weder (s,V\s) noch (V\t,t) sein." im englischen Sinne "The cut of minimal capacity must neither be (s,V\s) nor (V\t,t)." (was aber im deutschen eigentlich "darf weder" heißen würde da "must not" = "darf nicht"), was ja dann wiederum falsch gewesen wäre - daher mein letzter Post.
Noch kurz des Verständnisses halber: Mit ihrer Aussage meinten sie einfach nur, dass ein saturierter Schnitt sich auch irgendwo anders im Graph befinden kann (nicht muss!). Bildlich würde das bedeuten, dass der maximale Fluss von s nach t dann durch diesen Schnitt gedrosselt werden würde (auf den aufsummierten Fluss aller Kanten von S nach T). Korrekt?
Es tut mir Leid, dass ich das so missverstanden habe und Ihnen deshalb solche Umstände gemacht habe. Vielen Dank für Ihre Geduld.
