图的厚度与厚度问题 图论中， 厚度 （thickness）是衡量一个图在几何或拓扑上“复杂度”的参数，它描述的是将图分解为若干个平面子图的最小数目。具体来说，一个图 \( G \) 的厚度 \( \theta(G) \) 是最小的整数 \( k \)，使得 \( G \) 可以分解为 \( k \) 个平面子图的并集（即每条边恰好属于一个子图）。 1. 厚度定义与直观理解 背景 ：并非所有图都是平面图（例如 \( K_ 5 \) 或 \( K_ {3,3} \) 是非平面的）。厚度问题研究的是：如果一个图不能画在平面上而无交叉，那么至少需要几个平面图“叠放”才能表示它？ 数学定义 ： \[ \theta(G) = \min \{ k \mid G = G_ 1 \cup G_ 2 \cup \dots \cup G_ k, \text{每个 } G_ i \text{ 是平面子图} \}. \] 例子 ： 平面图的厚度为 1（例如树、网格图）。 完全图 \( K_ 5 \) 的厚度为 2（虽然 \( K_ 5 \) 非平面，但可以分解为两个平面子图）。 2. 厚度的性质与基本界限 下界 ：若图 \( G \) 有 \( n \) 个顶点和 \( m \) 条边，则每个平面子图最多有 \( 3(n-2) \) 条边（对 \( n \geq 3 \)），因此： \[ \theta(G) \geq \left\lceil \frac{m}{3n-6} \right\rceil. \] 上界 ：对于任意图，厚度不超过边稠密度的函数，例如 \( \theta(G) \leq \lfloor \frac{n+1}{2} \rfloor \) 对完全图成立。 3. 经典图的厚度计算 完全图 \( K_ n \) ： \[ \theta(K_ n) = \left\lceil \frac{n+7}{6} \right\rceil \quad (\text{除少数特例，如 } n=9, 10). \] 这一公式由 Battle、Harary 等人在 1960 年代证明，需结合平面图的最大边数和图分解的构造。 完全二分图 \( K_ {a,b} \) ： \[ \theta(K_ {a,b}) = \left\lceil \frac{ab}{2(a+b-2)} \right\rceil \quad (\text{当 } a,b \geq 2). \] 4. 厚度与其他图参数的关系 与色数的关系 ：厚度不影响色数，但厚度的存在使得非平面图可能需要更多层平面子图才能着色（例如，厚度为 2 的图可能仍需要 4 种颜色）。 与连通度的关系 ：高连通图可能具有较大的厚度，但厚度本身不直接依赖于顶点连通度。 5. 厚度问题的计算复杂性 判断任意图 \( G \) 是否满足 \( \theta(G) \leq k \) 是 NP-困难的（即使 \( k=2 \)）。 近似算法研究：存在基于最大平面子图提取的启发式算法，但无常数近似比。 6. 应用与扩展 电路设计 ：厚度对应多层电路板布线的最小层数（每层需避免交叉）。 拓扑厚度 ：推广到曲面嵌入（如环面厚度），即分解为可嵌入某曲面的子图的最小数目。 厚度问题本质是图分解与平面性的交叉，它既包含组合构造的巧思，也涉及计算复杂性的挑战。