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

朱明君

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

1. 引言

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

2. 辐边总和公式与图结构转换

2.1 辐边总和公式

在二维平面图中，除外围节点外，每个内部节点均可视为轮构型中心，节点与边可共享，轮构型可部分或完全叠加。辐边总和公式定义为：


w = 6(n - 4)


其中：

-  d  为二维平面图（原图）的节点个数；
-  v  为两层虚拟环的节点个数，每层含3个节点，总  v = 6 ；
-  n = v + d ，为添加虚拟环后的新图节点总数。

公式通过双层虚拟环包裹原图，自动处理孔洞、亏格、多面体等屏蔽结构。添加虚拟环后的新图为真实存在的图，原图作为其子结构存在。

2.2 原图与新图的结构转换

2.2.1 原图分解至新图的转换步骤

1.原图区域内  n  个节点各分解为  n  个变形轮构型，记忆其几何形状；
2.通过边与辐边的“皮筋伸缩”操作，将变形轮构型还原为标准轮构型；
3.选取各标准轮构型环上一节点的一侧与边的连接处断开，经边与辐边伸缩形成扇形，中心节点呈点片状，扇形两端分别为节点端与边端；
4.将所有扇形拼接为单心轮：扇形一侧节点端与另一扇形一侧边端连接，所有扇形扇柄以点片叠加。

2.2.2 新图还原至原图的转换步骤

1.从新图环上标记节点分解出  n  个扇形；
2.将各扇形两端连接，还原为标准轮构型；
3.按原变形状态通过部分或全部点边叠加，恢复原图结构，确保新图与原图结构等价。

3. 单中心轮图的最优着色问题

单中心轮图的着色规则由环上节点数  n  的奇偶性决定：

- 当  n = 2m + 1 （奇环）时：
环上以2种颜色交替着色  m  次，剩余1个节点用第3种颜色，中心节点用第4种颜色，总颜色数为  2 + 1 + 1 = 4 。
- 当  n = 2m （偶环）时：
环上用2种颜色交替着色  m  次，中心节点用第3种颜色，总颜色数为  2 + 1 = 3 。

4. 原图与新图的功能等价性

4.1 原图到新图的功能保持

原图分解为  n  个轮构型后，若中心节点颜色存在差异，选取占比最多的颜色作为新图中心颜色，其余轮构型将环上对应节点颜色与中心节点颜色互换，使所有中心节点颜色统一，确保新图与原图功能等价。

4.2 新图到原图的颜色一致性映射

新图分解为  n  个轮构型时，若中心节点颜色与原图中心颜色冲突，将新图中心节点颜色与环上节点颜色互换，使新图中心节点颜色与原图一致，维持二者功能等价性。

5. 结论

本文提出的辐边总和公式通过虚拟环包裹与轮构型转换，将二维平面图简化为单中心轮图，利用轮图着色特性实现四色以内的着色方案。原图与新图的双向转换及功能等价性保证了着色结果的有效性，为平面图着色问题提供了可操作的理论框架。

关键词：二维平面图；辐边总和公式；轮构型；图着色；四色定理