Flow Networks

把一張圖想像成一個複雜的水道管線，
有起點（source）與匯流點（sink），
每條水管都有流量上限。
我們想要知道，
從起點開始灌水、並經由一些路徑流到匯流點，
要怎麼走才能送出最大量的水、以及最多可以送出多少水。

一個flow network G=(V,E)是一個有向圖，
圖中每條edge(u,v)∈E有一個非負值的capacity c(u,v)≥0，
且每條edge只會有一個方向，
也就是若有一條edge(u,v)，就不能有edge(v,u）。
圖裡有一個source vertex s，以及一個sink vertex t。

定義G的flow為一個兩頂點對應到實數的函數：
f：V x V → R，且滿足以下2個特性：
(1) Capacity constraint：0≤f(u,v)≤c(u,v) for all u,v∈V
(2) Flow Conservation：∑(v∈V)f(v,u) = ∑(v∈V)f(u,v)

第(1)點就是流過edge的flow大小要小於流量限制；
第(2)點可以想成流進來的等於流出去的，
而若(u,v)∉E，則沒有從u到v的flow，因此f(u,v)=0。

f(u,v)即稱作從vertex u流向vertex v的flow，
定義f的值 |f| = ∑(v∈V)f(s,v) - ∑(v∈V)f(v,s)，
也就是從source流出去的總量減去流進source的總量。
在Maximum Flow的問題中，
我們希望可以找到|f|的最大值。

Introduction to Algorithms Fig. 26.2

之前有提到，
flow network graph中不能有雙向的邊，
在上圖(a)中，同時有(v1,v2)與(v2,v1)兩條邊，
因此圖(a)並不是個合法的flow network graph。

解決方式為，
新增一個新的vertex v'當做中介點，
原本的(v1,v2)變成(v1,v')以及(v',v2)，
而c(v1,v2)=c(v1,v')=c(v',v2)=10。