跳轉到內容
- 弧上的權重稱為容量。
- 網路的起點稱為源（S）；網路的終點稱為匯點（T）。
- 承載其全部容量的弧被稱為飽和的。
- 割是指將 S 與 T 分開的連續線，並且不穿過任何節點。
- 除了 S 和 T 之外，流入一個節點的流量總和必須等於流出該節點的流量總和。
- 最大流 - 最小割定理
- 透過網路的流量不能超過任何割的價值。
- 最大流量等於最小割的價值。
- 這意味著，如果您能夠透過觀察找到具有相同值的流量和割，那麼最大流 - 最小割定理告訴您，您已經獲得了最大流量。
- 標記過程透過系統地增加任何初始流量來找到最大流量
- 以任何初始流量或零流量開始。
- 用兩條弧替換每條弧：一條顯示流量可以增加的量（其剩餘容量），另一條顯示流量可以減少的量（其潛在迴流）。
- 如果 S 仍然與 T 相連，則找到從 S 到 T 的新流量，並根據需要更改剩餘容量和潛在迴流。
- 重複步驟 3，直到 S 與 T 斷開連線。
- 如果 S 與 T 斷開連線，則最大流量是步驟 1 和 3 中所有流量的總和。
- 如果網路具有多個源，則建立一個新的超級源；如果它具有多個匯點，則建立一個新的超級匯點。
- 如果節點具有限制的容量，則用兩個無限制的節點替換它，這兩個節點透過具有相關容量的弧連線。
- 對於弧具有上限和下限容量的網路，割的價值為
- 從 S 到 T 方向穿過割線的上限容量的總和減去從 T 到 S 方向穿過割線的下限容量的總和。
- 對於這樣的網路，對於標記過程，迴流使用最小容量計算。例如，對於一條上限容量為 8、下限容量為 1 的弧上的流量 5，剩餘容量為 3，潛在迴流為 4。
