Maximum Bipartite Matching

此為Maximum Flow的一種應用。
一張圖分成左邊和右邊，各自有一些vertex，
左邊的點有一些edge連到右邊的點，
我們想要找到最多可以配對幾組。

給一個無向圖G=(V,E)，
一個matching M是edges E的subset，（M⊆E）
使得對於所有vertex v∈V，最多會有一條邊接在v上，
maximum matching就是要找出M的最大值，
也就是最多可以成功配對幾組。

bipartite graph為將圖的vertex分成左右兩個子集，
V = L∪R，L和R沒有任何交集，（L and R are disjoint）
並且假設V裡所有的vertex都至少會有一條edge接到另一個vertex。

Introduction to Algorithms Fig. 26.8

方法很簡單，
只要在L的左側新增一個新的source vertex s，s連到所有的vertex∈L，
R的右側新增一個新的sink vertex t，所有的vertex∈R連到t。
接著在新的flow network graph中，每條edge賦予一個unit capacity，
並使用Ford-Fulkerson method去找s->t的maximum flow，
就能得到maximum matching的數量。
如上圖，圖(b)的maximum matching = 圖(c)的maximum flow = 3。