图的收缩核与图子式定理 接下来，我将从基本定义出发，逐步介绍图的收缩核与子式定理，包括其数学背景、核心性质及应用。 1. 基本定义：图的子式（Graph Minor） 子式的构成 ：若图 \( H \) 是图 \( G \) 的子式，记作 \( H \preceq G \)，则可通过以下三种操作从 \( G \) 得到 \( H \)： 删除边 ：移除某条边（不删除顶点）。 删除顶点 ：移除某个顶点及其关联边。 边收缩 ：将一条边 \( e = (u, v) \) 合并为一个新顶点 \( w \)，使 \( w \) 连接 \( u \) 和 \( v \) 的所有邻接点（避免重边时合并）。 示例 ：任意树是任意包含该树的图的子式（通过收缩非树边）。 2. 收缩核（Contraction-Critical Graph） 背景 ：在染色理论中，若图 \( G \) 的任意真子式（通过边收缩得到）的色数均小于 \( G \) 的色数，则称 \( G \) 为 收缩核 。 性质 ： 收缩核是“染色意义下不可约”的图，即无法通过收缩边降低色数。 例如：完全图 \( K_ n \) 是收缩核，因为收缩任意边会减少色数。 3. 子式定理（Graph Minor Theorem） 瓦格纳定理（Wagner’s Theorem） ： 图 \( G \) 是平面图当且仅当它不包含 \( K_ 5 \) 或 \( K_ {3,3} \) 作为子式。 此定理揭示了平面图的子式刻画。 罗伯逊-西摩定理（Robertson–Seymour Theorem） ： 子式偏序的良拟序性 ： 任意无限图序列中，必存在一个图是另一个图的子式。 禁止子式刻画 ： 每个图族封闭 under 子式操作时，可由有限个禁止子式刻画。 算法意义 ： 对任意固定图 \( H \)，存在 \( O(|G|^3) \) 算法判断 \( H \) 是否为 \( G \) 的子式。 4. 应用与推广 结构图论 ： 子式定理证明了图可被树分解控制，且具有复杂结构的图必包含大平面子式。 哈德维格尔猜想（Hadwiger’s Conjecture） ： 若图 \( G \) 的色数为 \( k \)，则 \( K_ k \) 是 \( G \) 的子式（已证对于 \( k \leq 6 \)）。 算法设计 ： 子式封闭的性质可用于设计固定参数可解算法，例如求解平面图上的 NP 难问题。 5. 总结 子式理论通过收缩和删除操作，将图的拓扑结构与代数性质联系起来，成为现代图论的核心工具之一。从瓦格纳定理到罗伯逊-西蒙定理，子式研究逐步揭示了图的深层分类规律。