图子式

在图论中，如果无向图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有至多 $\scriptstyle O(nh{\sqrt {\log h}})$ 条边。不包含K_h-子式的图至少有这么多条边。^[9]因此，G的平均度是 $\scriptstyle O(h{\sqrt {\log h}})$ 级别的。更进一步，不包含H-子式的图有一个和平面图分割定理（英语：planar separator theorem）类似的分割定理：给定H和任意不包含H-子式的n阶图G，可以找到 $\scriptstyle O({\sqrt {n}})$ 个G的顶点，使得删除这些点可以将G分成两个（可能不连通的）子图，使得每个子图有至多2n/3个顶点。^[10]更强的结论是，对于任意的图H，不包含H-子式的n阶图G的树宽是 $\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]

参见

注释

^ Lovász (2006), p. 77; Wagner (1937a).
^ Lovász (2006), theorem 4, p. 78; Robertson & Seymour (2004).
^ Robertson & Seymour (1995).
^ Fellows & Langston (1988).
^ Diestel (2005), Chapter 12: Minors, Trees, and WQO; Robertson & Seymour (2004).
^ Lovász (2006), p. 76.
^ Lovász (2006), pp. 80–82; Robertson & Seymour (2003).
^ Mader (1967).
^ Kostochka (1982); Kostochka (1984); Thomason (1984); Thomason (2001).
^ Alon, Seymour & Thomas (1990); Plotkin, Rao & Smith (1994); Reed & Wood (2009).
^ Grohe (2003)
^ Hadwiger (1943)
^ Robertson, Seymour & Thomas (1993).
^ 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.

[w-1] Lovász (2006), p. 77; Wagner (1937a).

[rst-2] Lovász (2006), theorem 4, p. 78; Robertson & Seymour (2004).

[rs95-3] Robertson & Seymour (1995).

[fl88-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).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]