最大流問題例題

最大流問題（Maximum Flow Problem）是圖論中的一個經典問題，它的目標是在一個帶有權重的有向圖中，找到一條從源點（source）到匯點（sink）的最大流量路徑。這裡有一個簡單的例子來解釋最大流問題：

假設我們有一個輸油管道網絡，我們想從一個油井（源點）輸送原油到一個煉油廠（匯點）。這個管道網絡由多條管道組成，每條管道都有一定的容量（流量限制）。我們的目標是在不超過每條管道容量限制的前提下，找到一條從油井到煉油廠的最大原油輸送路徑。

例題： 給出一個有向圖G=(V, E)，其中V是頂點集，E是邊集。圖G中有源點s和匯點t。每條邊(u, v)∈E有一個非負數流量上限c(u, v)。請找到一條從源點s到匯點t的最大流量路徑。

例如，給出以下圖G：

      5
s -- 2 -- t
      3

在這個例子中，源點s和匯點t分別用s和t表示，中間的數字表示每條邊的流量上限。我們需要找到一條從s到t的最大流量路徑。

解決這個問題可以使用福特-福克爾（Ford-Fulkerson）算法，它是一種貪心算法，通過不斷找到增廣路徑（augmenting path）來增加流。

步驟如下：

1. 初始時，圖中的所有邊的流量為0。
2. 檢查是否存在從源點s到匯點t的增廣路徑。增廣路徑是指一條不經過反方向的邊的路徑。
3. 如果找到增廣路徑，則沿著這條路徑增加流量，直到達到某個邊的流量上限為止。
4. 重複步驟2和3，直到找不到增廣路徑為止。

對於上面的例子，我們可以這樣找到最大流量：

1. 初始時，流量為0。
2. 找到增廣路徑s -> t，流量上限為2。
3. 增加流量，使得s -> t的流量增加到2。
4. 再次檢查，找到增廣路徑s -> t，流量上限為3。
5. 再次增加流量，使得s -> t的總流量增加到4（因為2 + 3 = 4）。
6. 再次檢查，找不到增廣路徑，停止算法。

因此，從源點s到匯點t的最大流量為4。