图子式 📖 Wikipedia

边收缩（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).

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