第四百五十三章 柯尼希定理（圖論）

　　柯尼希定理由 XDénes K?nig 于1931年提出的圖論領(lǐng)域的定理，用于說明在二分圖中最小點覆蓋的點數(shù)于最大匹配數(shù)的相等性。此外Jen? Egerváry在同年同樣獨立地將其提出，并拓展到了有權(quán)圖的范圍。

　　柯尼希知道的圖論的重要性，開始研究圖論，從最簡單的二分圖入手。

　　柯尼希說：“二分圖是一種可以把點集分成兩部分，每一部分不能有線相連，只能讓這兩個部分有線相連?！?p>　　XDénes K?nig說：“如果一個匹配中，圖中的每個頂點都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配?！?p>　　柯尼希說：“最小點覆蓋的點數(shù)等于最大匹配數(shù)?！?p>　　XDénes K?nig為了驗證柯尼希的說法，開始自己畫圖連線。

　　我們稱下圖中的下部分點集合為L，上部分的點集合為R。從左至右給下部分的每個點標(biāo)號為1，…，7；并給上部分的點標(biāo)號為8，…，14。令U為L中未匹配的點的集合，U={1}。從U出發(fā)的增廣路徑為1-10-3-13-7， 1-10-3-11-5-13-7， 1-11-5-13-7， 1-11-5-10-3-13-7及它們的子路徑，那么構(gòu)造性證明中的集合Z為{1，3，5，7，10，11，13}，可以得到L\Z={2，4，6}，R∩Z={10，11，13}，所以最小覆蓋K={2，4，6，10，11，13}。