網絡流問題是一類重要的組合優化問題，它涉及在網絡中最大化或最小化的特定類型的數據傳輸。這個問題的研究通常集中在最大流問題上，即在一個給定的網絡中，確定能夠從一個節點傳遞到另一個節點的最大數據量。
概念
網絡流問題是許多實際問題的一種數學模型，這些實際問題包括物流、水力系統以及配對問題等。網絡被建模為一個帶權重和方向的圖，其中每條邊都有一個最大容量限制。在這個模型中，網絡流必須滿足一定的條件，例如每個非源點和匯點的節點的流入流量等于流出流量，而且源點的流出流量等于匯點的流入流量。
最大流問題
問題描述
最大流問題是指在一個具有n個節點和m條邊的圖中，每條邊都有一個容量限制，需要從一個指定的源點s向一個指定的匯點t輸送物品，可以通過中間節點進行轉運，目標是找到最大的輸送量。
解決方法
為了求解最大流問題，引入了一些關鍵的概念，如反向弧、殘余網絡、增廣路徑和最大流定理。反向弧用于表示已經使用的邊的剩余容量，殘余網絡則是由原始網絡的邊的剩余容量組成的新的網絡。增廣路徑指的是在殘余網絡中從源點s到匯點t的一條路徑，沿著這條路徑可以增加流量。最大流定理表明，如果在殘余網絡中找不到增廣路徑，則當前的流量已經是最大流量。常用的求解最大流問題的算法包括Dinic算法、SAP算法和ISAP算法。
最小割最大流定理
最小割最大流定理指出，最大流的值等于最小割的容量。最小割是指在所有割中，邊權值和最小的割。可以通過在求得最大流之后，在殘余網絡中從源點s開始DFS，標記可達的節點，從而得到最小割。
最小費用最大流問題
最小費用最大流問題是在確保最大流的情況下，同時尋求最小費用的解決方案。在這種情況下，除了流量之外，網絡中的邊還帶有費用。為了實現這一目標，可以在尋找增廣路徑的同時，尋找費用最小的路徑進行增廣，以獲得最小費用的最大流。
參考資料 >
深入理解網絡流問題.知乎專欄.2024-11-21
ILH.博客園.2024-11-21
網絡流問題詳解.CSDN博客.2024-11-21