图的厚度问题 让我们从基础概念开始。图的厚度（thickness）是衡量一个图"接近平面图程度"的拓扑参数，它表示将一个图分解为若干个平面子图所需的最少数量。 1. 厚度问题的起源与定义 厚度问题的研究源于实际应用，比如在印刷电路板设计中，需要将复杂的电路连线分布在不同层上，每层要求连线不交叉（即对应平面图）。图的厚度θ(G)定义为最小的正整数k，使得图G可以分解为k个平面子图的并集。 数学定义：如果存在平面子图G₁, G₂, ..., Gₖ，使得E(G) = E(G₁) ∪ E(G₂) ∪ ... ∪ E(Gₖ)，且这些子图的边集两两不相交，则称θ(G) ≤ k。 2. 厚度与平面图的关系 平面图是厚度为1的特殊情况。如果一个图不是平面图，那么它的厚度至少为2。例如，完全图K₅的厚度为2，因为它可以分解为两个平面子图：一个四边形加一条对角线，以及一个三角形加两条射线。 厚度与图的密度密切相关：边数越多、连接越复杂的图，通常需要更多的平面层来避免交叉。 3. 厚度的基本性质 厚度具有几个重要性质： 单调性：如果H是G的子图，则θ(H) ≤ θ(G) 可加性：对于任意两个图G和H，有θ(G∪H) ≤ θ(G) + θ(H) 下界性质：θ(G) ≥ ⌈|E(G)|/(3|V(G)|-6)⌉（利用平面图的最大边数公式） 4. 特殊图的厚度计算 对于某些特定类型的图，厚度有精确公式： 完全图Kₙ的厚度：θ(Kₙ) = ⌊(n+7)/6⌋（当n≠9,10时） 完全二部图Kₘ,ₙ的厚度：当m,n均为偶数时，θ(Kₘ,ₙ) = ⌈mn/(2m+2n-4)⌉ 这些公式的证明通常需要构造性的分解方法和组合优化技术。 5. 厚度与图参数的关系 厚度与其他图参数存在密切联系： 与色数的关系：χ(G) ≤ 6θ(G)（因为每个平面图都是6-可着色的） 与亏格的关系：θ(G) ≤ γ(G) + 1（其中γ(G)是图的亏格） 与平均度的关系：θ(G) ≥ ⌈(平均度)/5.999...⌉ 6. 计算复杂性与算法 确定一个图的厚度是NP-难问题。即使对于厚度为2的情况，判定一个图是否具有厚度2也是NP-完全的。这导致研究者主要关注： 近似算法：开发多项式时间的厚度近似算法 特殊图类：研究树宽有界图、平面图等特殊图类的厚度计算 上下界估计：通过图参数给出厚度的上界和下界估计 7. 厚度问题的推广 厚度概念有几个重要推广： 外厚度：要求每个平面子图都是外平面图 几何厚度：要求每个平面子图在分解时保持几何位置关系 线性厚度：与图的线性荫度相关的概念 这些推广在VLSI设计、生物信息学等领域有具体应用。 厚度问题作为图论与拓扑的交叉研究领域，既包含深刻的数学理论，又在实际应用中发挥着重要作用，是图嵌入理论中的重要研究方向。