網路流、割與匹配
流量守恆(flow conservation)
在既非源點也非匯點的管路接頭處,水不能堆積也不能消失——流進的每一滴都得流出去。流量守恆正是網路裡的這條規則:內部頂點是穿越點,不是水庫也不是泉眼。正是這個約束讓流像穩定的電流,而非對邊的任意標號。
精確地說,對源點 s 與匯點 t 以外的每個頂點 v,進入 v 的邊上流量總和等於離開 v 的邊上流量總和:對入邊的 f(u, v) 求和 = 對出邊的 f(v, w) 求和。只有 s 與 t 例外——s 容許有淨流出的盈餘,t 容許有淨流入的虧損(它吸收)。這是電路中克希荷夫電流定律在網路上的對應。連同容量約束(每條邊 0 <= f <= c),守恆是定義合法流的兩條規則之一;流理論其餘一切都建立在這兩條之上。
守恆保證了流的值有良好定義——源點的淨流出等於匯點的淨流入,中間毫無洩漏。它也是為何任一流總能分解為少數幾條源到匯的路徑外加一些內部環路:路徑承載值,環路自動守恆且不承載任何值。一個微妙之處:守恆並不禁止環路上有流,它只禁止頂點處的累積;無用的循環環路是合法的卻毫無意義,好的演算法絕不製造它們。
頂點 a 從 s 收到 3、從 b 收到 1,故有 4 單位進入。守恆迫使 4 單位離開 a——比如 2 到 t、2 到 c。若改為只有 3 離開,a 就非法儲存了 1 單位,f 便不是合法流。
在每個內部頂點對帳:進等於出。只有源點與匯點這兩個帳戶可以不平衡。
守恆只適用於內部頂點。忘了 s 與 t 是例外是經典的建模錯誤——那會迫使值為 0,因為一個平衡的源點什麼也產不出。
又稱
另見