图的厚度与厚度问题 图论中， 厚度 （thickness）是衡量一个图在几何或拓扑上“复杂度”的参数之一，它关注的是 将图的边分解为若干平面子图的最小数目 。具体来说，一个图 \( G \) 的厚度 \( \theta(G) \) 定义为最小的整数 \( k \)，使得 \( G \) 的边集可以被划分为 \( k \) 个子集，每个子集构成的子图都是平面图。 1. 厚度问题的起源与背景 厚度概念源于印刷电路板设计：在电路布线时，需将导线分布在不同的层（每层不允许交叉），厚度即为所需的最少层数。 它与 平面图 （可画在平面上无交叉边的图）密切相关：若 \( \theta(G) = 1 \)，则 \( G \) 本身是平面图。 2. 厚度的定义与基本性质 形式化定义 ： \[ \theta(G) = \min \{ k \mid E(G) = E_ 1 \cup E_ 2 \cup \cdots \cup E_ k, \text{每个 } G[ E_ i ] \text{是平面图} \}. \] 简单性质 ： 若 \( G \) 是平面图，则 \( \theta(G) = 1 \)。 厚度具有单调性：若 \( H \) 是 \( G \) 的子图，则 \( \theta(H) \leq \theta(G) \)。 厚度与边数相关：对 \( n \) 顶点图，若边数 \( m > 3n - 6 \)（平面图的最大边数），则 \( \theta(G) \geq \lceil m / (3n - 6) \rceil \)。 3. 厚度的计算与上界 完全图 \( K_ n \) 的厚度 ： 已知结果：\( \theta(K_ n) \geq \lceil (n+7)/6 \rceil \)，且当 \( n \not\equiv 4, 7 \pmod{6} \) 时等号成立。 例如：\( \theta(K_ 9) = 3 \)，因为 \( K_ 9 \) 的边需分到 3 个平面子图中。 完全二部图 \( K_ {r,s} \) 的厚度 ： 公式：\( \theta(K_ {r,s}) = \lceil rs / (2r + 2s - 4) \rceil \)（当 \( r, s \geq 2 \)）。 4. 厚度与其他图参数的关系 与色数的联系 ：由四色定理，每个平面图是 4-可着色的，因此 \( \chi(G) \leq 4\theta(G) \)。 与亏格的关系 ：若图可嵌入亏格为 \( g \) 的曲面，则 \( \theta(G) \leq g + 1 \)，但反之不成立。 5. 厚度问题的计算复杂性 判定 \( \theta(G) \leq k \) 对任意 \( k \geq 2 \) 是 NP-完全问题（即使 \( G \) 是二部图）。 近似算法研究：存在多项式时间算法可计算厚度的 \( O(\sqrt{n}) \) 近似值。 6. 应用与扩展 VLSI 设计 ：厚度直接对应电路布线的层数优化。 拓扑图论 ：厚度与图的 书厚度 （book thickness）相关，后者要求边划分在“页”上，每页的边不交叉。 开放问题 ：完全确定 \( K_ n \) 在所有 \( n \) 下的厚度（目前仅对部分 \( n \) 解决）。 厚度问题结合了图的结构分解、平面性算法和组合优化，是图论与应用交叉的典型例子。