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

朱明君

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

作者：朱火华
日期：2025年11月25日

1. 引言
二维平面图的着色问题是图论中的经典难题。四色定理表明，任何平面图均可使用四种颜色进行着色。本文提出了辐边总和公式，通过将任意二维平面图（原图）简化为单中心轮图（新图），实现了着色过程的规范化和简化。新图与原图在结构和功能上的等价性，确保了着色结果的可映射性，为平面图着色提供了系统化的方法。辐边总和数等于新单中心轮图的辐边数，也等于环上节点数与新图环边数。

2.辐边总和公式与图结构转换
辐边总和公式适用于由外向内两层及以上环加中心区域结构的标准二维平面图，
也包括中心区域任意结构的平面图，其中中心区域节点数≥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”是为减去围内一个基准值，且所有顶点度数均≥1。
特殊情形下：
若 m= d，且m+d为≥ 4的偶数。
则 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 原图与新图的结构转换
2.3.1 原图分解至新图的转换步骤

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

输入图→弦边处理→孔洞剖分→标准图→拆出→还原→扇化分解→w计算→拼接→新单中心轮图→着色→逆向操作→颜色调和→原图着色

重要注记

本体系仅适用于二维平面图及可平面化图，不适用于k5，k3.3非平图

附录：n色定理
完全图Kn着色，每个节点度数n-1，正常着色需要n种颜色。
完全图本身的定义只要求顶点两两相连；为适配地图四色着色问题，限定：n≤4的完全图属于平面图，n≥5的全连接完全图视作非平面图。
四边形加一条对角线为4顶点5边构型，一般3色够用，4色也可以；补全全部6条邻接边得到完全图K4，该局部构型强制需要4色。