柯尼希定理 (圖論)

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

例如，在圖中的二部圖中，最大匹配（藍邊）和最小頂點覆蓋（紅點）數均為 6。

匹配與覆蓋

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

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

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

定理的陳述

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

證明

如圖粗線代表匹配 M，紅點代表集合 U

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

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

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

參考文獻

1. Called a covering and a minimum covering respectively by Bondy & Murty (1976), p. 73.
2. Bondy & Murty (1976), p. 70.
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.

參考

• 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.