Diskussion:Max-Flow-Min-Cut-Theorem

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 1 Jahr von DrLemming in Abschnitt Lineare Optimierung und Dualität
Zur Navigation springen Zur Suche springen

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)Beantworten


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)Beantworten
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)Beantworten


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))Beantworten


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

DrLemming (Diskussion) 11:47, 22. Apr. 2023 (CEST)Beantworten