Our website is made possible by displaying online advertisements to our visitors.
Please consider supporting us by disabling your ad blocker.
Max-Flow-Min-Cut-Theorem
Auf dem Gebiet der Graphentheorie bezeichnet das Max-Flow-Min-Cut-Theorem einen Satz, der eine Aussage über den Zusammenhang von maximalen Flüssen und minimalen Schnitten eines Flussnetzwerkes gibt. Der Satz besagt:
- Ein maximaler Fluss im Netzwerk hat genau den Wert eines minimalen Schnitts.
Der Satz ist eine Verallgemeinerung des Satzes von Menger. Er wurde im Jahr 1956 unabhängig von L.R. Ford Jr. und D.R. Fulkerson, sowie von P. Elias, A. Feinstein und C.E. Shannon bewiesen.[1][2]
- ↑ L.R. Ford Jr., D.R Fulkerson: Maximal flow through a network. In: Canad. J. Math. 8. Jahrgang, 1956, S. 399–404, doi:10.4153/CJM-1956-045-5 (math.ca [PDF]). Vorlage:Cite journal: Der Parameter language wurde bei wahrscheinlich fremdsprachiger Quelle nicht angegeben.
- ↑ P. Elias, A. Feinstein, C.E. Shannon: Note on Maximum Flow Through a Network. In: IRE Trans. on Information Theory, IT. 2. Jahrgang, Nr. 4, 1956, S. 117–119, doi:10.1109/TIT.1956.1056816 (ece.rice.edu ( des vom 4. März 2016 im Internet Archive) [abgerufen am 3. September 2013]). Vorlage:Cite journal: Der Parameter language wurde bei wahrscheinlich fremdsprachiger Quelle nicht angegeben.
Previous Page Next Page
Teorema de flux màxim tall mínim Catalan Fordova–Fulkersonova věta Czech Max-flow min-cut theorem English Teoremo pri maksimuma-fluo kaj minimuma-tranĉo EO نظریه جریان بیشینه برش کمینه FA Théorème flot-max/coupe-min French משפט זרימה מקסימלית - חתך מינימלי HE Maximális folyam – minimális vágás Hungarian Teorema del flusso massimo e taglio minimo Italian 最大フロー最小カット定理 Japanese
