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

朱明君

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

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

1. 引言

二维平面图着色是图论经典难题，四色定理指出任何平面图可用四种颜色完成着色。本文提出辐边总和公式，通过将任意二维平面图（原图）转化为单中心轮图（新图），实现着色流程的规范化与简化。新图与原图的结构功能等价性确保着色结果可映射，为平面图着色提供系统化学术方法。辐边总和数既等于新单中心轮图的辐边总数，也等价于新图环上节点数与环边数的关联参数。

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

2.1 辐边总和公式

该公式适用于“由外向内两层及以上环+中心区域”的标准二维平面图，计算时按轮构型独立累加辐边数。其核心特征如下：

- 理论基础：除外围节点外，围内每个节点均为轮构型中心，点边可共享且模块间可叠加（所有二维平面图均由轮构型模块构成）；
- 核心目标：将复杂平面图转化为单中心轮图（仅需4色，与原图结构功能等价）；
- 体系独立性：作为纯代数公式，不受传统二维平面图定义约束，与欧拉公式分属不同理论体系。

基础公式：
w = 6(n - m - 1) + (m - d)
其中：

n  为节点总数（ n \geq 4 ）， m  为外围节点数（ m \geq 2 ）， d  为第二层环节点数（ d \geq 2 ）， w  为辐边数（ w \geq 6 ）；
系数6源于最小解：当  n = 4 、 m = d = 2  时， w = 6 ；
“减1”机制：用于扣除围内基准值，确保所有顶点度数≥1。

特殊情形：

若  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_{\text{新}} - 4)

参数定义：

n_{\text{原}} ：原图节点数（ n_{\text{原}} \geq 0 ）；
n_{\text{新}} = n_{\text{原}} + 6 ：添加虚拟环后新图的节点总数（6为双层虚拟环节点数）；
虚拟环功能：包裹原图，有效处理孔洞、亏格曲面、多面体等屏蔽结构；新图为实际存在的图，原图作为其子结构包含其中，移除虚拟环后可继承着色结果（色数≤4）。

2.3 原图与新图的结构转换

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

1.按围内节点数分解：围内有  N  个节点即分解为  N  个变形轮构型，记录几何形状；
2.标准化还原：通过“皮筋伸缩”操作将变形轮构型转化为标准轮构型；
3.扇形化处理：在各标准轮构型环上节点与边的连接处断开，经伸缩形成扇形（中心节点呈点片状，两端为节点端与边端）；
4.拼接重组：扇形节点端与相邻边端对接，所有扇柄（中心节点）叠加，生成单中心轮图。

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

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

3. 新单中心轮图的最优着色规则

着色方案由新图环上节点数的奇偶性决定：

奇环（ n = 2m + 1 ）：环上节点用2色交替着色  m  次，剩余1个节点用第3色，中心节点用第4色（共4色）；
偶环（ n = 2m ）：环上节点用2色交替着色  m  次，中心节点用第3色（共3色）。

核心约束：若原图含任一奇轮构型模块，即使新图为偶环，也需采用4色方案，确保映射回原图无冲突。

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

4.1 原图到新图的功能保持

各轮构型中心节点颜色存在差异时，选取占比最多的颜色作为新图中心颜色，其余模块通过“中心-环节点颜色互换”实现中心颜色统一，维持功能等价。

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

新图分解后，若中心节点颜色与原图冲突，通过“中心-环节点颜色互换”调整一致，确保着色结果可继承。

4.3 无冲突直接替换机制

若新颜色与其他节点无冲突，可跳过颜色互换步骤，直接替换中心颜色，简化流程。

5. 结论

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

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



附录：公式扩展应用与补充说明

1.非标准图（含孔洞）修正：
修正项  z = (N_{\text{外}} - 3v_{\text{外}}) + 2(N_{\text{内}} - 3v_{\text{内}}) （ N  为边数和， v  为孔洞个数），修正公式：
w = 6(n - m - 1) + (m - d) - z
2.单层外围环结构修正：
以三边形为模，理论边数  e_{\text{理论}} = 2d - 3 （ d  为围内节点数），比较实际边数  a  引入修正项  \pm z ，综合公式：
w = 6(n - m - 1) + (m - d) \pm z - [(N_{\text{外}} - 3v_{\text{外}}) + 2(N_{\text{内}} - 3v_{\text{内}})]
3.普适简化公式：
适用于单/多层外环+中心区结构（基于树型模理论边数  e_{\text{理论}} = d - 1 ）：
w = n + 3d - 4 \pm z - [(N_{\text{外}} - 3v_{\text{外}}) + 2(N_{\text{内}} - 3v_{\text{内}})]

重要注记：本公式体系仅适用于平面图，对  K_n  全阶非平面图（如  K_5 、 K_{3,3} ）不适用。

辅助计算公式（与传统欧拉公式无关）：

三边形个数： a = (n - 2) + (n - m)
边的个数： e = 2n + (n - m - 3)



四色定理结构化证明术语体系

一、核心定义

1.二维平面图（三角剖分标准图）
经三角剖分的平面图，呈“由外向内至少两层环+中心区域”结构；点边共享可分解为轮构型模块，中心区域可容纳任意平面图（含可平面化立体图）；围内节点（中心区域+第二层环节点）均为轮构型中心，外围节点（最外层环节点）仅作为模块连接节点。
2.轮构型
含辐边的图结构范式，核心参数为辐边总和数  w （所有辐边的总数）。
3.轮构型分解
按围内节点数  N = n_{\text{原}} + 3 = n_{\text{新}} - 3 ，将标准图  G_{\text{标}}  拆分为  N  个轮构型模块；操作方式为：在模块环上节点与边的连接处断开，经辐边与环边伸缩变形为扇形；接口为凸形“节点端”（榫头）与凹形“边端”（卯眼），构成榫卯插拨机制，分则为扇形、合则为圆扇。
4.拼接
重组扇形模块的操作：通过榫卯结构将各模块节点端与相邻边端对接，所有模块中心节点叠加为单一点，生成全新单中心轮图（标准轮构型）。
5.虚拟环（含参数约定）
预处理非标准平面图的辅助构造，含两层环（最外层  m = 3 、第二层  d = 3 ），共引入6个虚拟节点；功能为包裹原图，使整体满足标准图结构。

二、参数与公式

1.参数定义
n_{\text{原}} ：原图节点数（ n_{\text{原}} \geq 0 ）；
n_{\text{新}} ：标准图节点数（ n_{\text{新}} = n_{\text{原}} + 6 ， n_{\text{新}} \geq 4 ）；
m ：最外层环节点数（约定  m = 3 ）；
d ：第二层环节点数（约定  d = 3 ）；
w ：新单中心轮图辐边总数（ w \geq 6 ）。
2.公式体系
基础公式： w = 6(n_{\text{新}} - m - 1) + (m - d) ；
简化公式（ m = d ）： w = 6(n_{\text{新}} - m - 1) ；
普适公式（ m = d = 3 ）： w = 6(n_{\text{新}} - 4) = 6(n_{\text{原}} + 2) 。

三、理论总流程

1.输入：任意平面图  G_{\text{原}} （ n_{\text{原}} \geq 0 ）；
2.预处理：添加  m = d = 3  的虚拟环，生成标准图  G_{\text{标}} （ n_{\text{新}} = n_{\text{原}} + 6 ）；
3.分解：拆分  G_{\text{标}}  为  N = n_{\text{原}} + 3  个扇形模块；
4.拼接：通过榫卯对接生成单中心轮图；
5.计算验证：辐边数  w = 6(n_{\text{原}} + 2) ；
6.着色映射：按  w  奇偶性着色（偶数3色、奇数4色），逆映射移除虚拟环，得到原图四色方案。

四、体系自洽性说明

符号统一：参数定义明确， m 、 d  固定为3，无歧义；
逻辑闭环：虚拟环衔接输入与公式，推导过程严格一致；
操作确定：分解、拼接、着色步骤清晰，结果可复现；
普适性：公式覆盖所有可平面化图，确保四色着色存在性。