九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

完全图厚度(thickness)精确值

《图论中的 50 个公开问题》 · 问题 35 专题综述

题面把 Kn 分解成最少几层平面子图?θ(Kn) 的确切公式是什么?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

图 G 的厚度 θ(G):把边集分拆成最少几份,使每份是平面图。Kn 的厚度:边数 C(n,2) 与 «平面图 ≤ 3v−6» 的下界给出 θ ≥ ⌈C(n,2)/(3n−6)⌉ = ⌈(n+7)/6⌉ 型(精确的整除细节逐类变);上界 ⌈(n+2)/6⌉ 型构造。多数 n mod 6 剩余类已锁定,少数类(n ≡ 某两三个值)仍开。

主要概念

计数下界与构造上界的 «六分之一» 结构

下界:3n−6 是平面图边数上限(欧拉公式),故 «层 ≥ 边数比»。上界构造的范式: «循环层»——顶点按 Zₙ 排列,第 j 层取 «距离类» 边(长度模 n 分桶),使每桶 «几乎平面»( «环形边» 的平面化)。 «每层 3n−6 条边» 的 «满载» 与 «桶的整除» 交互给出 mod 6 结构。

书厚度与双面变体

«书厚度»(页数):顶点在书脊、每页要求 «无交叉的单折» ——book(Kn) = ⌈n/2⌉(已证,Bernhart–Kainen)。厚度与书厚度的 «不完全平行»(厚度弱、书厚度强)源于 «交叉约束» 的强度差。

主要命题与证明

命题 1(Beineke–Harary 下界,完整推导) θ(Kn) ≥ ⌈(n+7)/6⌉ − (除数修正)。

证明 k 层平面图总边数 ≤ k(3n−6);需 ≥ C(n,2) = n(n−1)/2,故 k ≥ n(n−1)/(2(3n−6)) = (n²−n)/(6n−12)。做多项式除法:= (n+7)/6 − 7/(2(3n−12))·2 = (n+7)/6 − (校准项)。上取整后逐 mod 6 类化简。□

命题 2(Vasudevan 上界构造骨架) «距离桶» 构造:层 j 取 «长度 ∈ [6j−5, 6j] 的环边» —— «短环边» 的 «弦图» 是平面的( «圆内接 + 距离 ≤ 6 的边可无交叉安排» 的显式排布);桶覆盖所有长度 ⟹ 总层数 ⌈(n+2)/6⌉ 型。

进展与文献

Beineke–Harary 1965( «The thickness of the complete graph»);Vasudevan 与后续构造系;Aleksandrov–Dunfield 等的 «厚度的计算复杂度»(θ 的判定 NP-难);Mutzel–Weisbacher 的 «图厚度算法» 综述。开放核心:剩余 mod 6 类的 «计数–构造» 缺口(下上界差恰 1 的 «临界类»); «厚度 = 3 的图» 的结构刻画等低值情形;与 «拓扑厚度»(边允许画成弧的变体,更弱故更紧)的关系线。

← 返回问题 35