图的收缩核与子式理论 图的收缩核与子式理论是结构图论中的核心概念，它通过定义一系列图变换操作（主要是边收缩）来研究图的整体性质。这一理论不仅为图的分类提供了强大工具，还与图的可平面性、树宽等参数密切相关。 边收缩的基本操作 给定图 \( G \) 和其一条边 \( e = uv \)，边收缩操作是指将边 \( e \) 的两个端点 \( u \) 和 \( v \) 合并为一个新顶点 \( w \)，并将原先与 \( u \) 或 \( v \) 相连的所有边改为与 \( w \) 相连（注意消除可能产生的自环）。 例如，若 \( G \) 是一个三角形（3个顶点两两相连），收缩任意一条边后，会得到一个包含两个顶点和两条边的图（即多重边）。 子式的定义 如果图 \( H \) 可以通过对图 \( G \) 进行一系列边删除、顶点删除或边收缩操作得到，则称 \( H \) 是 \( G \) 的一个子式。 这三种操作允许任意顺序组合，且每条操作都会简化原图。例如，若 \( G \) 是一个正方形（4个顶点构成的环），通过删除一条边得到一个路径图，再收缩路径中的一条边，可能得到一个三角形。 子式关系的性质 子式关系是传递的：如果 \( H \) 是 \( G \) 的子式，且 \( K \) 是 \( H \) 的子式，则 \( K \) 也是 \( G \) 的子式。 子式关系是自反的：任何图都是其自身的子式。 子式关系不满足对称性：例如，三角形是正方形的子式，但正方形不是三角形的子式。 子式闭族 如果一个图族 \( \mathcal{F} \) 满足“若 \( G \in \mathcal{F} \)，则 \( G \) 的任意子式也属于 \( \mathcal{F} \)”，则称 \( \mathcal{F} \) 是子式闭的。 典型例子包括：平面图族（任何平面图的子式仍是平面图）、可嵌入某固定曲面的图族、树宽不超过某固定值的图族。 子式定理的经典案例 库拉托夫斯基定理 ：一个图是平面图当且仅当它不包含 \( K_ 5 \)（完全5个顶点的图）或 \( K_ {3,3} \)（完全二分图，两部分各有3个顶点）作为子式。 瓦格纳定理 ：进一步明确了平面图的判定条件，直接使用子式语言表述。 子式与图参数的关系 许多图参数在子式操作下是单调的。例如，如果 \( H \) 是 \( G \) 的子式，则树宽满足 \( \text{tw}(H) \leq \text{tw}(G) \)。 这种单调性使得子式理论成为研究图的结构限制性质的有力工具，例如在证明某些图族具有有界树宽时。 罗伯逊-西摩定理 这是子式理论的巅峰成果：在任何无限图序列中，必存在一个图是另一个图的子式。换言之，子式关系构成一个良拟序。 该定理意味着，任何子式闭的图族均可以由有限多个禁止子式来刻画。 算法应用 基于子式理论，对于任何子式闭的图族，存在一个固定参数可解算法来测试图是否属于该族。 例如，对于平面图测试，可以通过检查是否包含 \( K_ 5 \) 或 \( K_ {3,3} \) 子式来实现，尽管直接使用库拉托夫斯基条件的算法效率不高，但更高效的线性时间算法（如基于深度优先搜索的平面性测试）也源于此理论的思想。 通过理解图的收缩核与子式理论，您可以看到图的结构如何通过一系列简化操作被分解和分类，这为处理复杂的图论问题提供了统一的框架。