轉載:二部圖最小覆寫點集等于最大比對-----König定理及其證明

二分圖最大比對的König定理及其證明

    König定理是一個二分圖中很重要的定理，它的意思是，一個二分圖中的最大比對數等于這個圖中的最小點覆寫數。如果你還不知道什麼是最小點覆寫，我也在這裡說一下：假如選了一個點就相當于覆寫了以它為端點的所有邊，你需要選擇最少的點來覆寫所有的邊。比如，下面這個圖中的最大比對和最小點覆寫已分别用藍色和紅色标注。它們都等于3。這個定理相信大多數人都知道，但是網絡上給出的證明并不多見。有一些網上常見的“證明”明顯是錯誤的。是以，我在這裡寫一下這個定理的證明，希望對大家有所幫助。

    假如我們已經通過匈牙利算法求出了最大比對（假設它等于M），下面給出的方法可以告訴我們，選哪M個點可以覆寫所有的邊。

    匈牙利算法需要我們從右邊的某個沒有比對的點，走出一條使得“一條沒被比對、一條已經比對過，再下一條又沒比對這樣交替地出現”的路（交錯軌，增廣路）。但是，現在我們已經找到了最大比對，已經不存在這樣的路了。換句話說，我們能尋找到很多可能的增廣路，但最後都以找不到“終點是還沒有比對過的點”而失敗。我們給所有這樣的點打上記号：從右邊的所有沒有比對過的點出發，按照增廣路的“交替出現”的要求可以走到的所有點（最後走出的路徑是很多條不完整的增廣路）。那麼這些點組成了最小覆寫點集：右邊所有沒有打上記号的點，加上左邊已經有記号的點。看圖，右圖中展示了兩條這樣的路徑，标記了一共6個點（用 “√”表示）。那麼，用紅色圈起來的三個點就是我們的最小覆寫點集。

    首先，為什麼這樣得到的點集點的個數恰好有M個呢？答案很簡單，因為每個點都是某個比對邊的其中一個端點。如果右邊的哪個點是沒有比對過的，那麼它早就當成起點被标記了；如果左邊的哪個點是沒有比對過的，那就走不到它那裡去（否則就找到了一條完整的增廣路）。而一個比對邊又不可能左端點是标記了的，同時右端點是沒标記的（不然的話右邊的點就可以經過這條邊到達了）。是以，最後我們圈起來的點與比對邊一一對應。

    其次，為什麼這樣得到的點集可以覆寫所有的邊呢？答案同樣簡單。不可能存在某一條邊，它的左端點是沒有标記的，而右端點是有标記的。原因如下：如果這條邊不屬于我們的比對邊，那麼左端點就可以通過這條邊到達（進而得到标記）；如果這條邊屬于我們的比對邊，那麼右端點不可能是一條路徑的起點，于是它的标記隻能是從這條邊的左端點過來的（想想比對的定義），左端點就應該有标記。