minor · 树宽 · Robertson–Seymour

图子式理论：树宽与图子式定理

minor（子式） 关系——在子图谱系里见过——是「删点、删边、收缩连通块」三种操作的闭包，是图论里最深刻的偏序之一。本页沿这条线讲两件事：其一，如何用 tree decomposition（树分解） 度量一张图「离树有多远」，得到 treewidth（树宽）；其二，Robertson 与 Seymour 的 图子式定理——minor 关系是良拟序，于是任何对 minor 封闭的图类都只需有限条禁用子式即可刻画。

minor 回顾： H 是 G 的 minor，当且仅当从 G 出发，经删去顶点、删去边、收缩边 (contract) 三类操作可得到 H。收缩一条边即把它两端的顶点捏成一个，继承两者的全部外部邻居（重边去重、自环删除）。等价地：存在一族两两不交的连通顶点块 branch set，每块收缩成 H 的一个顶点，且 H 的每条边在 G 里都有对应连边。三种操作的逐步演示见子图谱系。

tree decomposition（树分解）： 一棵树 T，每个树节点挂一个原图顶点子集，称 bag，须同时满足三条：其一覆盖——每个原图顶点至少落在某个 bag 里；其二 边覆盖——每条原图边的两个端点共处于某一个 bag；其三 连通性 (running intersection)——对每个原图顶点 v，所有含 v 的 bag 在树 T 上构成一棵连通子树。treewidth = 在所有合法树分解中取 $（最大 bag 大小 - 1）$ ，再对所有分解求最小值。减 1 是约定，使树的树宽恰为 1。

几张图的树宽：

树 / 森林：treewidth = 1。把每条边 {u,v} 做成一个 bag，按原树的边相邻关系连成 bag 树即可，最大 bag 大小 2。
圈 Cₙ (n ≥ 3):treewidth = 2。沿圈把相邻顶点三三打包，最大 bag 大小 3；它不是树（含圈），故树宽必 > 1。
完全图 Kₙ：treewidth = n − 1。K_n 任两点相邻，任何树分解都必有一个 bag 含全部 n 个顶点，故下界 n−1；单个 bag 装下全部顶点即达此值。

minor 关系是良拟序 (well-quasi-ordering): 一个偏序是 wqo，意味着它既无无穷反链（两两不可比的无穷集），也无无穷下降链。Robertson 与 Seymour 历经二十余篇论文（Graph Minors 系列）证明：有限图在 minor 关系下构成 wqo。这是图子式定理的核心引擎。

图子式定理 (Robertson–Seymour)

每个对 minor 封闭的图类 𝓕（即 $G \in 𝓕$ 且 H 是 G 的 minor ⇒ $H \in 𝓕$ ），都存在一个有限的禁用子式集 {H₁， …， H_k}，使得 $G \in 𝓕 ⟺ G$ 不含任何 H_i 作为 minor。平面图是其著名特例：由 Wagner 定理，一张图可平面 ⟺ 它既不含 $K_5$ 也不含 $K_{3,3}$ 作为 minor（Kuratowski 的等价版本用拓扑子式即细分）。

树宽小为何有用： 许多在一般图上 NP-难的问题（independent set、vertex cover、dominating set、图着色…），一旦限制在树宽有界的图上，就能沿树分解自底向上做动态规划：每个 bag 至多 w + 1 个顶点，其上的局部状态数被 bag 大小封顶，于是总复杂度对顶点数线性 / 多项式、仅在树宽 w 上呈指数。更进一步，Courcelle 定理：任何可用 monadic second-order logic 表达的图性质，在树宽有界的图上都可线性时间判定。