# Kőnig 定理
Kőnig 定理就是將二分圖 (bipartite graph) 最大匹配與最小點覆蓋串來起來的關鍵。由於二分圖最大匹配問題可以被歸約 (reduce) 成最大網路流量問題，因此最大網路流量問題也可以歸約成最小點覆蓋問題

建議先讀完另一篇筆記[匹配與霍爾定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)再來看這篇，因本篇會使用到霍爾定理的結論來證明

注: Kőnig's theorem 是由 Dénes Kőnig 與 Jenő Egerváry 於 1931 年證出來。許多資料經常將 Kőnig 以德文讀音譯作「柯尼希」，但是用匈牙利語的讀音是「柯尼格」。由於生活的時代背景是有包含奧匈帝國時期 ，許多研究也是以德文發表。因不知他祖上究竟是德裔還是匈牙利裔，亦或是德奧邊境的少數民族 (猜測是從德奧邊境地區到匈牙利)，我不敢貿然翻譯它的名稱 (但我比較傾向「柯尼格」這個翻譯)。Dénes Kőnig 其實是位匈牙利猶太人，致力於研究圖論與集合論，是現代圖論領域重要的發跡者(以往的圖論都散布在各個領域)。最後他在 1944 年因德國迫害而自盡

## 點覆蓋 Vertex Cover
一張圖 $G=(V,E)$ 的點覆蓋是一個集合 $Q\subseteq V(G)$ 使得包含所有邊的最少一個終點。我們會說 $Q$ 覆蓋 $E(G)$

<center>

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

</center>

如上圖，$G$ 共有 $6$ 個節點，而其中 $2$ 個節點 (以方框表示) 可以覆蓋所有的邊。而黑邊會形成一組大小為 $2$ 的最大匹配

想當然爾，我們也可以把所有點都選起來，這樣一樣會形成點覆蓋

## 邊覆蓋 Edge Cover
一張圖 $G=(V,E)$ 的邊覆蓋是一個邊集合 $L$，所有節點都會與 $L$ 中的一些邊相鄰

<center>

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

</center>

如上圖，$4$ 條藍色的邊都是 $L$ 裡的邊，可以說這些藍邊覆蓋了所有節點。而方框裡的節點可以形成大小為 $4$ 的獨立集

想當然爾，我們也可以把所有邊都選起來，這樣一樣會形成邊覆蓋

## Kőnig 定理 Kőnig's Theorem
此定理的一般化又稱作 Kőnig-Egerváry theorem
### 敘述
如果 $G$ 是一張二分圖，則 $G$ 的最大匹配會等於最小點覆蓋

### 證明
令 $G$ 為一張 $X,Y$ 二分圖。由於不同的節點會被用於邊的匹配，對於點覆蓋 $Q$ 與匹配 $M$，$|Q|\geq |M|$。我們可以給一個最小點覆蓋 $Q$，然後再建構一個大小為 $|Q|$ 的匹配來證明他們是等價的

令 $R = X \cap Q$、$T = Y\cap Q$。再令 $H=R\cup(Y-T)$ 與 $H'=T\cup (X-R)$ 為 $G$ 的子圖。我們可以使用[霍爾定理](https://hackmd.io/@ShanC/Matching-and-Halls-Theorem)來說明說 $H$ 有一個匹配會使 $R$ 配到 $Y-T$，也可以說明 $H'$ 有一個匹配會使 $T$ 飽和。由於 $H$ 與 $H'$ 是互斥的，兩者的匹配會形成一個大小為 $|Q|$ 的匹配

由於 $R\cup T$ 是一個點覆蓋，$G$ 並沒有任何一條邊從 $Y-T$ 連到 $X-R$。對於每個 $S\subseteq R$，我們考慮 $N(S)$ 被包含在 $Y-T$。如果 $|N(S)| < |S|$，那我們可以將 $Q$ 中的 $S$ 帶入 $N(S)$，這樣就會得到更小的點覆蓋，因 $N(S)$ 覆蓋所有與 $S$ 相鄰且不被 $T$ 覆蓋的邊

最小化的 $Q$ 會在 $H$ 中產生霍爾條件，也因此 $H$ 有一匹配會使 $R$ 飽和。相同地，$H'$ 會產生一匹配使 $T$ 飽和

<center>

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

</center>

<p class="text-center">
圖源 : D.B.West - Introduction to Graph Theory 2/e p.113
</p>

## 覆蓋的補圖 The Completement of Covers
### 名詞定義
$\alpha(G)$ : 代表最大獨立集
$\alpha'(G)$ : 代表最大匹配
$\beta(G)$ : 代表最小點覆蓋
$\beta'(G)$ : 代表最小邊覆蓋

### 以符號表示 Kőnig 定理
對於一張二分圖來說，$\alpha'(G)=\beta(G)$

### 引理 1
在一張圖 $G$ 中，$S\subseteq V(G)$ 為一獨立集，若且為若 $\bar{S}$ 是一個點覆蓋，因此 $\alpha(G)+\beta(G)=n(G)$

#### 證明
如果 $S$ 是一個獨立集，那麼每條邊與最少與一個 $\bar{S}$ 中的節點相鄰。反之，如果 $\bar{S}$ 覆蓋所有節點，那麼就不會有邊將 $S$ 地點相鄰。因此所有對大獨立集是最小點覆蓋的補集 (complement)，且 $\alpha(G)+\beta(G)=n(G)$

### 定理 1 [Gallai 1959]
若 $G$ 是一張沒有孤立的節點的圖，那麼 $\alpha'(G)+\beta'(G)=n(G)$

#### 證明
從一個最大匹配 $M$，我們可以建構一個大小為 $n(G)-|M|$ 的邊覆蓋。由於最小的邊覆蓋不會大於我們建構的這個邊覆蓋，這說明了 $\beta'(G)\leq n(G) - \alpha'(G)$。此外，最大的匹配不會小於我們建構的這個匹配 $M$，這說明了 $\alpha'(G)\geq n(G) - \beta'(G)$。這兩個不等式完成了證明

### 推論 [Kőnig 1916]
若 $G$ 是一個二分圖且沒有被孤立的節點，那麼 $\alpha(G)=\beta'(G)$

#### 證明
由引理 1 與定理 1，$n(G)=\alpha(G)+\beta(G)=\alpha'(G)+\beta'(G)$。將 Kőnig 定理 $\alpha'(G)=\beta(G)$ 代入後就會得到 $\alpha(G)=\beta'(G)$

## 小結
根據 Kőnig 定理，當我們解出了二分圖的最大匹配問題，也相當於解出最大獨立集問題、最小點覆蓋問題及最小邊覆蓋問題

有意思的是，以上歸約僅限二分圖。若僅是在一般的圖中，最小點覆蓋問題與最大獨立集問題會是 NP-complete 問題，無法在多項式時間裡面解出來。而最大 (基數) 匹配問題與最小邊覆蓋問題則可以在多項式時間內解出 (詳見 Edmonds 的縮花演算法)

----

## 參考資料

- D.B.West - Introduction to Graph Theory 2/e
- [MacTutor - Dénes Kőnig](https://mathshistory.st-andrews.ac.uk/Biographies/Konig_Denes/)
- [Dénes König pronunciation in Hungarian](https://www.howtopronounce.com/hungarian/d%C3%A9nes-k%C3%B6nig-2)
- [Wikipedia - Dénes Kőnig](https://en.wikipedia.org/wiki/D%C3%A9nes_K%C5%91nig)
- [The life and scientific work of Dénes König (1884–1944)](https://www.sciencedirect.com/science/article/pii/0024379578900824)
- [Dénes Kőnig - Theory of finite and infinite graphs](https://archive.org/details/theoryoffinitein0000koni/page/50/mode/2up)
- [Kőnig's theorem (graph theory)](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory))
- [海大競程 - Classic Flow Problems](https://hackmd.io/@LeeShoWhaodian/ClassicFlowProblems#/)

----

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