# 二分圖匹配與網路流 Bipartite Matching and Flow
在這篇筆記中，會把之前幾篇講過的定理都串連起來，並且說明他們都是等價的。這些定理會有這些關聯不僅僅是因為我們在證明時使用了其他定理來證明，更是因為他們都可以用轉換成網路流量圖，再用最大流-最小割定理來證明。要看懂這篇筆記，需要的先備知識都寫在我的筆記裡了，可以去翻翻看

前情提要 : [匹配與霍爾定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)、[Kőnig 定理](https://hackmd.io/@ShanC/konig-theorem)、[連通性與 Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem)、[最大流量-最小割定理](https://hackmd.io/@ShanC/maxflow-mincut-theorem)

## Menger 定理與最大流-最小割定理
最大流量-最小割定理遠比演算法書中寫的強大，這節來好好講一下最大流量-最小割定理可以如何來搞定 Menger 定理的第二部分，讓各位體會一下此定理的強大之處

除此之外，寫這段還有一個原因，流量網路中所定義的「割」與 Menger 定理定義的「割」，其實不是同一個東西，但網路上的大家 (包括我學校的競程團隊) 都喜歡混著用。這導致我當時在學最大流最小割定理時超級困惑，常常在想「為什麼明明一張沒權重的圖突然就有容量了，真的超級怪」所以這邊多一些廢話來證這個東西

### 用最大流-最小割定理證 Menger 定理
我們可以來個大膽的假設，若我們能使用最大流量圖來描述任何 Menger 定理中所描述的圖，則「若最大流-最小割定理是正確的，則 Menger 定理是正確的」。這看起來超級複雜，但其實圖轉一轉換一換，不等式弄一弄，再套用最大流-最小割定理，證明就結束了，不用像之前在[這篇](https://hackmd.io/@ShanC/Menger-Theorem#Menger-%E5%AE%9A%E7%90%86)花一堆功夫弄了個歸納法還舉出一堆狀況才證明完

#### 證明
給定一張有向圖 $D$，我們把兩節點 $x, y$ 化為流量網路圖 $N$ 中的源點 $x$ 與匯點 $y$，並設定每條 $N$ 中的邊容量為 $1$。其中，我們可以觀察到幾點 :

- 每條從 $x$ 到 $y$ 的路徑，每一單位的流入 $y$ 流量都會對應到一條路徑，因此 $\lambda'_D(x, y)\geq max ~val(f)$
- 邊割集合 $[S, T]$ 的大小會對應到容量 $cap(S, T)$，因此 $min~cap(S, T)\geq \kappa'_D(x, y)$

(1) 根據最大流-最小割定理以及以上的不等式得到 : $\lambda'_D(x, y)\geq max ~val(f)=min~cap(S, T)\geq \kappa'_D(x, y)$

(2) 由於內部不相交邊路徑中彼此邊不共用，因此得到 : $\kappa'_D(x, y)\geq\lambda'_D(x, y)$

結合 (1) 與 (2) 得到的結論 : $\kappa'_D(x, y)=\lambda'_D(x, y)$，如此一來就用最大流-最小割定理證明了 Menger 定理

### 用 Menger 定理證最大流-最小割定理
在聊完怎麼搞定 Menger 定理後，我們來換個方向證回來最大流量-最小割定理

#### 證明
給定一張流量網路圖 $N$，其容量皆為整數。我們可以弄出一個有向圖 $D$，使 $N$ 中每條邊，$N$ 容量為多少 $D$ 中就有幾條邊

<img src="https://hackmd.io/_uploads/HJFQHWbgll.png" style="margin: 0 auto; display: block; width: 600px">

$~$
我們來看看這張轉換好的圖 $D$ :
- 每條 $s, t$-內部不相交邊路徑都會對應到 $N$ 中的邊流量 : $max~val(f)\geq \lambda'_D(s, t)$
- 若 $F$ 為 $D$ 中的 $s, t$-分割集，將其對應到 $N$ 可得到 $cap(S, T)=\kappa'_D(s, t)$，因此 : $\kappa'_D(s, t)\geq min~cap(S, T)$

(1) 根據 Menger 定理與上述的不等式 : $max~val(f)\geq \lambda'_D(s, t)=\kappa'_D(s, t)\geq min~cap(S, T)$

(2) 對於 $N$ 來說，根據 [Weak Duality](https://hackmd.io/@ShanC/maxflow-mincut-theorem#%E5%BC%95%E7%90%86-4--Weak-Duality) : $max~val(f)\leq min~cap(S, T)$

結合 (1) 與 (2) 得到的結論 : $max~val(f)=min~cap(S, T)$，如此一來就用最大流-最小割定理證明了最大流-最小割定理

### 二分圖的擴充路徑演算法 vs Ford-Fulkerson 演算法
二分圖的擴充路徑演算法其實是 Ford-Fulkerson 演算法的特例。將二分圖 $G=(\{L, R\}, E)$ 的兩個獨立集 $L, R$ 分別加上源點及匯點，並在每條二分圖中的邊加上容量 $1$，形成網路流量圖。執行兩種演算法，每個擴充路徑演算法的步驟都會剛好對應到 Ford-Fulkerson 演算法的每個步驟，因此就可以證明二分圖的擴充路徑演算法是 Ford-Fulkerson 演算法的特例。因為證了沒什麼人會看得懂，而且競程真的用不到，所以在這裡就不寫證明

雖然沒有證明，但是這個概念非常重要，因為此二分圖定義出來的流量皆為 $1$，且最大流量為 $O(min\{|L|, |R|\})=O(V)$。換句話說在這種特例下的 Ford-Fulkerson 演算法，時間複雜度為 $O(VE)$，並不是指數時間 (exponential time)

## 最大流-最小割定理與 Kőnig-Egerváry 定理
流量網路圖也可以用來完二分圖匹配，在競程各種神奇的 flow 題中，這種手法可說是層出不窮。其中我們可以這樣玩二分圖的原因一樣是因為定理們是等價的，因此可以這樣玩。以下就來證明「若最大流-最小割定理是正確的，則 Kőnig-Egerváry 定理是正確的」

#### 證明
給定一張 $X, Y$-二分圖 $G$。我們可以構建一張流量網路圖 $N$ 如以下規定 :
- 增加源點 $s$ 與匯點 $t$
- 對於每個 $x\in X$ 加入有向邊 $s\rightarrow x$ 並設容量為 $1$
- 對於每個 $y\in Y$ 加入有向邊 $y\rightarrow t$ 並設容量為 $1$
- 將連接 $X,Y$ 的邊設為有向邊從 $X$ 到 $Y$，並設容量為無限大

<img src="https://hackmd.io/_uploads/Bk2R6AWelx.png" style="margin: 0 auto; display: block; width: 700px">

$~$
根據 [Integrality Theorem](https://hackmd.io/@ShanC/maxflow-mincut-theorem#%E6%95%B4%E6%95%B8%E6%B5%81-Integral-Flows)，存在一個最大流量 $f$ 使每條邊的流量皆為整數。再者，容量為 $1$ 的限制使 $X,Y$ 之間的邊行成了匹配，$val(f)$ 就是匹配的大小。對於每個 $f$ 來說，$0\leq val(f)\leq max~val(f)$，因此我們就得到 $\alpha'(G)\geq val(f)$

加入割的觀點來看這張圖，因 $[s, V(N)-s]$ 是有限容量，一組最小割一定也是有限的容量。設 $[S, T]$ 是 $N$ 中的最小割，$X'=S\cap X$，$Y'=T\cap Y$。一個有限容量的割並不會包含無限容量的邊，因此 $X'$ 與 $Y'$ 之間沒有連邊。這代表 $(X-S)\cup (Y-T)$ 是一組點覆蓋。再者，割 $[S, T]$ 是由 $s$ 連到 $X\cap T=X-S$ 的邊與從 $Y\cap S=Y-T$ 連到 $t$ 的邊組成，他們的容量就是 $|(X-S)\cup (Y-T)|$。透過定義與對於圖的觀察，因 $cap(S, T)$ 可能會不小心切到無限大的邊，所以可得到 $\beta(G)\leq cap(S, T)$，

<img src="https://hackmd.io/_uploads/SJ6BxJflxe.png" style="margin: 0 auto; display: block; width: 520px">

$~$
(1) 根據最大流-最小割定理與上述的不等式 : $\beta(G)\leq min~cap(S, T)=max~val(f)\leq \alpha'(G)$

(2) 在任何圖中 $\alpha'(G)\leq \beta(G)$

由 (1) 與 (2)，得到 $\alpha'(G)=\beta(G)$，即二分圖最大匹配等於最小點覆蓋

## 把圖轉換成網路流量圖的技巧
由於在上面只有證 Menger 定理的第二部分，也就是關於邊割的那個部分。如果要說明第一個部分，也就是關於點割的那個部分，那我們其實有兩種方法

1. 把證出來的第二部分從線圖改回原本的圖來證明之
2. 使用以下技巧將圖轉為流量網路圖，再用最大流-最小割定理證明之

以下技巧不僅是在證明用的到，這些方法也是競程常用的技巧，很多 flow 題都需要這些方法來轉換題目的圖

### 有向圖拆點
有時候，當我們需要模擬點權而非邊權時，可以將圖轉成[線圖 (line graph)](https://hackmd.io/@ShanC/Menger-Theorem#%E7%B7%9A%E5%9C%96-Line-Graph)，以用邊來模擬點的狀況，但這樣並不直觀，在寫程式時也不好操作。以下提供另一種轉換方式 : 將帶權點拆成「入點」與「出點」，兩點中間連邊，權重為原本的點權，並將其他邊當成邊權有無限邊權

<img src="https://hackmd.io/_uploads/ByypXeZxge.png" style="margin: 0 auto; display: block; width: 600px">

### 無向邊拆邊
無向邊在有向圖的世界裡面，其實就是同時存在去與回兩種邊

<img src="https://hackmd.io/_uploads/rkm7rxZxxg.png" style="margin: 0 auto; display: block; width: 600px">

### 證明 Menger 定理第一部分的想法
可以將每個除了原點與匯點的節點設點權為 $1$，並進行以上拆點或拆邊，整張圖就會形成一張流量網路圖，在這流量網路圖中，除了一開始就可以從定義得出的不等式 $\kappa(x, y)\geq\lambda(x, y)$，還需要證明 $\kappa(x, y)\leq\lambda(x, y)$，而這就需要最大流-最小割定理來幫忙。總體來說幾乎跟上面的證明差不多，差別只在要怎麼分析新建好的流量網路圖得出不等式。礙於我想偷懶，這部分就丟個想法，拋磚引玉

## 邏輯等價關係
在我的筆記之中，簡略的說明了不同問題之間的轉換。其中只有 [Hall 定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)與[最大流-最小割定理](https://hackmd.io/@ShanC/maxflow-mincut-theorem)是獨立證出來的，剩下的 [Kőnig-Egerváry 定理](https://hackmd.io/@ShanC/konig-theorem)與 [Menger 定理](https://hackmd.io/@ShanC/Menger-Theorem)都有用到其他定理才推出來，然而在在與強大的網路流量圖轉換後，我們又得到了更多推證明的方式，得到下圖

<img src="https://hackmd.io/_uploads/SyqlxVYJle.png" style="margin: 0 auto; display: block; width: 600px">

$~$
有了這些轉換，我們便可以說明不同定理之間的等價關係，這意味著**定理們的效力是彼此等價的!!**

事實上，還有一堆定理與這些定理等價，但礙於不在圖論的範疇，我也看不懂

## 題目練習
很意外地，發現 CSES 上就有兩題裸的 Menger Theorem 裸題
雖然這篇還沒講要怎麼實作 flow，但是這題就先放著吧
以免有人覺得講這些理論沒用或是都在胡說八道

[CSES - Police Chase](https://cses.fi/problemset/task/1695/)
[CSES - Distinct Routes](https://cses.fi/problemset/task/1711)

----

## 參考資料

- D.B.West - Introduction to Graph Theory 2/e
- Introduction to Algorithms, Fourth Edition
- [Howard Wang - 圖形理論](https://hackmd.io/@HowWang/rkts6dUMo#Ch4-Connectivity-and-Paths)
- [Hall's marriage theorem Logical_equivalences - 維基百科](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem#Logical_equivalences)

----

> [ShanC 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC)
> 作者: ShanC
> 更新: 2025/5/3