s-t 割(s-t cut)
想像你想藉由剪斷某些管子來阻止所有水抵達排水口,而每根管子按寬度收費。能把抽水機與排水口完全切斷、又最便宜的那組管子,就是整個系統的瓶頸。s-t 割是「在哪裡做這道切割」的形式化版本,而它的容量就是帳單。
精確地說,s-t 割是把頂點分成兩側 S 與 T,源點 s 在 S、匯點 t 在 T。割的容量是從 S 側通往 T 側的邊的容量總和——只算前向越界的邊;從 T 回到 S 的邊不計費。(完全落在 S 內或 T 內的邊不越界,永不計入。)例如,只剪離開 s 的邊得到一個割,其容量是 s 的總出容量;只剪進入 t 的邊得到另一個割。最小割就是最便宜的這種分割。
割之所以重要,是因為每個割都是流的上界:任一單位從 s 到 t 的流量至少要從 S 越界到 T 一次,故任何流的值至多為任何割的容量。最大流最小割定理接著說:最佳的流恰好碰到最便宜的割。這個對偶極其有用:最小割告訴你真正的瓶頸——哪些邊若加寬就真能讓更多流量通過——而把問題建模成最小割(影像分割、專案選取)是標準技巧。一個提醒:這裡的「最小割」指最小容量,不是邊數最少。
在 s -> a(3)、s -> b(2)、a -> t(2)、b -> t(3)中:割 S = {s}、T = {a, b, t} 的容量為 3 + 2 = 5。割 S = {s, a, b}、T = {t} 的容量也是 2 + 3 = 5。而 S = {s, a}、T = {b, t} 前向切斷 a->t(2)、s->b(2)、a->b(1),容量 5——而這裡真正的最小割也是 5,正與最大流相符(這個小圖恰好所有最小割都等於 5)。
只有 S 到 T 的邊計費;T 到 S 的反向邊免費。在所有這類分割上取最小,等於最大流。
容量只算前向越界(S 到 T)的邊。反向邊(T 到 S)免費,這很容易忘——而「最小」指總容量最小,絕不是剪斷的邊數最少。