柯尼希定理

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

下面的證明提供了一種從最大匹配構造最小頂點覆蓋的方法。

設G=(V,E)是一個二部圖，設L,R是頂點集V的兩個部分。假設M是G的一個最大匹配。在一個頂點覆蓋中，沒有一個頂點可以覆蓋M的一條以上的邊(M是一個匹配，所以不存在邊的半重疊情況)，所以如果可以被構造出一個有|M|個頂點的頂點覆蓋，那麼它一定是一個最小覆蓋。 ^[1] 

下面我們構造一個上述頂點覆蓋。設U是頂點集L中未被匹配的頂點的集合（U可能是空集，此時L中的所有頂點都在匹配M中）。設頂點集Z是頂點集U中的頂點通過M交錯路相連點的集合。如下關係式取頂點集K：

K = ( L \ Z ) ∪ ( R ∩ Z )

對於邊集E中的任意邊e , 邊e如果不是一個M交錯路的一部分，則它的左頂點屬於頂點集K。接下來我們證明這一點。如果e是匹配M中的邊但不在M交錯路中，那麼它的左頂點不可能在M交錯路中（因為根據匹配的定義，兩條同一匹配中的邊不能共享一個頂點），也就是説e的左頂點屬於L \ Z。在另一種情況中，e既不屬於匹配M也不在M交錯路中，那麼顯然e的左端點不能在M交錯路中，否則這條M交錯路可以通過添加邊e進行擴展。因此，K是一個頂點覆蓋。 ^[1] 

此外，K中的每個頂點都是一條匹配邊的頂點。這是因為L \ Z中的每個頂點都是匹配的。而 R∩Z 中的每個頂點也必須是匹配的，因為如果存在一條與未匹配的頂點交替的M交錯路，那麼通過刪除該路徑上匹配的邊，在原有位置上添加未匹配的邊來改變匹配，會增加匹配的大小。然而，任何匹配中的邊都不能有兩個端點都在K中。 ^[1] 

因此，K是一個最小的頂點覆蓋。

構造性證明提供了一個用於在給定最大匹配情況下尋找最小點覆蓋的算法。因此，Hopcroft-Krap algorithm，一個用於尋找二分圖上最大匹配的算法，同樣可以有效的解決點覆蓋問題。

我們稱下圖中的下部分點集合為L，上部分的點集合為R。從左至右給下部分的每個點標號為1,…,7；並給上部分的點標號為8,…,14。令U為L中未匹配的點的集合，U={1}。從U出發的增廣路徑為1-10-3-13-7, 1-10-3-11-5-13-7, 1-11-5-13-7, 1-11-5-10-3-13-7及它們的子路徑，那麼構造性證明中的集合Z為{1,3,5,7,10,11,13}，可以得到L\Z={2,4,6},

所以最小點覆蓋

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