# 匹配與霍爾定理 Matching and Hall's Theorem
競程常出現的 flow 題當中，二分圖配對問題是常客中的常客，我猜原因是因為這樣子出題會比較隱晦一點，不容易看出可以 flow (或許吧)。 對於通靈專家而言，要把問題弄成二分圖匹配的樣貌並沒有什麼大不了的，但是對於一般人而言，這東西是非常難理解的，就算搞懂也很難理解建圖的過程，因此在本篇中我們需要先理解二分圖匹配問題的本質。其次需要知道許多問題背後可以轉化的原因是什麼，這會在[下一篇](https://hackmd.io/@ShanC/konig-theorem)解釋清楚

## 匹配 Matching
### 引入情境
今天有一群人要出去玩。已知飯店的每個房間只有兩個床位，且每一個人都只能挑一個床位。這群人的關係網如左圖，連邊的兩個人代表互相認識，他們希望可以跟自己認識的人同一個房間。如何分配才能使邊數最大呢?

下面的右圖或許是一種分法

<center class = "half">
<img src="https://hackmd.io/_uploads/S1WxWJ9Pye.png" style="width: 350px">
<img src="https://hackmd.io/_uploads/r1oenb5w1e.png" style="width: 350px">
</center>

<p class="text-center">
MyGo && Ave Mujica 人物關係圖 (我認為的)
<br>
(我比較喜歡愛爽但是出於無奈不喜歡鍵帽配祥子)
</p>

### 匹配定義
一個**匹配 (matching)** 是在一張圖 $G$ 中，一個不包含自環 (loop) 與共享終點 (shared endpoint) 的邊集合。假設有一匹配集 $M$，任何關聯 (incident) 匹配邊的節點都是被 $M$ **飽和的 (saturated)**，其餘則是**未飽和 (unsaturated)**，分別寫作 $M-saturated$ 與 $M-unsaturated$。一張圖中的**完美匹配 (perfect matching)** 是指一個匹配包含了所有節點

如上圖 MyGo && Ave Mujica 人物關係圖就是一個完美匹配的例子

### 匹配數量
匹配集中的邊數就稱為匹配的數量，即匹配集的基數 (cardinality)

<center>
<img src="https://hackmd.io/_uploads/ryXdyMqwyx.png" style="margin: 0 auto; display: block; width: 400px">
</center>
<p class="text-center">
如上圖，藍邊為匹配邊，此圖的匹配數為 1
</p>

### 最大匹配
**極大匹配 (maximal matching)** 是指一個不能再擴展的匹配。**最大匹配 (maximum matching)** 是指在一張圖的所有匹配中對大的匹配

看回上面那張圖，是一個極大匹配，因為選了邊 $e_{bc}$ 後就不可以再選邊 $e_{ab}$ 與 $e_{cd}$。如果要湊成最大匹配的話，那麼 $M=\{e_{ab}, e_{cd}\}$

## Berge 定理
### 交錯路徑 Alternating Path
設一個匹配 $M$，則一條交錯路徑是一條在匹配邊與未匹配邊交錯的路徑，寫作 $M$-alternating path

### 擴充路徑 Augmenting Path
在匹配 $M$ 中，一條兩終點都是未匹配點的交錯路徑被稱作擴充路徑 (或叫做增廣路徑)，寫作 $M$-augmenting path

### 對稱差集 Symmetric Difference
對於兩圖 $G$ 與 $H$，對稱差集 $G_\Delta H$ 是 $G \cup H$ 的子圖 (有時寫作 $G\bigoplus H$)。其中，$G_\Delta H$ 的每一條邊都只在 $G \cup H$ 中出現一次。對於兩個匹配 $M, M'$ 而言，$M_{\Delta}M'=(M-M')\cup(M'-M)$

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

$~$

如上圖，匹配 $M$ 有 $5$ 條細藍邊，匹配 $M$ 則有 $6$ 條粗黑邊。兩匹配有一條共有的邊 $e$，而這不是他們的對稱差集。$M_{\Delta}M'$ 中的邊形成一個長度為 $6$ 的環與長度為 $3$ 的路徑

### 引理 1
兩匹配的所有單元 (component) 之對稱差集，會形成一條路徑或一個偶數環

#### 證明
令 $M, M'$ 為兩個匹配，$F=M_{\Delta}M'$。因為 $M, M'$ 是兩個匹配，所有與其有邊關聯的節點分別最多只有一個 (根據匹配定義)，因此 $F$ 最的最大度數 $\Delta(F) \leq 2$。又因為最大度數最多只會是 $2$，每一個單元會形成路徑或環。此外，由於 $M_{\Delta}M'$ 是兩個邊集合 $M - M'$ 與 $M' - M$ 的聯集，如果形成環的話，從兩集合來的邊數會一樣，因此會形成偶數環

### Berge 定理
一個匹配 $M$ 是圖 $G$ 的最大匹配若且唯若 $G$ 沒有擴充路徑。此定理又稱作擴充路徑定理 (augmenting path theorem)

#### 證明 (Berge [1957])
我們可以證此命題的反面，即「$G$ 有比 $M$ 大的匹配若且唯若 $G$ 有擴充路徑」

$\Rightarrow$ : 我們可以直接觀察出一條擴充路徑可以產生比 $M$ 大的匹配
$\Leftarrow$ : 令 $M'$ 是一個在 $G$ 中大於 $M$ 的匹配，則我們可以造出一條 $M$ 的擴充路徑。設 $F=M_{\Delta}M'$，根據引理 1，$F$ 存在路徑與偶數環，而環上與於 $M$ 及 $M'$ 的邊數是相等的。因為 $|M'| > |M|$，$F$ 必有單元的 $M'$ 邊數比 $M$ 多，這種單元只能是兩終點都是未匹配的節點，因此他就是一條 $M$ 的擴充路徑

證畢

## 二分圖 Bipartite Graph
### 獨立集 Independent Set
一個節點集合內任兩節點都沒有邊相連
### 二分圖 Bipartite Graph
如果一張圖是由兩互斥的獨立集組成，則此圖是二分圖

<center>
<img src="https://hackmd.io/_uploads/B1eiCNqwkx.png" style="margin: 0 auto; display: block; width: 400px">
</center>
<p class="text-center">
上圖是由兩獨立集組成的二分圖
</p>

## 霍爾匹配條件 Hall's Matching Condition
在二分圖的匹配中，霍爾匹配條件是一個充分且顯然重要的條件。其中，我們使用 $N(S)$ 來代表 $S$ 的鄰居

### 霍爾定理 Hall's Theorem
$X, Y$-二分圖有一匹配使 $X$ 飽和，若且唯若 $|N(S)| \geq |S|$ 對於所有 $S \subseteq X$

#### 證明 (P.Hall [1935])
$\Rightarrow$ : $|S|$ 個在 $N(S)$ 的節點必須與 $S$ 匹配
$\Leftarrow$ : 我們可以證明這個命題的反面，也就是「若 $M$ 是 $G$ 裡的匹配，且並沒有使 $X$ 飽和，那麼就會得到一個集合 $S \subseteq X$ 使得 $|N(S)| < |S|$」

令 $u\in V$ 是未被 $M$ 飽和的節點。所有從 $u$ 能被 $M$ 的擴充路徑碰到的節點，令 $S\subseteq X$ 包含之，再令 $T\subseteq Y$ 包含之。$M$ 為粗的邊，如下圖

<center>
<img src="https://hackmd.io/_uploads/r1ndPI5DJx.png" style="margin: 0 auto; display: block; width: 600px">
</center>
<p class="text-center">
圖源 : D.B.West - Introduction to Graph Theory p.110
</p>

我們可以說明 $M$ 中的 $S - \{u\}$ 匹配 $T$。從 $u$ 出發的交替路徑會沿著不在 $M$ 中的邊碰到 $Y$，且會沿著 $M$ 中的邊碰到 $X$，因此所有在 $S - \{u\}$ 的節點會碰到 $M$ 裡的邊到達 $T$。因為並沒有 $M$ 的擴充路徑，所有 $T$ 的節點都飽和了，因此碰到 $y\in T$ 通過 $M$ 的交替路徑擴充到 $S$ 的節點。所以這些邊會生出一個從 $T$ 到 $S-\{u\}$ 的對射 (bijection)，且 $|T|=|S-\{u\}|$

從 $T$ 到 $S - \{u\}$ 會閃生 $T\subseteq N(S)$。事實上，$T=N(S)$

假設 $y\in Y-T$ 有一個鄰居 $v\in S$。邊 $vy$ 不能在 $M$ 裡面，因為 $u$ 是未被匹配的節點且剩下的 $S$ 已經通過 $M$ 匹配到 $T$。因此加了邊 $vy$ 到 $M$ 的交替路徑中會使得 $M$ 的交替路徑到達 $y$。這與 $y\notin T$ 違背，因此邊 $vy$ 不存在

藉由 $T=N(S)$，我們可以證明在這個例子中 $|N(S)|=|T|=|S| - 1 < |S|$。如此一來，就完成反面論述的證明

### 霍爾配婚定理 Hall's Marriage Theorem
當我們加入條件 $|X|=|Y|$ 時，霍爾定理就會變成霍爾配婚定理

----

## 參考資料

- D.B.West - Introduction to Graph Theory 2/e
- [Howard Wang - 圖形理論](https://hackmd.io/@HowWang/rkts6dUMo#Ch3-Matchings-and-Factors)
- [麗山演算法讀書會 - 二分圖、匹配、匈牙利算法](https://hackmd.io/@Lssh-Algorithm/B1SSNIl6u)
- [台師大演算法筆記 - matching](https://web.ntnu.edu.tw/~algo/Matching.html)
- [海大競程 - flow and match](https://hackmd.io/@LeeShoWhaodian/2024flow#/5)

----

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