出處:http://www.matrix67.com/blog/archives/116

二分圖最大匹配的K?nig定理及其證明

????如果你看不清楚第二個字母，下面有一個大號字體版本：

二分圖最大匹配的K?nig定理及其證明

????本文將是這一系列里最短的一篇，因為我只打算把K?nig定理證了，其它的廢話一概沒有。
????以下五個問題我可能會在以后的文章里說，如果你現在很想知道的話，網上去找找答案：
????1. 什么是二分圖；
????2. 什么是二分圖的匹配；
????3. 什么是匈牙利算法；(http://www.matrix67.com/blog/article.asp?id=41)
????4. K?nig定理證到了有什么用；
????5. 為什么o上面有兩個點。

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



????假如我們已經通過匈牙利算法求出了最大匹配（假設它等于M），下面給出的方法可以告訴我們，選哪M個點可以覆蓋所有的邊。
????匈牙利算法需要我們從右邊的某個沒有匹配的點，走出一條使得“一條沒被匹配、一條已經匹配過，再下一條又沒匹配這樣交替地出現”的路（交錯軌，增廣路）。但是，現在我們已經找到了最大匹配，已經不存在這樣的路了。換句話說，我們能尋找到很多可能的增廣路，但最后都以找不到“終點是還沒有匹配過的點”而失敗。我們給所有這樣的點打上記號：從右邊的所有沒有匹配過的點出發，按照增廣路的“交替出現”的要求可以走到的所有點（最后走出的路徑是很多條不完整的增廣路）。那么這些點組成了最小覆蓋點集：右邊所有沒有打上記號的點，加上左邊已經有記號的點?？磮D，右圖中展示了兩條這樣的路徑，標記了一共6個點（用 “√”表示）。那么，用紅色圈起來的三個點就是我們的最小覆蓋點集。
????首先，為什么這樣得到的點集點的個數恰好有M個呢？答案很簡單，因為每個點都是某個匹配邊的其中一個端點。如果右邊的哪個點是沒有匹配過的，那么它早就當成起點被標記了；如果左邊的哪個點是沒有匹配過的，那就走不到它那里去（否則就找到了一條完整的增廣路）。而一個匹配邊又不可能左端點是標記了的，同時右端點是沒標記的（不然的話右邊的點就可以經過這條邊到達了）。因此，最后我們圈起來的點與匹配邊一一對應。
????其次，為什么這樣得到的點集可以覆蓋所有的邊呢？答案同樣簡單。不可能存在某一條邊，它的左端點是沒有標記的，而右端點是有標記的。原因如下：如果這條邊不屬于我們的匹配邊，那么左端點就可以通過這條邊到達（從而得到標記）；如果這條邊屬于我們的匹配邊，那么右端點不可能是一條路徑的起點，于是它的標記只能是從這條邊的左端點過來的（想想匹配的定義），左端點就應該有標記。
????最后，為什么這是最小的點覆蓋集呢？這當然是最小的，不可能有比M還小的點覆蓋集了，因為要覆蓋這M條匹配邊至少就需要M個點（再次回到匹配的定義）。
????證完了。
??
Matrix67原創
做人要厚到 轉貼請注明出處

轉載于:https://www.cnblogs.com/wzb-hust/p/4896092.html

總結

以上是生活随笔為你收集整理的（转）二分图最大匹配的König定理及其证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。