流量網路（flow network）

想像一套單向水管系統，把源頭的抽水機接到排水口。每根管子每秒只能輸送一定的水量，接頭不能儲水，而你想盡量把水從抽水機推到排水口。流量網路就是這幅景象的數學版本，而它能描述的遠不只是水：道路上的車流、網際網路上的封包、供應鏈中的貨物，甚至把工人配對到工作。

形式上，流量網路是一個有向圖 G = (V, E)，外加兩個特殊頂點：源點 s 與匯點 t。每條邊 (u, v) 帶一個非負容量 c(u, v) >= 0，代表這條邊最多能承載多少。一個流（flow）給每條邊指定一個數值 f(u, v)，滿足 0 <= f(u, v) <= c(u, v)（不能超過管子的容量），且在 s 與 t 以外的每個頂點，流入總量必須等於流出總量（接頭既不製造也不消滅流量）。目標通常是把流的值（value）極大化，也就是離開 s 的淨流量；由守恆律，這恰等於抵達 t 的淨流量。

流量網路之所以重要，是因為單一個乾淨的模型涵蓋了一大族問題，而這個模型還配上一套優美的理論：最大流最小割定理把最佳可能的流與最便宜地切斷 s 到 t 的方法綁在一起，而高效演算法（埃德蒙茲-卡普、Dinic）能在多項式時間內求解。實務上的功夫在於建模：把排程、選取或匹配問題化為一個網路，使它的最大流恰好回答原問題。一個值得記住的慣例：容量通常只給在存在的邊上；不存在的邊視為容量 0。