柯尼希定理 (圖論)

在圖論中， 柯尼希定理是指二部圖的最大的匹配數與最小的頂點覆蓋數相等。該定理以猶太裔匈牙利數學柯尼希·德納什（英語：Dénes Kőnig）的名字命名。1931年，匈牙利數學家艾蓋瓦里·耶內獨立發現了該定理在加權圖的情形下更一般的形式。

匹配與覆蓋

圖的頂點覆蓋是指它的一個頂點集，該圖的每一條邊都至少有一個端點在這個頂點集中。如果該圖沒有一個點數更少的頂點覆蓋，則稱其為最小頂點覆蓋。^[1]

圖的匹配是指一個邊的集合，每兩條邊都沒有公共頂點。一個匹配稱為最大匹配，如果不存在一個邊數更多的匹配。^[2]

對於匹配的每一條邊，頂點覆蓋中至少有一個頂點為此邊的端點，因此任何頂點覆蓋集的元素個數都大於等於所有匹配集的元素個數。柯尼希定理表明對於二部圖，這兩個集合元素大小相同。

定理的陳述

在任意二部圖中，最大匹配的邊數等於最小頂點覆蓋的頂點數。 ^[3]

證明

設 $M$ 是一個最大匹配，因為頂點覆蓋大於等於匹配集的大小，因此我們只需構造一個大小為 $|M|$ 的頂點覆蓋。構造如下：

將二部圖的兩部分分別記為 A 和 B。一個圖關於匹配 M 的交錯路（alternating path）是指一條從圖中一個非匹配頂點出發，邊在匹配集 M 與 $E\backslash M$ 中交錯出現的道路。^[4]取頂點集 U 如下：對於 M 的每條邊，如果存在一條交錯路終止於該邊在 B 中的端點，那麼該端點屬於 U，否則該邊在 A 中的端點屬於 U。因爲 U 里每一個頂點都與 M 的一條邊一一對應，所以 $|U|=|M|$ 。因此我們只需要證明 U 為一個頂點覆蓋。

假設有一條邊 ab 沒有被 U 覆蓋，即 $a\in A,b\in B$ 都不在 U 中。如果 a 不是某一匹配的端點，那麼 ab 本身就是一條從非匹配頂點出發的交錯路，那麼 $b\in U$ ，矛盾。如果 a 屬於某個匹配 ab'，那麼 $b'\in U$ 。這樣， $Pb'ab$ 就是一條交錯路，從而 $b\in U$ ，矛盾。

參考文獻

^ Called a covering and a minimum covering respectively by Bondy & Murty (1976), p. 73.
^ Bondy & Murty (1976), p. 70.
^ Bondy & Murty (1976), Theorem 5.3, p. 74; Cook et al. (2011).
^ Diestel, Reinhard. 图论 Graph Theory. 由於, 青林翻譯. 北京: 科學出版社. 2020: 32. ISBN 978-7-03-064807-5.

參考

Biggs, E. K.; Lloyd; Wilson, R. J., Graph Theory 1736–1936, Oxford University Press: 203–207, 1976, ISBN 0-19-853916-9 .
Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander, Combinatorial Optimization, Wiley Series in Discrete Mathematics and Optimization 33, John Wiley & Sons: 48–49, 2011, ISBN 9781118031391 .
Bondy, J. A.; Murty, U. S. R., Graph Theory with Applications, North Holland, 1976, ISBN 0-444-19451-7 .
Gallai, Tibor, Maximum-minimum Sätze über Graphen, Acta Mathematica Academiae Scientiarum Hungaricae, 1958, 9 (3–4): 395–434, MR 0124238, doi:10.1007/BF02020271 .
Göös, Mika; Suomela, Jukka, No sublogarithmic-time approximation scheme for bipartite vertex cover, Distributed Computing, 2014, 27 (6): 435–443, MR 3280546, arXiv:1205.4605 , doi:10.1007/s00446-013-0194-z
Kőnig, Dénes, Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére, Matematikai és Természettudományi Értesítő, 1916, 34: 104–119 .
Kőnig, Dénes, Gráfok és mátrixok, Matematikai és Fizikai Lapok, 1931, 38: 116–119 .
Lovász, László, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, 1972, 2 (3): 253–267, MR 0302480, doi:10.1016/0012-365X(72)90006-4 .
Lovász, László, Minimax theorems for hypergraphs, Hypergraph Seminar (Proc. First Working Sem., Ohio State Univ., Columbus, Ohio, 1972; dedicated to Arnold Ross), Lecture Notes in Mathematics 411, Berlin: Springer: 111–126, 1974, MR 0406862, doi:10.1007/BFb0066186 .
Storer, J. A., An Introduction to Data Structures and Algorithms, Progress in Computer Science and Applied Logic Series, Springer, 2001, ISBN 9780817642532 .

[1] Called a covering and a minimum covering respectively by Bondy & Murty (1976), p. 73.

[2] Bondy & Murty (1976), p. 70.

[thm-stmt-3] Bondy & Murty (1976), Theorem 5.3, p. 74; Cook et al. (2011).

[4] Diestel, Reinhard. 图论 Graph Theory. 由於, 青林翻譯. 北京: 科學出版社. 2020: 32. ISBN 978-7-03-064807-5.

[1]

[2]

[3]

[4]