最大流量定義

最大流量（Maximum Flow）是一個網路流（Network Flow）問題中的一個概念。在圖論中，最大流量問題是指在一個帶有權重的有向圖（通常稱為流量圖）中，找到一條從源點（Source）到匯點（Sink）的最大流量路徑。這裡的「流量」可以理解為在某一段邊上可以通過的最大物質量或信息量。

最大流量問題的定義如下：

給定一個有向圖G = (V, E)，其中V是頂點集，E是邊集。在圖中，存在一個源點s ∈ V 和一個匯點t ∈ V。每條邊(u, v) ∈ E都有一個非負數權重c(u, v)，表示從頂點u到頂點v的邊的容量（capacity）。

問題是找到一組從源點s到匯點t的路徑，使得這些路徑上的邊的流量總和最大，同時保證每條邊的流量不超過它的容量。這裡的流量是指通過每條邊的實際物質量或信息量。

最大流量問題可以用福特-弗洛森算法（Ford-Fulkerson algorithm）來解決，它是一個貪心算法，可以找到從源點到匯點的最大流量路徑。最大流量問題在許多領域都有應用，如交通網絡、數據傳輸、資源分配等。