概念地圖・Ford–Fulkerson 增廣路
作者 山姆（謝冠生）・喵喵書評創辦人
發布
分類：系統
這一頁不只是把一個概念解釋一遍——一張自己畫的結構圖，加上拿台灣情境從頭走一次的實例演練、這個框架什麼時候會騙你，以及它接回 P.A.I.N. 之後長什麼樣。一頁必須交付的三層 →
Ford–Fulkerson 增廣路：一張網路的最大流量卡在哪
總表那邊進得來十八噸，末端只收得到十二噸。中間沒有漏水，每一段管也都還沒鏽死——差別長在幾段口徑湊起來的那個組合。Ford–Fulkerson 做的事很土：從源點挑一條還有餘裕的路，能塞多少塞多少，塞完再找下一條，找到再也找不出來為止。停下來的那一刻，它同時交出兩個答案——這張網路的最大流量，以及卡住它的那一組關卡。兩個數字必須相等，那是驗算，也是這個框架最好用的地方。
一張網路，兩個數字要對得起來
先把圖上那七條邊攤成表。容量是這一段每小時過得了多少，流量是三次增廣塞完之後它實際扛著多少，兩個相減就是餘裕。
| 這一段 | 容量 | 三次增廣後的流量 | 還剩多少餘裕 |
|---|---|---|---|
| S→A | 10 | 10 | 0，走滿 |
| S→B | 8 | 2 | 6 |
| A→C | 6 | 6 | 0，走滿 |
| A→D | 5 | 4 | 1 |
| B→D | 7 | 2 | 5 |
| C→T | 9 | 6 | 3 |
| D→T | 6 | 6 | 0，走滿 |
節點自己會對帳：A 進來 10、出去 6 加 4；D 進來 4 加 2、出去 6；T 收到 6 加 6，總共 12。走滿的邊有三條，落在那一刀上的只有兩條——S→A 一樣是 10／10，把它換粗卻一噸都拿不回來。原因藏在殘餘圖裡，第四節會把它拆開。
這條增廣路怎麼找，看殘餘容量
找增廣路是很機械的事，機械到可以列成四道自問。管閥現場最常卡住的地方，也剛好都落在這四題上。
一、源點與匯點各釘一個。一套管網有沒有天花板，得先講清楚水從哪一個錶進來、算到哪一個點為止。總表到廠區大門是一段，大門到生產線又是一段——邊界量錯，後面每一條路都白算。管閥商最常見的作法是把匯點設在自己交付的那顆閥上，而客戶抱怨的是三十公尺外那個水龍頭。自問：這條流程的「進得來」與「收得到」，各是由哪一個關卡量出來的？
二、容量要用同一個單位、同一段時間量。口徑寫毫米、泵浦寫揚程、閥門寫 Cv 值，三份規格書擺在一起，沒有一份講的是噸。要跑增廣路，得先全部換算成同一個問題：這一段每小時最多過幾噸。換算這一步沒做完，圖畫得再漂亮也只是一張接線圖。自問：每一段的上限，都是用同一個單位、同一段時間量出來的嗎？
三、一條路能送多少，由路上最窄的那一段決定。總表→東站→水塔→末端這條路，前面那段 10 噸再寬也沒用，中間有一段只有 6，整條路就只送得了 6。管閥業務最容易高估的就是這件事：客戶問「換一顆大的可不可以」，答案要看那顆閥在哪一條路上、那條路上還有沒有比它更窄的地方。自問：你正在跑的那條路上，最窄的是哪一關，你點得出來嗎？
四、已經送出去的量，收不收得回來。這是殘餘圖存在的理由。東站先把 4 噸派給了蓄水池，那 4 噸是可以收回來重新分配的——圖上就畫成一條由蓄水池指回東站的反向邊，容量 4。少了這條邊，你會以為東站已經滿載，於是永遠找不到後面那條更好的路。實體管子當然不會倒流，倒流的是「派給誰」這個決定。自問：先前分配出去的量，現在還收得回來嗎？
一套管閥網路的十二噸，三次增廣走一遍
底下這家台灣中部的管閥工程商，是為了把這個結構講清楚而編出來的示意情境，沒有指涉任何真實公司。他們替一座廠區配水：總表是源點，末端生產線是匯點，中間有東側加壓站、西側加壓站、屋頂水塔、地下蓄水池四站，單位是每小時的噸數。
- 先把七段管的上限抄下來：總表→東站 10、總表→西站 8、東站→水塔 6、東站→蓄水池 5、西站→蓄水池 7、水塔→末端 9、蓄水池→末端 6。總表那邊兩條幹管加起來 18 噸。先有數字
- 第一次增廣：總表→東站→水塔→末端：路上最小的餘裕是東站→水塔那 6 噸，送 6。一次到底
- 第二次增廣：總表→東站→蓄水池→末端：總表→東站還剩 4、東站→蓄水池 5、蓄水池→末端 6，最小是 4，送 4，累計 10。再吃四噸
- 第三次增廣：總表→西站→蓄水池→末端：西側幹管餘裕還有一大把，但蓄水池→末端只剩 2 噸，只送得了 2，累計 12。西線只用兩噸
- 再也找不到有餘裕的路：所以最大流是 12 噸，總表那 18 噸有 6 噸整年進不來。十八進十二出
- 切一刀驗算：從總表沿殘餘圖走，到得了西站、蓄水池，再靠那條反向邊倒回東站；水塔與末端走不到。刀就切在東站→水塔（6）與蓄水池→末端（6）上，合計 12。兩數對上
工程師指的那兩段管，就是這一刀切到的兩段。這裡最值錢的一個結論是反過來的：把總表→西站那條幹管從 8 噸加粗到 12 噸，末端一噸都不會多——它本來就有 6 噸沒用到。想真的往上走，得動切上的那兩段。把東站→水塔換成 9 噸的口徑，天花板從 12 升到 15；可是切還是落在同一組兩段上，因為蓄水池→末端那 6 噸沒動過。要再往上，兩段得一起動，而那時候瓶頸會整個跳到總表→東站與西站→蓄水池去。報價單上寫幾個口徑很容易，難的是講清楚哪一組加起來最小、換完之後下一組會長在哪裡。以上為說明結構用的示意情境，僅供理解框架之用。
這條最小切最容易被讀錯的地方
- 只看正向餘裕去找切，會切出一個對不起來的數字。從源點出發，只挑「還有餘裕的正向邊」走：S→A 已經 10／10 走不動，走 S→B 到 B，再走 B→D 到 D，D→T 也走滿，於是停在 S、B、D 三個點上，切在 S→A（10）與 D→T（6），合計 16。可是最大流明明是 12。錯在漏了反向邊：A→D 身上扛著 4 噸流量，代表這 4 噸可以退回去，所以從 D 能「倒著」走到 A，A 也屬於源點那一側。這樣切才落在 A→C 與 D→T 上，6 加 6 剛好 12。殘餘圖是這一刀的判準——少看那條反向邊，就會多算出 4 噸根本不存在的天花板。
- 走滿的邊，只有一部分會落在切上。圖上三條 10／10、6／6、6／6 都塞爆了，其中 S→A 卻不在刀口。理由是它後面還有替代路徑：水流過了 A 之後，可以走 A→C，也可以走 A→D，兩條路把壓力分散掉。把 S→A 換成 14 噸，那多出來的水到了 A 一樣出不去。哪裡最擠，看流量表就知道；哪裡值得花錢，只認那一刀。
- 順序會換掉分配，但換不掉那個總數。如果先跑 S→B→D→T 送 6，再跑 S→A→C→T 送 6，總數一樣是 12，可是每段扛的量全變了：A→D 從 4 變成 0，B→D 從 2 變成 6。最大流的那個總數是唯一的，怎麼分卻有好幾種寫法。所以拿演算法吐出來的那張流量分配當排班表、當管線施工圖，會排出一個明明可行卻沒人認帳的方案——把它當成一種可行解，別當成唯一解。
卡住的那兩段管
一條交付流程的天花板，寫在某一組接頭加起來的那個數字裡。
網路流最迷人的地方，是它把「我覺得產能不夠」換成一個指得出來的位置。管網那一刀切在兩段管上；工廠那一刀可能切在一台設備加一位師傅；接案公司那一刀可能切在提案期加驗收期。指得出位置，才有得討論錢該花在哪裡。只是這張圖畫得出每一段每小時過得了幾噸，畫不出末端那個人願不願意再多等三十分鐘。P.A.I.N. 的第一個字問的是誰在痛——瓶頸後面站著的那位客戶，他的忍耐上限沒有寫在任何一份規格書上，而它常常比管子先破。把最大流從 12 拉到 15 要花多少錢，估得出來；把一個人從「再等等」推到「我不等了」的那條線在哪，只能去問他。畫出自己那條交付流程，圈出加起來最小的那一組關卡——今晚就畫，先別急著加人。
常見問題
Ford–Fulkerson 和 Edmonds–Karp 差在哪？
同一套骨架，差別在挑路的規矩。Ford–Fulkerson 只說「找一條還有餘裕的路」，沒說怎麼找；容量是無理數時，理論上可以一直找下去而收斂不到答案。Edmonds–Karp 把規矩釘死：每次都挑邊數最少的那條增廣路，找路的次數因此有了上限，跟容量多大無關。手算的網路都很小，順序影響的多半只是演算的順暢度——但寫成程式要跑幾萬條邊時，這個規矩決定了它跑不跑得完。
最大流一定等於最小切嗎？
是，這就是最大流最小切定理。直覺可以這樣理解：任何一刀切開源點與匯點，水都得穿過那一刀，所以流量永遠不會超過任何一刀的容量和——這是上界。而演算法停下來時，殘餘圖上從源點走得到的那群節點，往外的每一條邊都剛好走滿，那一刀的容量和恰好等於當下的流量——這是下界。上界跟下界撞在一起，答案就只剩一個。本文那張圖是 6＋6＝12，跟末端收到的 12 對得起來。
容量會變動、或者不是整數，還能用嗎？
可以，但要換個問法。整數容量最好用，每次增廣至少推進 1，一定停得下來。小數也算得出來，只是要留意收斂。真正麻煩的是容量隨時間變——尖峰時段的水壓、白天夜間的人力，這時要嘛切成幾個時段各算一張圖，要嘛把容量取保守值。拿一張用平均值畫出來的網路去承諾尖峰交期，最大流會算得很漂亮，現場照樣塞車。
一定要畫成網路圖才算用了這個框架嗎？
不必。真正要拿走的是三個動作：把交付路徑拆成一段一段、每段標一個每小時的上限、再問哪一組關卡加起來最小。三個人的小工作室在白板上畫五個框就夠用。畫成圖的好處是反向邊看得見——你會發現某一段之所以卡住，是因為前面那一站把量派給了另一條路，而那個決定隨時可以收回來重派。
下游把訊號往上游推、讓前段自己減速，那是另一套做法，先繞去讀背壓與流量控制；至於使用率一逼近上限、等待時間就往上翹的那條線，收在排隊使用率曲線裡。
喜歡這篇文章嗎？
每週幫你拆二本好書，把判斷力、好書金句、好問題，直送你的信箱。
不適合你可隨時退訂 · 每週兩封，陪你把書讀進生活。
送出即表示同意我們依隱私權政策使用你的 email。