一個看不出有水管的問題
這裡有個看起來和網路毫不相干的問題。左邊坐著應徵者，右邊坐著職缺；每當某應徵者勝任某職缺，就畫一條邊。你想盡可能多錄取人，每位應徵者至多接一份工作、每份工作至多由一人擔任。一組不共用任何端點的邊就是一個匹配，而我們要的是一個最大匹配——在資格允許下能同時成立的錄取數越多越好。這裡沒有源點、沒有匯點、哪兒都沒有容量。那為什麼這會是最大流的招牌應用呢？
因為答案是一個微小的建模動作——把問題重塑到它的最大流恰好就是你想要的那個數字。圖是二分的（兩側，每條邊都橫跨兩側），正是讓這次重塑忠實無誤的特殊配料。最大匹配是一個「選出最大的合法集合」的問題，而那恰恰是流天生就能回答的問題口味。真正要做的不是發明什麼巧妙的演算法；而是多畫四條邊，並把每個箭頭指向正確的方向。
建構：栓上一個源點與一個匯點
拿出那張左集為 L、右集為 R 的二分圖。新增一個全新的源點 s，以及一個全新的匯點 t。從 s 向每個左頂點各畫一條邊；從每個右頂點各畫一條邊到 t；並把每條原始的「勝任」邊從它的左端點導向右端點。現在給整張網路裡的每一條邊容量都恰好是 1。那單一個數字就是整個訣竅：s->u 上容量 1 表示應徵者 u 至多被用一次；w->t 上容量 1 表示職缺 w 至多被填一次；而 u->w 上容量 1 表示那組配對要嘛整個被選、要嘛完全不選。
s
/ | \ (each s->left edge has capacity 1)
u1 u2 u3
| \X/
w1 w2 w3 (each left->right edge = a qualification, cap 1)
\ | /
t (each right->t edge has capacity 1)現在登場、且名副其實的主張是：這張網路裡的整數流，恰好對應到匹配，而流的值等於匹配的大小。 為何是整數？因為所有容量都是整數，最大流的整數性質保證存在一個在每條邊上都取整數的最大流——於是每條邊載的不是 0 就是 1，從不出現分數。一條載著 1 的邊 u->w 意思是「錄取 u 去做 w」；s 與 t 處的容量 1 上限，禁止任何應徵者或職缺被用兩次。所以一個值為 k 的流就是 k 組不相交的錄取，而一個值最大的流就是一個最大匹配。我們沒有解決匹配；我們把它重新表述了一遍。
增廣路徑化身交錯路徑
在這個小裝置上跑任何最大流演算法，增廣路徑會發生某種美妙的事。回想一條增廣路徑在殘餘網路裡從 s 走到 t，自由地使用前向邊（還有空間）與後向邊（撤銷）。在匹配網路裡，撕去 s 與 t 這兩個書檔，中間剩下的就是一條交錯路徑：它在「目前不在匹配中」的勝任邊（前向）與「目前在匹配中」的邊（後向）之間交替。沿它推一個單位，會把它碰到的每條邊都翻轉——未匹配的配對變成已匹配、擋路的那一組已匹配配對變成未匹配——匹配恰好長大一格。
- 假設 u1 已和 w1 匹配，而現在應徵者 u2 只勝任 w1。樸素的貪婪卡住了：w1 已被佔走，於是 u2 看似無法錄取。
- 但假設 u1 還勝任一份尚未填補的職缺 w2。殘餘網路提供了一條交錯路徑：u2 -> w1（前向，未匹配）、w1 -> u1（後向，已匹配的那條邊）、u1 -> w2（前向，未匹配）。
- 增廣 1：現在 u2 接下 w1，u1 移去做 w2。我們沒有趕走任何人——我們重新安排了。匹配從一組錄取變成兩組，這正是殘餘網路當初為之而生的「撤銷舊選擇」之力。
這正是為何樸素的貪婪匹配——看到誰就配誰、絕不重新考慮——可能不到位，與我們在貪婪那一階遇到的裂縫一模一樣：局部沒問題，全域卻非最佳。這裡的修法和流的修法相同，因為它們本就是同一個修法。柏吉定理給出一條乾淨的停止規則：一個匹配是最大的，恰恰當不存在增廣（交錯）路徑時，而那也正是不存在 s 到 t 的殘餘路徑之時。這兩個故事是穿著兩套戲服的同一個故事。
從最小割上讀出柯尼希定理
現在來收紅利。當流為最大時，最大流最小割定理遞給我們一個容量相等的最小割。追究在匹配小裝置裡一個有限容量的割意味著什麼：它只能切 s->u 與 w->t 這些邊（中間那些邊，依柯尼希的經典論證，可以被避開），而選出的那一組邊對應到一個頂點集——其 s 邊被切的左頂點，加上其 t 邊被切的右頂點——它們合起來碰到每一條勝任邊。一個碰到每條邊的頂點集就是一個頂點覆蓋。所以最小割的容量等於最小頂點覆蓋的大小。
把這些等式串起來，一條著名的定理免費現身。最大匹配等於最大流（我們的建構），最大流等於最小割（對偶定理），最小割等於最小頂點覆蓋（割的解讀）。因此在任何二分圖中，最大匹配的大小等於最小頂點覆蓋的大小——這就是柯尼希定理，一條著名的極小-極大對偶，而流幾乎不費額外力氣就把它交到我們手上。最大的不相交邊集，與覆蓋所有邊的最小頂點集，是同一個數字。
它的代價，以及誠實的附帶細則
這有多快？每條增廣路徑讓匹配增加 1，所以至多 V 次增廣，每次是一回花 O(E) 的圖搜尋。這給出一個簡單的 O(V*E) 界——已經是多項式、已經是個不錯的答案。但因為所有容量都是 1，這是一張單位容量網路，恰好是迪尼茨演算法大放異彩的場合：它在這裡以 O(E * sqrt(V)) 執行，每個階段找出許多條最短增廣路徑而非一條。這個想法的「匹配原生」版本就是霍普克洛夫特-卡普演算法，它每一輪沿一整組極大的最短交錯路徑增廣，同樣達到 O(E * sqrt(V))。
兩個提醒讓你保持誠實。其一，那些是最壞情況的漸進量；一般的隱藏常數但書都適用，在真實的圖上樸素的 O(V*E) 方法往往遠在其界之前就結束——漸進描述的是規模的成長，而非在每個尺寸上的判決。其二，更重要的是：這整套訣竅倚賴圖是二分的。在一般（非二分）圖上的樸素最大流，「不」能正確地建模匹配，因為一個奇環能製造出背後並無匹配的流。一般匹配也能在多項式時間內解，但它需要埃德蒙茲的花朵演算法，那是一個確實不同且更難的想法——不是流。
最後，要是邊帶權重呢——付應徵者 u 三十元去做職缺 w，而你想要最便宜的一整套錄取？容量為 1 的最大流完全無視權重；它只會數數。為此你得攀上最小成本最大流或匈牙利演算法，那是下一篇談把問題建模成流的導覽要鋪陳的。本篇的教訓是最乾淨的那個情形：當一個問題是「在兩側之間挑出最大的合法配對」，就畫一個源點、一個匯點、和一堆單位容量，讓一個你早已信任的最大流演算法去做工——然後從割上免費讀出那些對偶定理。