柯尼希定理 (圖論)
在圖論中， 柯尼希定理是指二部圖的最大的匹配數與最小的頂點覆蓋數相等。該定理以猶太裔匈牙利數學柯尼希·德納什的名字命名。1931年，匈牙利數學家艾蓋瓦里·耶內獨立發現了該定理在加權圖的情形下更一般的形式。
匹配與覆蓋 編輯
圖的頂點覆蓋是指它的一個頂點集，該圖的每一條邊都至少有一個端點在這個頂點集中。如果該圖沒有一個點數更少的頂點覆蓋，則稱其為最小頂點覆蓋。[1]
圖的匹配是指一個邊的集合，每兩條邊都沒有公共頂點。一個匹配稱為最大匹配，如果不存在一個邊數更多的匹配。[2]
對於匹配的每一條邊，頂點覆蓋中至少有一個頂點為此邊的端點，因此任何頂點覆蓋集的元素個數都大於等於所有匹配集的元素個數。柯尼希定理表明對於二部圖，這兩個集合元素大小相同。
定理的陳述 編輯
證明 編輯
設 是一個最大匹配，因為頂點覆蓋大於等於匹配集的大小，因此我們只需構造一個大小為 的頂點覆蓋。構造如下：
將二部圖的兩部分分別記為 A 和 B。一個圖關於匹配 M 的交錯路（alternating path）是指一條從圖中一個非匹配頂點出發，邊在匹配集 M 與 中交錯出現的道路。[4]取頂點集 U 如下：對於 M 的每條邊，如果存在一條交錯路終止於該邊在 B 中的端點，那麼該端點屬於 U，否則該邊在 A 中的端點屬於 U。因爲 U 里每一個頂點都與 M 的一條邊一一對應，所以 。因此我們只需要證明 U 為一個頂點覆蓋。
假設有一條邊 ab 沒有被 U 覆蓋，即 都不在 U 中。如果 a 不是某一匹配的端點，那麼 ab 本身就是一條從非匹配頂點出發的交錯路，那麼 ，矛盾。如果 a 屬於某個匹配 ab'，那麼 。這樣， 就是一條交錯路，從而 ，矛盾。
參考文獻 編輯
- ^ 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 等人 (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.
