图的收缩核与图子式定理 我们先从基础概念开始。图H是图G的收缩核（或称G可收缩到H），是指可以通过对G的边进行一系列 边收缩 运算得到H。边收缩是指将一条边e的两个端点u和v合并成一个新的顶点w，并且w与所有原本与u或v相邻的顶点相连。这个过程可能会产生重边，在简单图的讨论中，我们通常会在收缩后删除可能产生的重边和自环。 例如，如果一个图G包含一个三角形（3个顶点两两相连），那么通过连续收缩两条边，G可以收缩到一个单个顶点（K1），因为三角形可以逐步收缩成一条边，再收缩成一个点。 接下来是核心概念： 图子式 。图H是图G的一个子式，如果H是G的某个子图的收缩核。这意味着，要得到H，我们可以分两步走： 首先，从G中删除一些顶点和边，得到一个子图G'。 然后，对G'进行一系列的边收缩操作，最终得到图H。 子式关系是图论中一个极其重要的偏序关系，它比“子图”关系更一般。例如，任何图都是其自身的子式。一个著名的例子是，库拉托夫斯基定理指出，一个图是平面图当且仅当它不包含K5（5个顶点的完全图）或K3,3（完全二分图）作为子式。这里的“不包含”精确来说就是“不包含作为子式”。 基于子式概念，一个非常重要的定理是 图子式定理 ，也称为罗伯逊-西摩定理。这个定理是图论领域的一个里程碑式成果，其内容非常深刻。我们可以分层次理解： 首先，定理指出，在子式关系下， 任何无限图序列中，总有一个图是另一个图的子式 。这个性质被称为子式关系的 良拟序性 。这意味着，你无法构造一个无限的图序列，使得序列中的任何一个图都不是序列中另一个图的子式。 其次，由这个良拟序性质可以直接导出一个惊人的推论： 对于任何给定的图族F（例如，所有不能画在曲面S上的图的集合），如果F在取子式下是封闭的（即如果G在F中，那么G的任何子式也在F中），那么F可以由一个有限的禁用子式列表来刻画 。换句话说，存在一个有限的图集合 {H1, H2, ..., Hk}，使得一个图G属于族F，当且仅当G不包含H1, H2, ..., Hk中的任何一个作为子式。 平面图的刻画就是此定理的一个特例：平面图族（在取子式下封闭）的有限禁用子式列表就是{K5, K3,3}。图子式定理将这个结论推广到了任意曲面（例如环面）甚至更一般的图族上。 最后，图子式定理还包含一个算法结论： 对于任何固定的图H，存在一个多项式时间算法来判断一个输入图G是否包含H作为子式 。这个算法的复杂度是O(n^3)，但常数项巨大地依赖于H的大小，因此该算法主要是理论上的意义，表明问题是固定参数可处理的。