完美圖定理
此條目可參照英語維基百科相應條目來擴充。 (2020年5月3日) |
此條目需要補充更多來源。 (2020年5月3日) |
在圖論中，完美圖定理（由洛瓦茲·拉茲洛證明László Lovász （1972a, 1972b））斷言：一個無向圖是完美的若且唯若其補圖也是完美的。這個結論一度是Claude Berge提出的猜想。它有時也被稱為弱完美圖定理，以和強完美圖定理[1]作區分。強完美圖定理通過禁止導出子圖來刻畫完美圖。
定理敘述
一個完美圖是具有下述性質的無向圖：在其每個導出子圖中，最大團的頂點數都等於對該導出子圖的着色的顏色數的最小值。完美圖包括了很多重要類型的圖，例如二分圖、弦圖和可比圖。
一個圖的補圖在某兩個頂點之間連一條邊若且唯若原圖在這兩個頂點之間沒有連邊。從而原圖中的團成為其補圖中的獨立集，而原圖的一個染色成為其補圖的一個團覆蓋。
完美圖定理斷言：完美圖的補圖也是完美的。
等價地，在完美圖中，最大獨立集的頂點數等於其團覆蓋中團個數的最小值。
例子
令G是一個長度為大於3的奇數的循環圖（洞），則G的任何染色需要至少3種顏色，但G不含有三角形，所以它不是完美的。由完美圖定理，G的補圖（一個奇數長度的反洞）肯定也不是完美的。如果G是一個長度為5的圈，則它是一個自補圖，但此性質對更大的奇數長度不再成立，而對於奇數個頂點的反洞計算其團數和色數也不像對於奇數個頂點的循環圖那麼容易。強完美圖定理指出，奇數長度的洞和反洞是完美圖的最小的禁止導出子圖。
應用
在一個非平凡的二分圖中，由定義染色所需的顏色數最小是2，而由於二分圖中不含有三角形，其團數也是2。而二分圖的任何導出子圖還是二分圖。所以二分圖是完美的。在有n個頂點的二分圖中，一個最小團覆蓋需要一個最大匹配加上另一些團，每個對應於一個未匹配頂點，其中團的個數等於n-M，這裏M是最大匹配的邊數。於是在這個例子中完美圖定理可以推出柯尼希定理 (圖論)，即有n個頂點的二分圖的最大獨立集的頂點數也是n-M[2]
洛瓦茲的證明
和強完美圖定理的關係
Chudnovsky et al. (2006)得到的強完美圖定理斷言一個圖是完美的若且唯若其所有導出子圖和它們的補圖都不是長度為大於等於5的奇數的循環圖。由於此條件在取補圖後不變，強完美圖定理可以直接推出（弱）完美圖定理。
推廣
Cameron, Edmonds & Lovász (1986)證明，如果一個完全圖的所有邊被分成三個導出子圖，使得任何三個頂點都在其中一個導出子圖中連通，且兩個導出子圖是完美的，則第三個導出子圖必然也是完美的。完美圖定理是這個結果在其中一個導出子圖是空圖時的特例。
註釋
- ^ 強完美圖定理也是Claude Berge的猜想之一，但在多年之後的2006年才被Chudnovsky-Robertson-Seymour-ThomasChudnovsky et al. (2006)證明。
- ^ Kőnig (1931), 後來被Gallai (1958)重新得到。
參考文獻
- Berge, Claude, Färbung von Graphen, deren sämtliche beziehungsweise deren ungerade Kreise starr sind, Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-naturwissenschaftliche Reihe, 1961, 10: 114 （德語）.
- Berge, Claude, Perfect graphs, Six Papers on Graph Theory, Calcutta: Indian Statistical Institute: 1–21, 1963.
- Cameron, K.; Edmonds, J.; Lovász, L., A note on perfect graphs, Periodica Mathematica Hungarica, 1986, 17 (3): 173–175, MR 0859346, doi:10.1007/BF01848646.
- Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, The strong perfect graph theorem, Annals of Mathematics, 2006, 164 (1): 51–229, MR 2233847, arXiv:math/0212070
, doi:10.4007/annals.2006.164.51. - Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin, Progress on perfect graphs (PDF), Mathematical Programming, Series B., 2003, 97 (1-2): 405–422 [2020-05-03], MR 2004404, doi:10.1007/s10107-003-0449-8, （原始內容存檔 (PDF)於2010-07-31）.
- 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 （德語）
- Golumbic, Martin Charles, 3.2. The perfect graph theorem, Algorithmic Graph Theory and Perfect Graphs, New York: Academic Press: 53–58, 1980, ISBN 0-12-289260-7, MR 0562306.
- 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, 1972a, 2 (3): 253–267, doi:10.1016/0012-365X(72)90006-4.
- Lovász, László, A characterization of perfect graphs, Journal of Combinatorial Theory, Series B, 1972b, 13 (2): 95–98, doi:10.1016/0095-8956(72)90045-7.
- Reed, Bruce A., From conjecture to theorem, Ramírez Alfonsín, Jorge L.; Reed, Bruce A. (編), Perfect Graphs, Wiley-Interscience Series on Discrete Mathematics and Optimization, Chichester: Wiley: 13–24, 2001, MR 1861356.
