網路流、割與匹配

流的值(value of a flow)

若網路是一套從抽水機到排水口的管路,流的值就是你真正在乎的那個數字:每秒究竟有多少水從抽水機真的送到了排水口。不是內部來回晃動了多少,而是源點到匯點的淨吞吐量。把這個數字極大化就是整場遊戲的目標。

形式上,流 f 的值記作 |f|,是離開源點的淨流量:離開 s 的邊上流量總和,減去進入 s 的邊上流量總和。守恆律保證了一個乾淨的事實:這也等於進入匯點 t 的淨流量——中間既不損失也不生成,凡離開源點的,必抵達匯點。用平衡論證便能看出緣由:把 s、t 以外所有頂點的守恆方程相加,內部一切相消,留下(離開 s)減(進入 s)等於(進入 t)減(離開 t)。第二個乾淨的事實:對任意一個 s-t 割,f 的值都等於穿過該割的淨流量,而那至多為割的容量——所以每個割都給 |f| 一個上界。

這個值正是最大流問題的目標:找一個合法的流,使 |f| 盡可能大。它也是最大流最小割定理精確釘住的量:把最大值等同於最小割容量。一個常見的失誤是把這個值與所有邊上流量的總和混淆;一個在無用環路上繞了 100 單位的流,其值可以是 0。只有源點到匯點的淨吞吐量才算數。

源點 s 有兩條出邊各載 3 與 2,還有一條入邊載 1(有流量回到 s)。則 |f| = (3 + 2) - 1 = 4。無論內部長什麼樣,恰有 4 單位淨流量抵達 t。

值是源點的淨流出——要減掉任何回流;由守恆律,它等於匯點的淨流入。

值是淨吞吐量,不是所有邊上流量的總和。一個流內部數字可以很大,但若那些數字只是循環而未抵達匯點,其值仍可很小(甚至為零)。

又称
flow value|f|流量值