图的嵌入与厚度问题 步骤1：图嵌入的基本概念回顾与厚度问题的引入 图嵌入是将图映射到某个曲面上的过程，使得边仅在顶点处相交。您已学过平面图（可嵌入到球面或平面的图），但许多图（如完全图K₅或完全二分图K₃,₃）是非平面图。那么，如何衡量一个非平面图“接近”平面图的程度？厚度问题就是其中一种度量方式：它研究的是将一个图的边集划分为尽可能少的子集，使得每个子集构成的子图都是平面图。这个最少数目称为图的厚度，记作θ(G)。例如，厚度为1的图就是平面图。 步骤2：厚度的精确定义与示例 给定图G，其厚度θ(G)是满足以下条件的最小整数k：G的边集可以被划分为k个子集E₁, E₂, ..., Eₖ，使得每个边诱导的子图G[ Eᵢ ]都是平面图。直观上，这相当于用k个平面层（每层是一个平面子图）来“绘制”原图G，且所有层共享相同的顶点集。 示例1 ：树是平面图，因此其厚度θ(T) = 1。 示例2 ：完全图K₅是非平面图，但可以将其边集划分为两个平面子图（例如，一个子图包含一个三角形和两条独立边，另一个子图包含剩余边），因此θ(K₅) = 2。 步骤3：厚度与图参数的关系 厚度与图的其它参数存在理论联系： 顶点数n与边数m ：对任意简单图，每个平面子图最多有3n - 6条边（n ≥ 3时），因此k个平面层最多容纳k(3n - 6)条边。这推出厚度下界：θ(G) ≥ ⌈m / (3n - 6)⌉（当n ≥ 3）。 平均度 ：结合上述关系，可推导出θ(G) ≥ ⌈(m/n) / 6⌉ ≈ ⌈d_ avg / 6⌉，其中d_ avg为平均度。 色数 ：厚度与色数χ(G)无关（存在高厚度但低色数的图，反之亦然），但厚度影响图的物理实现复杂度。 步骤4：特定图类的厚度计算 完全图Kₙ的厚度是经典问题。已知公式：θ(Kₙ) ≥ ⌈(n + 7)/6⌉，且当n ≡ 1, 2 (mod 6)时等号成立。例如： θ(K₈) = 2（因8 ≡ 2 mod 6，计算得⌈(8+7)/6⌉ = ⌈15/6⌉ = 3? 需修正：实际θ(K₈)=2，公式在n≠1,2 mod 6时为下界）。 完全二分图K_ {a,b}的厚度也有研究，例如θ(K_ {4,4}) = 2。 步骤5：厚度问题的计算复杂性与应用 NP-困难性 ：确定任意图的厚度是NP-困难的，因此研究多集中于近似算法或特定图类的精确值。 应用场景 ： VLSI设计 ：将电路布线分解为多个平面层以减少交叉。 网络可视化 ：用多层平面布局展示复杂网络，提升可读性。 生物信息学 ：分析蛋白质相互作用网络的结构层次。 步骤6：厚度与相关概念的对比 厚度常与以下概念区分： 亏格 ：将图嵌入到可定向曲面的最小 genus（如球面genus=0，环面genus=1）。厚度关注的是层数，而亏格关注曲面拓扑复杂度。 交叉数 ：允许边交叉时所需的最少交叉次数，厚度则要求每层完全无交叉。 算术厚度 ：允许边在绘制时弯曲，厚度通常假设边是直线段（几何厚度）。