辐边总和公式及其在二维平面图着色中的应用

朱明君

辐边总和公式及其在二维平面图着色中的应用
作者：朱火华
日期：2025年12月6日
1. 引言
二维平面图的着色问题是图论中的经典难题。四色定理表明，任何平面图都能够使用四种颜色进行着色。本文提出了辐边总和公式，通过将任意二维平面图（原图）简化为单中心轮图（新图），使着色过程变得规范且简便。新图与原图在结构和功能上的等价性，确保了着色结果具有可映射性，为平面图着色提供了系统化的方法。辐边总和数等于新单中心轮图的辐边数，也等于环上节点数与新图环边数的总和。
2. 辐边总和公式与图结构转换
2.1 辐边总和公式（三维代数构造范式）
辐边总和公式适用于具有由外向内两层及以上环加中心区域结构的标准二维平面图，也适用于中心区域为任意结构的平面图，其中中心区域节点数≥0。计算时，每轮构型的辐边独立计算后再相加。
在二维平面图中，除了外围节点，围内的每个节点都是轮构型中心，点边可以共享，轮构型间部分或全部点边会叠加。（也就是说，所有二维平面图都是由轮构型模块叠加而成）该公式的目的是将其转化为单中心轮图，以简化着色（单中心轮图仅需4色，与原图结构功能等价）。
辐边总和公式作为纯代数公式，不受二维平面图定义的限制，与传统图论中的欧拉公式属于不同体系，其定义如下：
基础公式：w = 6(n - m - 1) + (m - d)
其中，n为节点总数（n ≥ 4），m为外围节点数（m ≥ 2），d为第二层环节点数（d ≥ 2），w为辐边数（w ≥ 6）。系数6源自最小解情况：当n = 4，m = d = 2时，w = 6，该最小解由两个1 + 3轮构型模块部分点边叠加而成，公式中的“减1”是为了减去围内的一个基准值，且所有顶点度数均≥1。注：特殊情形下：
若m = d ，且m + d为≥ 4的偶数。
若m = d，则w = 6(n - m - 1) = 6(n - (m + 1))；
若m = d = 3，则w = 6(n - 4)。
2.2 普适公式与虚拟环构建
对于标准和非标准二维平面图，都可以通过添加双层虚拟环（总节点数6，每层含3个节点）来覆盖所有平面图类型，简化计算过程。由此得出普适公式：
w = 6(n新 - 4)
其中，n原为二维平面图（原始图）的节点个数（n原≥ 0）；6为两层虚拟环的节点个数，n新 = n原 + 6为添加虚拟环后新图的节点总数。双层虚拟环的作用是包裹原图，有效处理孔洞、亏格曲面、多面体等屏蔽结构。添加虚拟环后的新图是实际存在的图，原图作为其子结构包含在新图中；去掉双层虚拟环后，原图可以继承新图的着色结果，且其色数≤4。
注：普适公式将自动按照标准处理双层虚环的连接边，以及内层环与原图的连接边问题，涵盖包括原图中各构型之间不连通时添加虚拟连接边的情况。无论采用何种连接方式，w值均保持恒定。

2.3 重构公式（等价生成）
⊙ = 1 + w
由计算所得的辐边总和数w ，直接确定最终等价的单中心标准轮图的规模⊙。其中1代表由原图所有围内节点（所有轮构型模块的中心节点）通过几何叠加生成的唯一中心等效体；w为该轮图环上的节点数（即辐边数）。
2.4 原图与新图的结构转换
2.4.1 原图分解至新图的转换步骤
1. 将原图分解，若原图围内有N个节点就能分解出N个变形轮构型，并记录其几何形状；
2. 通过边与辐边的“皮筋伸缩”操作，将变形轮构型还原为标准轮构型；
3. 选取各标准轮构型环上一节点的一侧与边的连接处断开，经边与辐边伸缩形成扇形，使中心节点呈点片状，扇形两端分别为节点端与边端；
（注：节点端的端为凹卯眼，边端的端为凸榫头，中心节点为扇柄中扇钉或点片，辐边为扇骨，环边为扇纸）。
4. 将所有扇形拼接为单中心轮图：扇形一侧节点端与另一扇形一侧边端连接，所有扇形扇柄以点片叠加。
2.4. 2 新图还原至原图的转换步骤
1. 从新图环上标记节点拆解出 n 个扇形；
2. 将各个扇形的两端相连，还原成标准轮构型；
3. 依照原图的变形状态，通过部分或全部点边叠加，恢复原图结构，确保新图与原图结构等价。
3 新单中心轮图的最优着色问题
新单中心轮图的着色规则由环上节点数 n 的奇偶性决定：
当 n = 2m + 1（奇环）时：环上节点采用 2 种颜色交替着色 m 次，剩余 1 个节点使用第 3 种颜色，中心节点使用第 4 种颜色，总颜色数为 4；
当 n = 2m（偶环）时：环上节点采用 2 种颜色交替着色 m 次，中心节点使用第 3 种颜色，总颜色数为 3。
关键约束：若原图中存在任一奇轮构型模块，那么新图即便为偶环也必须采用 4 色方案，这是保证着色结果能无冲突映射回原图的核心条件。
注：新单中心轮图是由轮构型扇化模块组装而成，与传统单中心轮图是两个不同的概念。
4 原图与新图的功能等价性
4.1 原图到新图的功能保持
原图分解为 n 个轮构型后，若各中心节点颜色存在差异，选取占比最多的颜色作为新图中心颜色，其余轮构型通过环上对应节点颜色与中心节点颜色互换，使所有中心节点颜色统一，确保新图与原图功能等价。
4.2 新图到原图的颜色一致性映射
新图分解为 n 个轮构型时，若中心节点颜色与原图中心颜色冲突，通过新图中心节点颜色与环上节点颜色互换，使新图中心节点颜色与原图一致，维持二者功能等价性。
4.3 无冲突场景下的颜色直接替换机制
在原图与新图的双向转换中，当新颜色与其他节点颜色无冲突时，可跳过复杂的颜色互换步骤，直接进行中心颜色替换，简化着色流程。
5 结论（可分可合，原图新图双向转换结构功能全等价）
本文提出的辐边总和公式借助虚拟环包裹与轮构型转换，将二维平面图简化为单中心轮图，利用轮图着色特性实现四色以内的着色方案。原图与新图的双向转换及功能等价性保证了着色结果的有效性，为平面图着色问题提供了可操作的理论框架。
关键词：二维平面图；辐边总和公式；轮构型；图着色；四色定理

辐边总和公式体系（原始表达式整理版）
一、核心参数定义
1. n：总节点数（n ≥ 4）
2. m：外围节点数（m ≥ 2）
3. d：第二层环节点数（d ≥ 2）
4. w：辐边总数
5. a：三角形个数
6. e：总边数
7. P：共享边个数
8. R：节点度数之和

、标准二维平面图
定义：由外向内两层及以上环加中心区域结构的平面图。
基础公式：w = 6(n - m - 1) + (m - d)
参数与特例同上。
二、非标准二维平面图（含孔洞）
定义：两层及以上环加中心结构，且孔洞为边数≥4的多边形。
修正项 z：
外围孔洞：z外 = N外 - 3v外（N为边数和，v为孔洞个数）
围内孔洞：z内 = 2(N内 - 3v内)
修正公式：w = 6(n - m - 1) + (m - d) - [ (N外 - 3v外) + 2(N内 - 3v内) ]
三、单层外围环加中心区域结构（含孔洞）
理论基准：以三边形为模，理论连接边数 e理论 = 2d - 3（d为围内节点数）。
修正项 z：比较实际连接边数 a 与 e理论：（其中a为围内节点连接边数），
若 e理论 < a，则 +z
若 e理论 > a，则 -z
若 e理论 = a，则 z=0
综合公式：w = 6(n - m - 1) + (m - d) ± z - [ (N外 - 3v外) + 2(N内 - 3v内) ]
四、多面体的处理
多面体可经展开、剪面、透视、三角剖分转为二维平面图，并视其结构选用上述公式：
双环+中心：用基础公式。
单层环+中心：用基础公式 ± 修正项z。
无环结构作为子结构均被涵盖。
五、普适公式（覆盖所有类型）
标准和非标准二维平面图，均可通过添加双层虚拟环（总节点6，每层3个）统一处理。
普适公式：w = 6(n新 - 4)，其中 n新 = n原 + 6。
六、单层或多层外环加中心区结构（含孔洞）的简化公式
简化公式：w = n + 3d - 4 ± z - [ (N外 - 3v外) + 2(N内 - 3v内) ]（d为围内节点数）
修正基准：以树型为模，理论连接边数 e理论 = d - 1（d为围内节点数）。
修正项 z：比较实际连接边数 a 与 e理论：（其中a为围内节点连接边数），
若 e理论 < a，则 +z
若 e理论 > a，则 -z
若 e理论 = a，则 z=0
重要提示：本公式体系仅适用于平面图，对于Kn全阶图（如K5、K3,3等非平面不适用。

二、基于n, m, d的基本公式
a = (n - 2) + (n - m) = 2n - m - 2
e = 2n + (n - m - 3) = 3n - m - 3
P = 2n + (n - m - 3) - m = 3n - 2m - 3
R = 6n - 2m - 6
三、基于w, m, d的导出公式
a = (w + 2m + d) / 3
e = (w + 3m + d) / 2
P = (w + m + d) / 2
R = w + 3m + d
四、w = 6(n-m-1) + (m-d)
1.a = {[6(n-m-1)+(m-d)] + 2m + d}/3= (6n - 3m - 6)/3 = 2n - m - 2
2.e = {[6(n-m-1)+(m-d)] + 3m + d}/2= (6n - 2m - 6)/2= 3n - m - 3
3.P = {[6(n-m-1)+(m-d)] + m + d}/2= (6n - 4m - 6)/2= 3n - 2m - 3
4.R = [6(n-m-1)+(m-d)] + 3m + d = 6n - 2m - 6
五、特殊对称情形（m = d = n / 2）
w = 6(n - n/2- 1)= 3n - 6
e = 3n - n/2- 3 =(5n)/2- 3
w = e + (n/2- 3)
e = w - (n/2- 3)

六. 含孔洞情形的修正公式
对于有孔洞的二维平面图，其中每个孔洞为边数≥4 的多边形，则：
修正项：z = N - 3v，其中 N 为所有孔洞边数总和，v 为孔洞个数
三边形个数修正公式：a = (n - 2) + (n - m) - (N - 2v)
a = w - [3(n - m - 2) + 2] - (N - 2v)
边的个数修正公式：  e = 2n + (n - m - 3) - (N - 3v)
                    e = （w + 3m + d）/2- (N - 3v)