Back Teorema de flux màxim tall mínim Catalan Fordova–Fulkersonova věta Czech Max-Flow-Min-Cut-Theorem German Max-flow min-cut theorem English Teoremo pri maksimuma-fluo kaj minimuma-tranĉo Esperanto نظریه جریان بیشینه برش کمینه Persian Théorème flot-max/coupe-min French משפט זרימה מקסימלית - חתך מינימלי HE Maximális folyam – minimális vágás Hungarian 最大フロー最小カット定理 Japanese
Il teorema del flusso massimo e taglio minimo (conosciuto anche come max-flow min-cut) dice che, in una rete di flusso, il massimo flusso passante dalla sorgente (il nodo iniziale) al pozzo (il nodo finale) è uguale alla somma dei pesi degli archi nel taglio minimo.
Si tratta di una generalizzazione del problema primale standard, tipico della programmazione lineare.
Il teorema fu dimostrato da P. Elias, A. Feinstein, e C.E. Shannon nel 1956, e indipendentemente anche da L.R. Ford Jr. e D.R. Fulkerson nello stesso anno.[1]
- ^ P. Elias, A. Feinstein, and C. E. Shannon, A note on the maximum flow through a network, IRE. Transactions on Information Theory, 2, 4 (1956), 117–119