圖子式

在圖論中，如果無向圖H可以通過圖G刪除邊和頂點或收縮邊得到，則稱H為G的子式（minor）或次圖。

圖子式的提出源自瓦格納定理，這個定理表明：若且唯若一個圖不存在完全圖K₅和完全二分圖K_3,3的子式時，這個圖才是平面圖。^[1] 羅伯遜-西摩定理（英語：Robertson–Seymour theorem）表明，對於任何在圖上刪除點或邊或收縮邊保留的性質，類似的禁子式表徵（英語：forbidden minor characterization）（forbidden minor characterization）也存在。^[2] 給定圖G和圖H，可以在多項式時間內判斷H是否是G的子式。^[3] 連同上述禁子式表徵，這意味着任何刪除點或邊和收縮邊保留的圖的屬性可以在多項式時間內被識別。^[4] 其他涉及到圖子式的定理和猜想包括圖結構定理（英語：graph structure theorem）、Hadwiger猜想（英語：Hadwiger conjecture (graph_theory)）等。

定義

邊收縮（contraction）是在圖上移除一條邊同時合併這條邊的兩個鄰點。一個無向圖H是另一個無向圖G的子式，如果G通過一系列的收縮邊、刪除邊、刪除孤立點可以得到一個同構於H的圖。這一系列收縮和刪除操作的順序不影響最後得到的圖H。

例子

H是G的子式：

H.

G.

以下顯示了如何構造子式。首先去除圖G中虛線邊，再去掉孤立的頂點，最後對灰色邊進行邊收縮即得到圖H。

主要結論和猜想

可以很直接地驗證，在同構意義上，圖子式關係是一個偏序關係：它滿足自反性（自己是自己的子式）、反對稱性（圖G和H互為子式僅當它們同構）、傳遞性（圖G的子式的子式也是圖G的子式）。尼爾·羅伯遜（英語：Neil Robertson (mathematician)）和保羅·西摩（英語：Paul Seymour (mathematician)）提出了一個更深刻的結論：圖子式關係實際上是一種良擬序關係：給定一串無窮的圖序列G₁, G₂,...總是存在i < j，使得 G_i是G_j的子式。一個等價的表述是，任意的一簇圖的集合必然只有有限個子式意義下的極小元^[5]。這個結論驗證了先前的一個猜想：瓦格納猜想。它很早就被克拉斯·瓦格納（英語：Klaus Wagner）提出，直至1970年才發表。^[6]

在他們證明的過程中，西摩和羅伯遜也同時證明了圖結構定理（英語：graph structure theorem）。對於一個給定的圖H，這個定理刻畫了不包含H-子式的圖的結構。這個定理的嚴格表述又長又複雜，但是簡而言之，它證明了這樣一個圖必須具有由嵌在有界虧格曲面上的圖以小方式修改而成的圖的團和（英語：Clique-sum）結構。因此，他們的理論建立了圖子式和圖的拓撲嵌入之間的基本聯繫。^[7]

對於任意圖H，無H-子式的簡單圖必須是稀疏的，即圖的邊數小於等於一個常數倍的圖的階數^[8]。更精確地，如果圖H有h個點，那麼有n個頂點的不包含H-子式的簡單圖G有至多${\displaystyle \scriptstyle O(nh{\sqrt {\log h}})}$條邊。不包含K_h-子式的圖至少有這麼多條邊。^[9]因此，G的平均度是${\displaystyle \scriptstyle O(h{\sqrt {\log h}})}$級別的。更進一步，不包含H-子式的圖有一個和平面圖分割定理（英語：planar separator theorem）類似的分割定理：給定H和任意不包含H-子式的n階圖G，可以找到${\displaystyle \scriptstyle O({\sqrt {n}})}$個G的頂點，使得刪除這些點可以將G分成兩個（可能不連通的）子圖，使得每個子圖有至多2n/3個頂點。^[10]更強的結論是，對於任意的圖H，不包含H-子式的n階圖G的樹寬是${\displaystyle \scriptstyle O({\sqrt {n}})}$數量級的。^[11]

Hadwiger猜想（英語：Hadwiger conjecture (graph_theory)）表明，如果圖G不包含k階完全圖子式，那麼G可以被(k − 1)-着色^[12]。k = 5的情況即為四色定理。Hadwiger猜想在k ≤ 6的情況下已經被證實^[13]，但是更一般的情況下還沒有定論。Bollobás, Catlin & Erdős (1980) 稱它為「圖論中最深刻的尚未解決的問題之一」。另一個將四色定理和圖子式聯繫起來的猜想是snark猜想（英語：Snark (graph theory)），它表明任意無割邊的3-正則圖，如果它的邊色數等於4，那麼佩特森圖一定是它的子式。^[14]

參見

• 瓦格納定理
• 細分
• 邊收縮
• 串並圖
• 子圖
• 圖論術語

註釋

1. Lovász (2006), p. 77; Wagner (1937a).
2. Lovász (2006), theorem 4, p. 78; Robertson & Seymour (2004).
3. Robertson & Seymour (1995).
4. Fellows & Langston (1988).
5. Diestel (2005), Chapter 12: Minors, Trees, and WQO; Robertson & Seymour (2004).
6. Lovász (2006), p. 76.
7. Lovász (2006), pp. 80–82; Robertson & Seymour (2003).
8. Mader (1967).
9. Kostochka (1982); Kostochka (1984); Thomason (1984); Thomason (2001).
10. Alon, Seymour & Thomas (1990); Plotkin, Rao & Smith (1994); Reed & Wood (2009).
11. Grohe (2003)
12. Hadwiger (1943)
13. Robertson, Seymour & Thomas (1993).
14. Thomas (1999); Pegg (2002).

參考文獻

• Alon, Noga; Seymour, Paul; Thomas, Robin, A separator theorem for nonplanar graphs, Journal of the American Mathematical Society, 1990, 3 (4): 801–808 [2019-04-25], JSTOR 1990903, MR 1065053, doi:10.2307/1990903, （原始內容存檔於2019-02-14） （英語）.
• Błasiok, Jarosław; Kamiński, Marcin; Raymond, Jean-Florent; Trunck, Théophile, Induced minors and well-quasi-ordering, Bibcode:2015arXiv151007135B, arXiv:1510.07135  （英語）.
• Bollobás, B.; Catlin, P. A.; Erdős, Paul, Hadwiger's conjecture is true for almost every graph (PDF), European Journal of Combinatorics, 1980, 1: 195–199 [2019-04-25], doi:10.1016/s0195-6698(80)80001-1, （原始內容 (PDF)存檔於2009-03-18） （英語）.
• Buchheim, Christoph; Chimani, Markus; Gutwenger, Carsten; Jünger, Michael; Mutzel, Petra, Crossings and planarization, Tamassia, Roberto (編), Handbook of Graph Drawing and Visualization, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2014 （英語）.
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi, Diameter and treewidth in minor-closed graph families, revisited, Algorithmica, 2004, 40 (3): 211–215 [2019-04-25], doi:10.1007/s00453-004-1106-1, （原始內容存檔於2019-09-20） （英語）.
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M., 1.5-Approximation for treewidth of graphs excluding a graph with one crossing as a minor, Proc. 5th International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX 2002), Lecture Notes in Computer Science 2462, Springer-Verlag: 67–80, 2002, doi:10.1007/3-540-45753-4_8 （英語）
• Diestel, Reinhard, Graph Theory 3rd, Berlin, New York: Springer-Verlag, 2005 [2019-04-25], ISBN 978-3-540-26183-4, （原始內容存檔於2011-07-28） （英語）.
• Ding, Guoli, Excluding a long double path minor, Journal of Combinatorial Theory, Series B, 1996, 66 (1): 11–23, MR 1368512, doi:10.1006/jctb.1996.0002 （英語）.
• Eppstein, David, Diameter and treewidth in minor-closed graph families, Algorithmica, 2000, 27: 275–291, MR 1759751, arXiv:math.CO/9907126 , doi:10.1007/s004530010020 （英語）.
• Fellows, Michael R.; Langston, Michael A., Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM, 1988, 35 (3): 727–739, doi:10.1145/44483.44491 （英語）.
• Grohe, Martin, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 2003, 23 (4): 613–632, arXiv:math/0001128 , doi:10.1007/s00493-003-0037-9 （英語）.
• Hadwiger, Hugo, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich, 1943, 88: 133–143 （英語）.
• Hall, Dick Wick, A note on primitive skew curves, Bulletin of the American Mathematical Society, 1943, 49 (12): 935–936, doi:10.1090/S0002-9904-1943-08065-2 （英語）.
• Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce, The disjoint paths problem in quadratic time, Journal of Combinatorial Theory, Series B, March 2012, 102 (2): 424–435, doi:10.1016/j.jctb.2011.07.004 （英語）
• Kostochka, Alexandr V., The minimum Hadwiger number for graphs with a given mean degree of vertices, Metody Diskret. Analiz., 1982, 38: 37–58 （俄語）.
• Kostochka, Alexandr V., Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica, 1984, 4: 307–316, doi:10.1007/BF02579141 （英語）.
• Lovász, László, Graph minor theory, Bulletin of the American Mathematical Society, 2006, 43 (1): 75–86, doi:10.1090/S0273-0979-05-01088-8 （英語）.
• Mader, Wolfgang, Homomorphieeigenschaften und mittlere Kantendichte von Graphen, Mathematische Annalen, 1967, 174 (4): 265–268, doi:10.1007/BF01364272 （英語）.
• Nešetřil, Jaroslav; Ossona de Mendez, Patrice, Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Springer: 62–65, 2012, ISBN 978-3-642-27874-7, MR 2920058, doi:10.1007/978-3-642-27875-4 （英語）.
• Pegg, Ed, Jr., Book Review: The Colossal Book of Mathematics (PDF), Notices of the American Mathematical Society, 2002, 49 (9): 1084–1086 [2019-04-25], Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756, （原始內容存檔 (PDF)於2019-04-02） （英語）.
• Plotkin, Serge; Rao, Satish; Smith, Warren D., Shallow excluded minors and improved graph decompositions, Proc. 5th ACM–SIAM Symp. on Discrete Algorithms (SODA 1994): 462–470, 1994 （英語）.
• Reed, Bruce; Wood, David R., A linear-time algorithm to find a separator in a graph excluding a minor, ACM Transactions on Algorithms, 2009, 5 (4): Article 39, doi:10.1145/1597036.1597043 （英語）.
• Robertson, Neil; Seymour, Paul, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, 1983, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5 （英語）.
• Robertson, Neil; Seymour, Paul D., Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory, Series B, 1986, 41 (1): 92–114, doi:10.1016/0095-8956(86)90030-4 （英語）
• Robertson, Neil; Seymour, Paul D., Excluding a graph with one crossing, Robertson, Neil; Seymour, Paul (編), Graph Structure Theory: Proc. AMS–IMS–SIAM Joint Summer Research Conference on Graph Minors, Contemporary Mathematics 147, American Mathematical Society: 669–675, 1993 （英語）.
• Robertson, Neil; Seymour, Paul D., Graph Minors. XIII. The disjoint paths problem, Journal of Combinatorial Theory, Series B, 1995, 63 (1): 65–110, doi:10.1006/jctb.1995.1006 （英語）.
• Robertson, Neil; Seymour, Paul D., Graph Minors. XVI. Excluding a non-planar graph, Journal of Combinatorial Theory, Series B, 2003, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X （英語）.
• Robertson, Neil; Seymour, Paul D., Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory, Series B, 2004, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001 （英語）.
• Robertson, Neil; Seymour, Paul; Thomas, Robin, Hadwiger's conjecture for K₆-free graphs (PDF), Combinatorica, 1993, 13: 279–361 [2019-04-25], doi:10.1007/BF01202354, （原始內容 (PDF)存檔於2009-04-10） （英語）.
• Thomas, Robin, Recent excluded minor theorems for graphs, Surveys in combinatorics, 1999 (Canterbury) (PDF), London Math. Soc. Lecture Note Ser. 267, Cambridge: Cambridge Univ. Press: 201–222, 1999 [2019-04-25], MR 1725004, （原始內容 (PDF)存檔於2016-08-03） （英語）.
• Thomason, Andrew, An extremal function for contractions of graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 1984, 95 (2): 261–265, Bibcode:1983MPCPS..95..261T, doi:10.1017/S0305004100061521 （英語）.
• Thomason, Andrew, The extremal function for complete minors, Journal of Combinatorial Theory, Series B, 2001, 81 (2): 318–338, doi:10.1006/jctb.2000.2013 （英語）.
• Wagner, Klaus, Über eine Eigenschaft der ebenen Komplexe, Math. Ann., 1937a, 114: 570–590, doi:10.1007/BF01594196 （英語）.
• Wagner, Klaus, Über eine Erweiterung des Satzes von Kuratowski, Deutsche Mathematik, 1937b, 2: 280–285 （英語）.

外部連結

• 埃里克·韋斯坦因. Graph Minor. MathWorld.