图 minor

形式陈述 ​

若图 $H$ 可从有限简单无向图 $G$ 经过有限次下列操作得到，就称 $H$ 是 $G$ 的 minor，记作 $H\preccurlyeq G$：

1. 删除顶点及其关联边；
2. 删除边；
3. 收缩边 $uv$，即把 $u,v$ 合并为一个顶点。

收缩可能产生自环或平行边；在简单图约定下，随后删除自环并把平行边合并。这个清理不改变 simple minor 关系。

等价地，$H$ 是 $G$ 的 minor，当且仅当可以为每个 $v\in V(H)$ 选取 $G$ 中一个非空连通顶点集 $B_v$，使这些 branch sets 两两不交，并且每当 $uv\in E(H)$ 时，$G$ 中至少有一条边连接 $B_u$ 与 $B_v$。把每个 $B_v$ 收缩为一点，就得到含 $H$ 的子图，再删除多余边即可。

直觉 ​

普通子图只允许删除，minor 还允许把一段连通区域压缩成一个粗粒度顶点。它忘掉局部路径有多长，却保留哪些连通块能够彼此相邻。因此 minor 适合描述在任意细分和局部拉长下都不变的全局拓扑障碍。

branch-set 刻画把收缩过程静态化：不必记录操作顺序，只需指出原图中哪些互不重叠的连通块扮演目标图顶点。目标图没有要求的额外邻接可以删除，所以 branch sets 之间允许比 $H$ 更多的边。

例子与边界 ​

四边形 $C_4$ 不含三角形子图，但收缩任意一条边后得到 $K_3$，所以 $K_3\preccurlyeq C_4$。这直接说明 minor 不等于子图公理库子图Subgraph顶点集和边集分别取原图子集且保持端点关系所得的图。。一条边被任意多次细分所得的长路径，收缩新增边后又回到原边；minor 因而忽略这种局部长度变化。

平面图的 minor 仍是平面图。Wagner 定理进一步断言，有限图平面当且仅当它没有 $K_5$ 或 $K_{3,3}$ minor。Kuratowski 定理公理库Kuratowski 定理Kuratowski's theorem有限图可平面嵌入，当且仅当不含 K5 或 K3,3 的细分子图。使用的则是 subdivision，也就是 topological minor；两条定理结论相近，但一般 minor 的 branch sets 可以分叉，不能把两种包含关系当作同一个定义。

收缩也不是任意识别两个顶点：只有一条边的两个端点可直接收缩；branch-set 版本相应要求每一块连通。诱导子图又是更严格的概念，因为它连删除保留顶点之间的边都不允许。

推论与应用 ​

若一个图性质在删除与收缩下保持，就称其 minor-closed。平面性、固定曲面可嵌入性以及树宽不超过给定常数都是典型例子；特别地，

$$H\preccurlyeq G⟹\mathrm{tw}(H)\le \mathrm{tw}(G),$$

其中树宽见树分解与树宽公理库树分解与树宽Tree decomposition · Treewidth用按树组织的顶点袋覆盖图，并以最小最大袋大小衡量图偏离树结构的程度。。

Robertson–Seymour 图 minor 定理说明有限图在 minor 关系下良拟序；等价地，每个 minor-closed 图族都由有限个禁用 minor 刻画。该定理的证明远超定义页范围，但它解释了为何“找有限障碍”成为结构图论与识别算法中的统一策略。

参考资料

• Reinhard Diestel, Graph Theory, 5th ed., Springer, 2017, chapters on planar graphs and graph minors.
• Neil Robertson and Paul D. Seymour, “Graph Minors. XX. Wagner's Conjecture,” Journal of Combinatorial Theory, Series B 92 (2004), 325–357.