Kőnig 定理

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

建議先讀完另一篇筆記匹配與霍爾定理再來看這篇，因本篇會使用到霍爾定理的結論來證明

注: 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)$

$$
如上圖，

$G$ 共有

$6$ 個節點，而其中

$2$ 個節點 (以方框表示) 可以覆蓋所有的邊。而黑邊會形成一組大小為

$2$ 的最大匹配

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

邊覆蓋 Edge Cover

一張圖

$G=(V,E)$ 的邊覆蓋是一個邊集合

$L$，所有節點都會與

$L$ 中的一些邊相鄰

$$
如上圖，

$4$ 條藍色的邊都是

$L$ 裡的邊，可以說這些藍邊覆蓋了所有節點。而方框裡的節點可以形成大小為

$4$ 的獨立集

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

Kőnig 定理 Kőnig's Theorem

此定理的一般化又稱作 Kőnig-Egerváry theorem

敘述

如果

$G$ 是一張二分圖，則

$G$ 的最大匹配會等於最小點覆蓋

證明

令

$G$ 為一張

$X,Y$ 二分圖。由於不同的節點會被用於邊的匹配，對於點覆蓋

$Q$ 與匹配

$M$，

$|Q|\ge |M|$。我們可以給一個最小點覆蓋

$Q$，然後再建構一個大小為

$|Q|$ 的匹配來證明他們是等價的

令

$R=X\cap Q$、

$T=Y\cap Q$。再令

$H=R\cup (Y-T)$ 與

$H^{\prime }=T\cup (X-R)$ 為

$G$ 的子圖。我們可以使用霍爾定理來說明說

$H$ 有一個匹配會使

$R$ 配到

$Y-T$，也可以說明

$H^{\prime }$ 有一個匹配會使

$T$ 飽和。由於

$H$ 與

$H^{\prime }$ 是互斥的，兩者的匹配會形成一個大小為

$|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^{\prime }$ 會產生一匹配使

$T$ 飽和

圖源 : D.B.West - Introduction to Graph Theory 2/e p.113

覆蓋的補圖 The Completement of Covers

名詞定義

$\alpha (G)$ : 代表最大獨立集

${\alpha }^{\prime }(G)$ : 代表最大匹配

$\beta (G)$ : 代表最小點覆蓋

${\beta }^{\prime }(G)$ : 代表最小邊覆蓋

以符號表示 Kőnig 定理

對於一張二分圖來說，

${\alpha }^{\prime }(G)=\beta (G)$

引理 1

在一張圖

$G$ 中，

$S\subseteq V(G)$ 為一獨立集，若且為若

$\overline{S}$ 是一個點覆蓋，因此

$\alpha (G)+\beta (G)=n(G)$

證明

如果

$S$ 是一個獨立集，那麼每條邊與最少與一個

$\overline{S}$ 中的節點相鄰。反之，如果

$\overline{S}$ 覆蓋所有節點，那麼就不會有邊將

$S$ 地點相鄰。因此所有對大獨立集是最小點覆蓋的補集 (complement)，且

$\alpha (G)+\beta (G)=n(G)$

定理 1 [Gallai 1959]

若

$G$ 是一張沒有孤立的節點的圖，那麼

${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)=n(G)$

證明

從一個最大匹配

$M$，我們可以建構一個大小為

$n(G)-|M|$ 的邊覆蓋。由於最小的邊覆蓋不會大於我們建構的這個邊覆蓋，這說明了

${\beta }^{\prime }(G)\le n(G)-{\alpha }^{\prime }(G)$。此外，最大的匹配不會小於我們建構的這個匹配

$M$，這說明了

${\alpha }^{\prime }(G)\ge n(G)-{\beta }^{\prime }(G)$。這兩個不等式完成了證明

推論 [Kőnig 1916]

若

$G$ 是一個二分圖且沒有被孤立的節點，那麼

$\alpha (G)={\beta }^{\prime }(G)$

證明

由引理 1 與定理 1，

$n(G)=\alpha (G)+\beta (G)={\alpha }^{\prime }(G)+{\beta }^{\prime }(G)$。將 Kőnig 定理

${\alpha }^{\prime }(G)=\beta (G)$ 代入後就會得到

$\alpha (G)={\beta }^{\prime }(G)$

小結

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

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

---

參考資料

• D.B.West - Introduction to Graph Theory 2/e
• MacTutor - Dénes Kőnig
• Dénes König pronunciation in Hungarian
• Wikipedia - Dénes Kőnig
• The life and scientific work of Dénes König (1884–1944)
• Dénes Kőnig - Theory of finite and infinite graphs
• Kőnig's theorem (graph theory)
• 海大競程 - Classic Flow Problems

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2025/1/21