網路就是一張帶容量的圖
你早已認識圖是由邊連起來的頂點，而在最短路徑那一階，你在每條邊上放一個數字、叫它權重。一個流網路保留了有向邊，卻重新詮釋那個數字：不再是一筆要付的成本，而是每條邊承載一個容量，也就是「每單位時間有多少東西能沿著它流動」的一個非負上限。把它想成寬窄不一的水管、車道數不同的道路，或頻寬不同的纜線。有兩個特殊頂點被挑出來：一切的起點源點 s，以及一切最終必須抵達的匯點 t。整個主題就是一個問題——我們一次能從 s 推送多少東西到 t？
想像一個小例子：s 指向兩個中間頂點 a 和 b，a 和 b 又都指向 t。邊 s->a 能載 3、s->b 能載 2、a->t 能載 2、b->t 能載 3。容量是網路固定的性質——它們永遠不變。我們能選的是流：實際沿每條邊送出的量，這個我們馬上就會精確釘死。把這個四條邊的菱形記在腦中；隨著規則一條條到來，我們會把車流路由穿過它。
一個流必須遵守的三條規則
一個流為每條邊指定一個數字 f(u,v)——實際在其上流動的量——而要算作合法的流，它必須滿足兩個約束。第一，容量約束：在每條邊上，0 <= f(u,v) <= c(u,v)。你不能送出負的量，也不能超過水管的寬度。第二，流量守恆：在 s 和 t 以外的每個頂點，流進來的總量等於流出去的總量。中間頂點不創造、也不儲存任何東西；凡是抵達的，都必須離開。一個交會口不是一座水庫。
守恆才是真正做事的規則，所以把它在菱形上具體化。假設我們沿 s->a 送 2；a 處的守恆強迫 2 離開 a，而唯一的出口是 a->t、其容量恰好是 2，所以 a->t 載 2。現在沿 s->b 送 2；b 處的守恆強迫 2 經由 b->t 離開（容量 3，沒問題）。檢查兩個中間頂點：a 處進等於出（進 2、出 2），b 處也是（進 2、出 2）。每條邊都遵守它的容量。這是一個合法的流。注意守恆禁止了什麼：我們無法送 3 進入 a，因為只有 2 能離開 a，多出的那一單位將無處可去。
一個流的值——我們要最大化的那一個數字
現在我們為這份獎賞命名。一個流的值，記作 |f|，是離開源點的淨量：所有從 s 出發的邊上的流的總和，減去任何流回 s 的邊上的流。根據我們剛推出的平衡，這等於抵達 t 的淨量，所以你在任一端量都行。在我們的菱形裡，s->a 與 s->b 各 2，值就是 2 + 2 = 4——四個單位完成了從源點到匯點的旅程。最大流問題很單純：在所有合法的流之中，找出一個值盡可能大的。這一階的一切——增廣路徑、殘餘網路、福特-富爾克森——都是把那一個數字往上推的機械。
在菱形裡 4 是我們能做到的最好嗎？試著超越它。離開 s 的兩條邊容量是 3 和 2，所以最多 3 + 2 = 5 能離開源點。但看看一切必須匯聚到哪裡：邊 a->t 上限是 2、邊 b->t 上限是 3，所以最多 2 + 3 = 5 能抵達 t。兩個界限都說 5，可我們只到了 4——能更好嗎？把 s->a 推到 3？不行：a->t 仍只收 2，所以進入 a 的第三單位卡住了。經 a 的路徑至多載 min(3,2) = 2，經 b 的路徑至多載 min(2,3) = 2，所以誠實的最大值是 2 + 2 = 4。兩條腿都被掐住——a 那條被 a->t 掐，b 那條被 s->b 掐。決定的是瓶頸，而非源點。
割：你能在哪裡把網路切斷
那套瓶頸推理有個名字，而它是這一階最深刻的構想。一個 s-t 割 是把所有頂點分成兩隊的任一種方式：一個含源點 s 的集合 S，以及含匯點 t 的其餘部分 T。割的容量是所有從 S 側跨到 T 側的邊的容量總和——沿著那個特定劃分把 s 與 t 徹底切斷的代價。不同的劃分給出不同的代價，而每一個都是橫亙在源點與匯點之間的一道牆。
這裡是關鍵的觀察，那個讓割不只是個定義的觀察：每一滴從 s 走到 t 的流，在某處必定從 S 側跨到 T 側，因為 s 在 S 裡、t 在 T 裡。所以流永遠不可能超過任何割的容量——割是一道牆，能通過的不會多於這道牆的合計寬度。用符號寫，|f| <= 任一割的容量。在菱形裡，把 a 和 s 放在同一側，t 與 b 放在另一側。跨越的邊是 a->t（容量 2）與 s->b（容量 2），割容量為 4——而我們值為 4 的流恰好頂到它。我們找到了一個容量等於流值的割，這意味著兩者都動不了：流無法越過那道牆而增長，也不存在更薄的牆。
即將到來的對偶之初嚐
我們無意間撞上了某種了不起的東西。任何流的值，至多是任何割的容量——這個方向，叫做弱對偶，我們剛用一行論證證明了。而令人驚嘆、且這一階其餘部分將會掙得的主張是：這兩者其實會相遇：最大流的值永遠等於最小割的容量。這就是最大流最小割定理，是整個演算法領域最著名的結果之一。它說，你能推送的最大量，與你能築起的最便宜的牆，是同一個數字——儘管一個是對「流」的最大化、另一個是對「割」的最小化。
在你動身往上爬之前，一個誠實的提醒。這裡的一切都假設容量是固定的非負數，且流可以取直到上限的任何實數值。當容量是整數時，最大流結果也能用整數的流達成——這個事實讓「流」成為觀照「不可分割之物」問題的完美透鏡，例如把人指派給工作。緊接著的下一篇指南會建起殘餘網路與增廣路徑，這些工具把這幅靜態的圖景變成一個真正的演算法；第三篇證明我們剛預告的那條等式；而第四篇則展示，光是把一個問題建模成一張網路——最著名的就是匹配——就能讓最大流替你扛起重活。