Diskussion:Max-Flow-Min-Cut-Theorem
aus Wikipedia, der freien Enzyklopädie
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))