柯尼希定理(圖論的柯尼希定理)

二分圖最小點覆蓋的點數=最大匹配數。

基本介紹

• 中文名：柯尼希定理
• 外文名：Konig's theorem
• 表達式：二分圖最小點覆蓋的點數=最大匹配數
• 提出者： Dénes Kőnig；Jenő Egerváry
• 提出時間：1931
• 套用學科：數學
• 適用領域範圍：圖論

定律定義

在圖論中，柯尼希定理是這樣一個定理：二分圖最小點覆蓋的點數=最大匹配數。

推導過程

假設已經找到二分圖G的一個最大匹配M，A、B為由二分圖定義所得的兩個點集，現在從B點集（A點集也行，不影響）中非飽和點（往往不止一個）出發，循著”非匹配邊->匹配邊->非匹配邊->匹配邊……”的原則走下去，沿途標記所走過的點，最後得到的邊顯然是匹配邊（這個不理解的，這裡就廢話了，要自己想。。。），且邊數為偶數，終止點是B點集的點。取A點集中標記的點與B點集中未標記的點記為點集S，那么這個點集S即為圖G的一個最小點覆蓋，且點數等於最大匹配數。到這裡有三個問題要解決：

1. 為啥S中的點能覆蓋圖G的所有邊；
   
2. 為啥S中點的個數等於最大匹配數；
   
3. 為啥S是最小的點覆蓋；
   

第一，只要說明不存在這樣的一條邊，它的左端點未標記，右端點標記就ok了，假設存在這樣的一條邊，首先它只能是非匹配邊，因為按照上述的原則會發現匹配邊的標記只能從A點集中的點出發，所以匹配邊如果有標記的必然是左右端點都標記，但是如果它是非匹配邊的話，那么就可以繼續走，走到它的未標記的左端點，這樣一來便與前述矛盾。所以，S中的點能覆蓋圖G中的所有邊。

第二，因為每個點都是匹配M某條邊的一個端點。為什麼呢？我們假設B點集中未標記的某個點沒有對應某條匹配邊，那么它早就被標記了。假設A點集中標記的點沒有對應某條匹配邊，那就走不到它那裡，因為如果可以，那么就會形成一條增廣軌了……這是最大匹配M所不允許的。又一條匹配邊或者兩端點都標記，或者都未標記，這保證了不會S中點對應的匹配邊不會重、不會漏。所以，點集S中的點與匹配M中的邊一一對應。

第三，這個就顯而易見了，因為匹配M，我們知道，覆蓋點集數至少為最大匹配數，所以點集S是最小點覆蓋集。

綜上，證明完畢。

發展簡史

1931年由Dénes Kőnig和Jenő Egerváry分別獨立提出