跳转到内容

图子式

维基百科,自由的百科全书
(重定向自次图

图论中,如果无向图H可以通过图G删除边和顶点或收缩边得到,则称H为G的子式(minor)或次图

图子式的提出源自瓦格纳定理,这个定理表明:当且仅当一个图不存在完全图K5完全二分图K3,3的子式时,这个图才是平面图[1] 罗伯逊-西摩定理英语Robertson–Seymour theorem表明,对于任何在图上删除点或边或收缩边保留的性质,类似的禁子式表征英语forbidden minor characterization(forbidden minor characterization)也存在。[2] 给定图G和图H,可以在多项式时间内判断H是否是G的子式。[3] 连同上述禁子式表征,这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。[4] 其他涉及到图子式的定理和猜想包括图结构定理英语graph structure theoremHadwiger猜想英语Hadwiger conjecture (graph_theory)等。

定义

边收缩(contraction)是在图上移除一条边同时合并这条边的两个邻点。一个无向图H是另一个无向图G的子式,如果G通过一系列的收缩边、删除边、删除孤立点可以得到一个同构H的图。这一系列收缩和删除操作的顺序不影响最后得到的图H

例子

H是G的子式:

H. 图H

G. 图G

以下显示了如何构造子式。首先去除图G中虚线边,再去掉孤立的顶点,最后对灰色边进行边收缩即得到图H。

从图G变为图H

主要结论和猜想

可以很直接地验证,在同构意义上,图子式关系是一个偏序关系:它满足自反性(自己是自己的子式)、反对称性(图GH互为子式仅当它们同构)、传递性(图G的子式的子式也是图G的子式)。尼尔·罗伯逊英语Neil Robertson (mathematician)保罗·西摩英语Paul Seymour (mathematician)提出了一个更深刻的结论:图子式关系实际上是一种良擬序关系:给定一串无穷的图序列G1, G2,...总是存在i < j,使得 GiGj的子式。一个等价的表述是,任意的一簇图的集合必然只有有限个子式意义下的极小元[5]。这个结论验证了先前的一个猜想:瓦格纳猜想。它很早就被克拉斯·瓦格纳英语Klaus Wagner提出,直至1970年才发表。[6]

在他们证明的过程中,西摩和罗伯逊也同时证明了图结构定理英语graph structure theorem。对于一个给定的图H,这个定理刻画了不包含H-子式的图的结构。这个定理的严格表述又长又复杂,但是简而言之,它证明了这样一个图必须具有由嵌在有界亏格曲面上的图以小方式修改而成的图的团和英语Clique-sum结构。因此,他们的理论建立了图子式和图的拓扑嵌入之间的基本联系。[7]

对于任意图H,无H-子式的简单图必须是稀疏的,即图的边数小于等于一个常数倍的图的阶数[8]。更精确地,如果图Hh个点,那么有n个顶点的不包含H-子式的简单图G有至多条边。不包含Kh-子式的图至少有这么多条边。[9]因此,G平均度级别的。更进一步,不包含H-子式的图有一个和平面图分割定理英语planar separator theorem类似的分割定理:给定H和任意不包含H-子式的n阶图G,可以找到G的顶点,使得删除这些点可以将G分成两个(可能不连通的)子图,使得每个子图有至多2n/3个顶点。[10]更强的结论是,对于任意的图H,不包含H-子式的n阶图G树宽数量级的。[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).

参考文献

外部链接