图嵌入与匹配书嵌入：F-sum运算与分散性分析
1. 图嵌入与匹配书嵌入基础概念解析
在计算机科学和离散数学领域，图嵌入问题一直备受关注。书嵌入(book embedding)作为一种特殊的图嵌入方式，最早由Bernhart和Kainen在1979年提出。这种嵌入方法将图的顶点排列在三维空间的一条直线（称为书脊）上，并将每条边分配到以书脊为边界的半平面（称为页面）中，要求同一页面内的边不能交叉。
匹配书嵌入(matching book embedding)是书嵌入的一种强化形式，它在书嵌入的基础上增加了一个关键约束：每个顶点在每个页面上的度数不超过1。这意味着在每个单独的页面上，与任何顶点相连的边最多只能有一条。满足这一条件的书嵌入称为匹配书嵌入，而实现这种嵌入所需的最少页面数称为图的匹配书厚度(matching book thickness)，记作mbt(G)。
从图论角度看，匹配书嵌入与图的边着色问题密切相关。一个图G被称为分散的(dispersable)，当且仅当其匹配书厚度等于图的最大度Δ(G)；若匹配书厚度等于Δ(G)+1，则称该图是近似分散的(nearly dispersable)。这些概念不仅具有理论价值，在VLSI设计、网络路由等实际应用中也具有重要意义。
2. F-sum图运算的构造与性质
2.1 四种基本图变换操作
F-sum运算建立在四种基本图变换操作之上，这些操作可以显著改变原图的结构特性：
S操作：在图的每条边上插入一个新顶点，相当于将每条边替换为长度为2的路径。对于任意图G，S(G)的最大度Δ(S(G))保持与原图相同，即Δ(S(G))=Δ(G)，且至少存在一个黑色顶点（原图顶点）达到最大度。
R操作：为原图的每条边添加一个新顶点，并将该顶点与原边的两个端点相连。这种操作使最大度翻倍，Δ(R(G))=2Δ(G)，同样存在黑色顶点达到最大度。
Q操作：在每条边上插入新顶点后，还将相邻边上的新顶点相连。这种操作产生的图Q(G)最大度至少为Δ(G)+1，且所有达到最大度的顶点都是白色（新增顶点）。
T操作：将原图的顶点和边都作为新顶点，保留原图中的邻接和关联关系。T操作也使最大度翻倍，Δ(T(G))=2Δ(G)，且存在黑色顶点达到最大度。
2.2 F-sum运算的正式定义
给定两个图G₁和G₂，以及操作F∈{S,R,Q,T}，F-sum运算G₁+ᴅG₂定义为F(G₁)□G₂-E*，其中□表示图的笛卡尔积，E*是特定条件下需要移除的边集。直观上，G₁+ᴅG₂包含|V(G₂)|个F(G₁)的副本，每个副本对应G₂的一个顶点。这些副本中的顶点分为两类：黑色顶点（对应原图G₁的顶点）和白色顶点（对应G₁的边）。
在F-sum图中，两个顶点(u₁,u₂)和(v₁,v₂)相邻当且仅当满足以下条件之一：
- u₁=v₁∈V(G₁)且u₂v₂∈E(G₂)
- u₂=v₂∈V(G₂)且u₁v₁∈E(F(G₁))
这种构造方式使得F-sum运算能够生成丰富的图类，为研究匹配书嵌入性质提供了广阔的空间。
3. 外平面图的分散性证明
3.1 外平面图的基本性质
外平面图(outerplanar graph)是指所有顶点都可以画在平面上一个圆周上，且所有边都可以画在圆内而不交叉的图。这类图在图的嵌入理论中具有特殊地位，因为它们的结构相对简单，但又能体现许多重要性质。
根据已有研究，外平面图的边色数χ'(G)（对图进行正常边着色所需的最少颜色数）与其最大度Δ(G)有以下关系：
- 除非G是奇圈，否则外平面图都属于第1类图，即χ'(G)=Δ(G)
这一性质为证明外平面图的分散性奠定了基础。
3.2 分散性证明的核心思路
定理3.1：如果G是一个不是奇圈的外平面图，那么G是分散的。
证明分为两种情况考虑：
Δ(G)≤2的情况：此时G只能是路径或圈。由于排除了奇圈，剩下的只有偶圈和路径。这些图显然满足mbt(G)=Δ(G)，因此是分散的。
Δ(G)≥3的情况：利用外平面图的性质，可以将所有顶点排列在一个"印刷圆周"(printing cycle)上，所有边作为该圆周的弦且不相交。根据引理2.3，此时χ'(G)=Δ(G)，意味着可以使用Δ(G)种颜色对边进行正常着色。通过将每种颜色对应的边分配到一个单独的页面，就可以构造出所需的匹配书嵌入，证明mbt(G)=Δ(G)。
这一证明不仅确立了外平面图的分散性，还为后续研究F-sum运算的匹配书厚度提供了重要工具。特别是对于路径、圈和星图等特殊图类，它们的F-sum变换结果往往保持或继承了外平面性，这使得相关结论可以直接应用。
4. F-sum运算的匹配书厚度上界
4.1 主要定理及其证明
定理3.2：对于F∈{S,Q,R,T}，设G是任意简单图，H是任意分散二分图，则mbt(G+ᴅH)≤mbt(F(G))+Δ(H)，其中Δ(H)是H的最大度。
证明的核心思想是构造性地利用H的分散性和二分性来构建G+ᴅH的匹配书嵌入：
利用H的分散性：由于H是分散二分图，它存在一个Δ(H)-边着色，对应Δ(H)页的匹配书嵌入。同时，作为二分图，H的顶点可以进行红蓝二着色。
顶点排列策略：对于H中的每个红色顶点，在书脊上放置F(G)的一个标准匹配书嵌入；对于蓝色顶点，则放置其逆序排列。这种对称排列利用了二分图的特性。
边分配方案：将G+ᴅH的边分为两类处理：
- 来自F(G)副本内部的边：分配到mbt(F(G))个页面
- 连接不同F(G)副本的边（对应H的边）：利用H的边着色分配到Δ(H)个页面
由于H是二分图，连接不同颜色顶点的边可以在同一页面内无交叉地排列。最终总页面数不超过mbt(F(G))+Δ(H)。
4.2 特例分析与边界紧致性
对于不同的F操作，这个上界的紧致性表现不同：
F∈{S,R,T}的情况：当F(G)本身是分散的时，G+ᴅH也是分散的。例如，对于路径P₃和偶圈C₄，有mbt(P₃+ᴅC₄)=mbt(F(P₃))+Δ(C₄)，证明上界可以达到。
F=Q的特殊情况：由于Q操作产生的白色高度顶点，使得Δ(G+QH)=max{Δ(Q(G)),Δ(G)+Δ(H)}，通常严格小于mbt(Q(G))+Δ(H)。然而对于星图Sₙ和路径Pₙ等特殊图类，仍能证明mbt(Sₙ+QH)=Δ(Sₙ)+Δ(H)，表明在某些情况下界仍然紧致。
定理3.3：对于星图Sₙ和任意分散二分图H，Sₙ+QH是分散的，即mbt(Sₙ+QH)=Δ(Sₙ)+Δ(H)=n+Δ(H)。
定理3.4：对于路径Pₙ和任意分散二分图H，Pₙ+QH也是分散的，满足mbt(Pₙ+QH)=Δ(Pₙ)+Δ(H)。
这些特例不仅验证了主要定理的正确性，也展示了F-sum运算在不同图类上表现出的丰富性质。
5. 循环图的Q-sum与近似分散性
5.1 循环图Q-sum的特殊性质
当考虑两个循环图的Q-sum时，即Cₚ+QC_q（q为偶数），我们遇到了一个有趣的现象。根据Q操作的性质：
- Q(Cₚ)中所有白色顶点度为4，黑色顶点度为2
- Cₚ+QC_q是一个4-正则图（所有顶点度数为4）
- 当p为奇数时，Cₚ+QC_q包含奇圈，因此不可能是二分图
根据引理2.2，正则图要成为分散图必须首先是二分图，因此Cₚ+QC_q（p为奇数）不可能是分散的。那么它是否可能是近似分散的呢？
5.2 近似分散性证明
定理3.5：对于q为偶数的Cₚ+QC_q，它是近似分散的，即mbt(Cₚ+QC_q)=5=Δ(Cₚ+QC_q)+1。
证明的关键在于构造一个5页的匹配书嵌入：
顶点排列：将Q(Cₚ)的黑色顶点顺时针标记为v₁,...,vₚ，白色顶点逆时针标记为vₚ₊₁,...,v₂ₚ。对于C_q的每个红色顶点uᵢ，按顺序排列(v₁,uᵢ),...,(vₚ,uᵢ)；蓝色顶点uⱼ则按逆序排列。
边分配策略：
- 页面1-2：处理Q(Cₚ)副本内部的特定边对
- 页面3-5：处理剩余的副本内部边以及连接不同副本的边（对应C_q的边）
这种精细的分配方案确保了所有边都能在5个页面内无交叉地排列，同时满足匹配书嵌入的度数约束。当q为奇数时，情况更为复杂，这引出了本文最后的开放问题。
6. 未解决问题与未来方向
尽管本文取得了多项重要成果，但仍有一些开放问题值得进一步探索：
奇数q的循环图Q-sum：对于Cₚ+QC_q（q为奇数），是否也是近似分散的？目前的证明技术难以直接推广到这种情况。
Q-sum的紧上界：定理3.2给出的上界对于Q-sum是否总是紧的？或者说，是否存在图G和H使得mbt(G+QH)=mbt(Q(G))+Δ(H)？目前仅在星图和路径等特殊情况下验证了较弱的等式。
这些问题的解决将进一步完善我们对F-sum运算匹配书厚度的理解，并可能发展出新的图嵌入技术。从应用角度看，这类研究有助于优化网络布局、集成电路设计等实际问题的解决方案。