Knig定理，同時一個二分圖中的最大匹配數等於這個圖中的最小點覆蓋數。假如選了一個點就相當於覆蓋了以它為端點的所有邊，你需要選擇最少的點來覆蓋所有的邊。
基本介紹
- 中文名：Knig定理
- 內容：一個二分圖中很重要定理的意思
- 前提：求出了最大匹配
- 通過：匈牙利算法
證明過程
下面給出的方法可以告訴我們，選哪M個點可以覆蓋所有的邊。
匈牙利算法需要我們從右邊的某個沒有匹配的點，走出一條使得“一條沒被匹配、堡燥辨晚一條已經匹配過，再下一條又沒匹配這樣交替地出現”的路（交錯軌，增廣路）。但是，現在我們已經找到了最大匹配，已經不存在這樣的路了。換句話說，我們能尋找到很多屑船譽可能的增廣路，但最後都以找不到“終點是還沒有匹配過的點”而失敗。我們給所有這樣的點打上記號：從右邊的所有沒有匹配過的點出發，按照增廣路的“交替出現”的要求可以走到的所有點（最後走出的路徑是很多條不完整的增廣路）。那么這些點組成了最小覆蓋點集。
首先，為什麼這樣得到的點集點的個數恰好有M個呢？答案很簡單，因為每個點都是某個匹配邊的其中一個端點。如果右邊的哪個點是沒有匹配過的，那么它早就當成起點被標記了；如果左邊的哪個點是沒有匹配過的，踏抹記葛那就走不到它那裡去（如果走得到它那裡去那就找到了一條完整的增廣路）。而一個匹配邊又不可能左端點是標記了的，同時右端點是沒標記的（不然的話右邊的點就可以經過這條邊到達了）。因此，最後我們圈起來的點與匹配邊一一對應。
其次，為什麼這樣得到的櫻朽洪點集可以覆蓋所有的邊呢？答案同樣簡單。不可能存在某一條邊，它的左端點是沒有標記的，而右端點是有標記的。原因如下：如果這條邊不屬於我們的匹配邊，那么左端點就可以通過這條邊到達乘海尋（從而得到標記）；如果這條邊屬於我們的匹配邊，那么右端點不可能是一條路徑的起點，於是它的標記只能是從這條邊的左端點過來的（想想匹配的定義），左端點就應該有標記。
最後，為什麼這是最小的點覆蓋集呢？這當然是最小的，不可能有比M還小的點覆蓋集了，因為要覆蓋這M條戲拳腳匹配邊至少就需要M個點（再次回到匹配的定義）。
對兩側添加源匯點後可以從最小割最大流的角度理解。
在原圖上對所有的邊的左結點和右結點連一條容量無窮大的流（從左結點到右結點），然後再添加源匯頂點，對源點到每個左頂點添加容量為1的流，對每個右頂點到匯點添加容量為1的流。
易知，最大流即為最大匹配數。
我們來研究所有的割，我們將所有左頂點劃為A1,A2兩部分,右頂點劃為B1,B2兩部分，並研究從S並A1並B2到T並A2並B1這個割的最小取法（這個劃分方式包含了所有可能的割），如若左頂點P到右頂點Q有邊，那么最小割中顯然不會有“P屬於A1且Q屬於B1”成巴循立（否則就這一條邊割出來就是無窮大，肯定不是最小割），於是最小割中所有的邊PQ必滿足“P屬於A2或Q屬於B2”，換句話說，A2，B2中所有頂點組成這個二分圖的一個點集覆蓋。
下面觀察，我們易知，再最小割中，總的割必然等於S到A2的+B2到T的（這些是最小割中所有可能的邊了）。而S到A2+B2到T就是A2，B2中所有頂點的個數總和，所以最小割就是滿足題意（A2並B2構成最小點集覆蓋）的A2並B2中頂點最少的情況，亦即最小點集覆蓋，於是乎：
最大匹配數=最大流=最小割=最小點集覆蓋
