DSA 最大流

最大流問題

最大流問題是關於在一個有向圖中，找到從一個點到另一個點的最大流量。

更具體地說，流量來自源頂點 \(s\)，最終到達匯頂點 \(t\)，圖中的每條邊都定義了流量和容量，容量是指該邊所能擁有的最大流量。

找到最大流可能非常有用

• 用於規劃城市道路以避免未來的交通擁堵。
• 評估移除供水管道、電纜或網路電纜的影響。
• 找出流網路中擴充套件容量將帶來最高最大流的位置，目的是增加例如交通、資料流量或水流量。

術語和概念

流網路通常是指有流量流過的有向圖。

邊的容量 \(c\) 告訴我們允許透過該邊的流量是多少。

每條邊還有一個流量值，表示該邊的當前流量。

上圖中的邊 \( v_1 \rightarrow v_2 \)，從頂點 \( v_1 \) 到頂點 \( v_2 \)，其流量和容量描述為 0/7，表示流量為 0，容量為 7。因此，這條邊的流量最多可以增加到 7，但不能再多。

最簡單的形式，流網路有一個源頂點 \(s\)，流量從這裡流出，一個匯頂點 \(t\)，流量在這裡彙集。其他頂點只是讓流量透過。

對於除 \(s\) 和 \(t\) 之外的所有頂點，都有流量守恆，這意味著進入頂點的流量必須與離開頂點的流量相同。

最大流是透過 Ford-Fulkerson 或 Edmonds-Karp 等演算法找到的，透過在流網路中的邊上傳送越來越多的流量，直到邊的容量使得不再能傳送更多流量。這樣一條可以傳送更多流量的路徑稱為增廣路徑。

Ford-Fulkerson 和 Edmonds-Karp 演算法是使用一種稱為殘餘網路的工具來實現的。這將在接下來的頁面中更詳細地解釋。

殘餘網路用每條邊的殘餘容量設定，其中邊的殘餘容量是該邊的容量減去流量。因此，當一條邊的流量增加時，其殘餘容量就以相同的數量減少。

對於殘餘網路中的每條邊，還有一個反向邊，其方向與原邊相反。反向邊的殘餘容量等於原邊的流量。反向邊對於在最大流演算法中將流量沿某條邊傳送回很有用。

下圖顯示了本頁頂部模擬圖中的反向邊。每條反向邊都指向相反的方向，並且由於一開始圖中沒有流量，因此反向邊的殘餘容量為 0。

這些概念中的一些，例如殘餘網路和反向邊，可能很難理解。這就是為什麼在接下來的兩頁中將更詳細地解釋這些概念並提供示例。

當找到最大流時，我們會得到一個關於流網路總共可以傳送多少流量的值。

多個源頂點和匯頂點

Ford-Fulkerson 和 Edmonds-Karp 演算法需要一個源頂點和一個匯頂點才能找到最大流。

如果圖中存在多個源頂點或多個匯頂點，則需要修改圖以找到最大流。

要修改圖以便可以在其上執行 Ford-Fulkerson 或 Edmonds-Karp 演算法，如果存在多個源頂點，則建立一個額外的超級源頂點；如果存在多個匯頂點，則建立一個額外的超級匯頂點。

從超級源頂點，建立到原始源頂點的邊，容量為無窮大。類似地，從匯頂點建立到超級匯頂點的邊，容量也為無窮大。

下圖顯示了這樣一個圖，其中有兩個源 \(s_1\) 和 \(s_2\)，以及三個匯 \(t_1\)、\(t_2\) 和 \(t_3\)。

要在該圖上執行 Ford-Fulkerson 或 Edmonds-Karp，會建立一個超級源 \(S\)，並與原始源節點之間建立容量為無窮大的邊；同時建立一個超級匯 \(T\)，並與原始匯節點之間建立容量為無窮大的邊。

Ford-Fulkerson 或 Edmonds-Karp 演算法現在可以透過從超級源 \(S\) 到超級匯 \(T\) 的路徑，找到具有多個源頂點和匯頂點的圖中的最大流。

最大流最小割定理

要理解這個定理，我們首先需要知道什麼是割。

我們建立兩個頂點集：一個僅包含源頂點，稱為“S”，另一個包含所有其他頂點（包括匯頂點），稱為“T”。

現在，從源頂點開始，我們可以透過包含相鄰頂點來擴充套件集合 S，並繼續包含相鄰頂點，只要不包含匯頂點即可。

擴充套件集合 S 將縮小集合 T，因為任何頂點都屬於集合 S 或集合 T。

在這種設定下，當所有頂點都屬於集合 S 或集合 T 時，集合之間就存在一個“割”。割由所有從集合 S 指向集合 T 的邊組成。

如果我們加總從集合 S 指向集合 T 的所有邊的容量，我們就得到了割的容量，這就是該割中從源到匯的總可能流量。

最小割是具有最低總容量的割，這將是瓶頸。

下圖中，對本頁頂部模擬圖中的圖進行了三種不同的割。

割 A：此割的集合 S 中包含頂點 \(s\) 和 \(v_1\)，其他頂點屬於集合 T。此割中離開集合 S 的邊（從匯到源）的總容量為 3+4+7=14。我們不計算邊 \(v_2 \rightarrow v_1\) 的容量，因為這條邊是反向的，從匯到源。因此，穿過割 A 的最大可能流量為 14。

割 B：割 B 的最大可能流量為 3+4+3=10。

割 C：割 C 的最大可能流量為 2+6=8。如果我們檢查圖中的所有其他割，都不會找到容量更低的割。這就是最小割。您是否執行過本頁頂部的最大流模擬？那麼您也知道 8 是最大流，這正是最大流最小割定理所說的。

最大流最小割定理表明，找到圖中的最小割與找到最大流是相同的，因為最小割的值將與最大流的值相同。

最大流最小割定理的實際意義

使用 Ford-Fulkerson 等演算法找到圖中的最大流也有助於我們理解最小割在哪裡：最小割將是邊已達到滿容量的地方。

最小割是瓶頸所在，因此如果我們想增加超過最大限制的流量，這在實際情況中很常見，那麼我們現在就知道圖中的哪些邊需要修改才能增加整體流量。

修改最小割中的邊以允許更大的流量在許多情況下都非常有用

• 可以實現更好的交通流量，因為城市規劃者現在知道在哪裡建立額外的車道，在哪裡重新規劃交通，或者在哪裡最佳化交通訊號。
• 在製造業中，可以透過針對瓶頸進行改進來提高產量，例如升級裝置或重新分配資源。
• 在物流中，瞭解瓶頸在哪裡，可以透過更改路線或增加關鍵點的容量來最佳化供應鏈，確保商品更有效地從倉庫運往消費者。

因此，使用最大流演算法找到最小割，可以幫助我們理解系統在哪裡可以進行修改以允許更高的吞吐量。

最大流問題的數學描述

最大流問題不僅僅是計算機科學中的一個主題，它也是一種數學最佳化型別，屬於數學領域。

如果您想在數學上更好地理解這一點，以下將用數學術語描述最大流問題。

圖中所有邊 (\(E\))，從頂點 (\(u\)) 到頂點 (\(v\))，其流量 (\(f\)) 小於或等於該邊 (\(c\)) 的容量

\[ \forall (u,v) \in E: f(u,v) \leq c(u,v) \]

這基本上意味著邊的流量受該邊的容量限制。

此外，對於所有邊 (\(E\))，從 \(u\) 到 \(v\) 的單向流量與從 \(v\) 到 \(u\) 的反向負流量相同

\[ \forall (u,v) \in E: f(u,v) = -f(v,u) \]

下面的表示式說明，除了源頂點 (\(s\)) 和匯頂點 (\(t\)) 之外，所有頂點 (\(u\)) 都保持流量守恆

\[ \forall u \in V \setminus \{s,t\} \Rightarrow \sum_{w \in V} f(u,w) = 0 \]

這基本上意味著進入頂點的流量與離開該頂點的流量相同（源頂點和匯頂點除外）。

最後，所有離開源頂點 \(s\) 的流量都必須在匯頂點 \(t\) 處結束

\[ \sum_{(s,u) \in E} f(s,u) = \sum_{(v,t) \in E} f(v,t) \]

上面的等式說明，將所有流出源頂點邊的流量相加，將得到與將所有流入匯頂點邊的流量相加相同的總和。