Diskussion:Max-Flow-Min-Cut-Theorem
Letzter Kommentar: vor 1 Jahr von DrLemming in Abschnitt Lineare Optimierung und Dualität
Beim ersten Schnitt wird die kante (o,p) nicht mitgezählt. Warum ?
- Ihre Kapazität in Flussrichtung ist 0. Polopower 18:37, 13. Jan. 2009 (CET)
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
- c(s,p) = 3 ;-) Polopower 20:19, 4. Apr. 2009 (CEST)
- 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 20:00, 31. Aug. 2009 (CEST)
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) 18:25, 19. Feb. 2016 (CET))
Lineare Optimierung und Dualität[Quelltext bearbeiten]
Der hier besprochene Satz scheint mir ein Spezialfall aus der linearen Optimierung zu sein: https://de.wikipedia.org/wiki/Lineare_Optimierung#Der_starke_Dualitätssatz