Diskussion:Max-Flow-Min-Cut-Theorem
Beim ersten Schnitt wird die kante (o,p) nicht mitgezählt. Warum ?
- Ihre Kapazität in Flussrichtung ist 0. Polopower Diskussion:Max-Flow-Min-Cut-Theorem#c-Polopower-2009-01-13T17:37:00.000Z11
Warum gibt es nicht auch noch den minimalen Schnitt S = {s},T = {p,o,q,r,t} ?
- c(s,o) + c(s,p) = 3 + 2 = 5
- Ist der Satz so richtig formuliert? Problem: Punkt 3. |f| soll doch sicher der Wert des Flusses sein,oder?
- Das Beispiel widerspricht dem?
- Laut Anmerkung im Beispiel, ist der Schnitt S1={s,o,p,r} , Q1 ={q,t} nicht minimal. Er hat Kapazität 6.
- Die anderen Schnitte haben Kapazität 5. Der Wert des maximalen Flusses ist ebenfalls 5.
- Also ist doch 5=|f|<6= c(S1,Q1). Somit 3. verletzt.
- Vorschlag: |f|=min{c(S,Q), (S,Q) ist Schnitt}. Oder irre ich? --88.75.117.97 Diskussion:Max-Flow-Min-Cut-Theorem#c-88.75.117.97-2009-08-31T18:00:00.000Z-Polopower-2009-04-04T18:19:00.000Z11
Ist in der Beweisskizze unter 2.=>3. in der zweiten Zeile mit c(S,T) die Kapazizät
im residualen Netzwerk gemeint, in der dritten Zeile aber die des ursprünglichen Graphen?
M.E. ergibt es nur dann Sinn, aber es sollte dann in der Darstellung sauber unterschieden
werden. (nicht signierter Beitrag von Stefan1971HH (Diskussion | Beiträge) Diskussion:Max-Flow-Min-Cut-Theorem#c-Stefan1971HH-2016-02-19T17:25:00.000Z11)
Lineare Optimierung und Dualität
[Quelltext bearbeiten]Der hier besprochene Satz scheint mir ein Spezialfall aus der linearen Optimierung zu sein: Lineare Optimierung#Der starke Dualitätssatz11
DrLemming (Diskussion) Diskussion:Max-Flow-Min-Cut-Theorem#c-DrLemming-20230422094700-Lineare Optimierung und Dualität11