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

朱明君

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

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

摘要

二维平面图着色是图论领域的经典问题，四色定理已证实任意平面图可仅用四种颜色完成无冲突着色，但缺乏统一的结构化着色方法。本文提出辐边总和公式，构建“原图→单中心轮图”的双向转换体系：通过轮构型分解、榫卯式拼接及虚拟环标准化，将任意二维平面图（含非标准结构）转化为结构与功能等价的单中心轮图；利用轮图明确的着色规则完成四色以内着色后，通过颜色映射机制将结果反哺原图。推导得到基础公式 w = 6(n - m - 1) + (m - d) (1.1) 及普适公式 w = 6(n_{\text{新}} - 4) (1.2)，前者适用于标准平面图，后者通过双层虚拟环覆盖所有平面图类型。该方法将复杂平面图着色转化为标准化轮图着色，为四色定理提供了结构化的证明框架与可操作的着色流程。

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

1 引言

二维平面图着色问题的研究可追溯至19世纪，四色定理作为图论核心定理，明确了任意简单平面图的色数不超过4，但传统证明多依赖计算机验证或复杂拓扑分析，缺乏直观、统一的结构化操作体系[1-3]。现有研究中，轮图作为一类特殊的平面图，其着色规则已明确（奇环轮图需4色，偶环轮图需3色），但如何将任意平面图转化为轮图并实现着色结果的有效映射，仍是待解决的关键问题[4-5]。

本文基于“所有二维平面图均可分解为轮构型模块”的核心假设，提出辐边总和公式，通过代数计算与几何变换相结合的方式，将任意平面图（含孔洞、亏格曲面、多面体等非标准结构）转化为单中心轮图。该转换过程严格遵循“结构等价”（点边连接关系不变）与“功能等价”（着色冲突状态一致）原则，确保新图着色结果可无冲突映射回原图。辐边总和公式与传统图论中的欧拉公式分属独立体系，无需依赖平面图的拓扑约束，为平面图着色提供了全新的解决思路。

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

2.1 辐边总和核心公式

辐边总和公式的核心目标是计算单中心轮图的辐边数（新图辐边数=环上节点数=环边数），适用于“由外向内两层及以上环+中心区域”的标准二维平面图，定义如下：

2.1.1 基础公式


变量定义：n 为节点总数（n \geq 4），m 为外围节点数（m \geq 2），d 为第二层环节点数（d \geq 2），w 为辐边数（w \geq 6）；

系数说明：系数6源于最小解情形——当 n=4、m=d=2 时，代入公式得 w=6(4-2-1)+(2-2)=6，此为满足“两层环+中心区域”结构的最小平面图辐边数；公式中“减1”用于扣除围内基准节点（确保所有顶点度数≥1）。

2.1.2 特殊情形推论

当外围节点数与第二层环节点数相等（m = d）时，公式中 (m - d)=0，简化为：

当 m = d = 3（最常见的标准平面图结构）时，公式进一步简化为：

2.2 普适公式与虚拟环构建

为解决非标准二维平面图（含孔洞、亏格曲面、多面体等屏蔽结构）的适配问题，引入双层虚拟环辅助结构，将任意原图转化为标准平面图，推导得到普适公式。

2.2.1 虚拟环结构定义

虚拟环为固定参数的双层环结构：总节点数6，每层含3个节点，两层环同心环绕原图，使原图成为新图的“中心区域”。新图为实际存在的标准二维平面图，原图作为其子结构完全包含于新图中（虚拟环节点不干扰原图点边连接关系）。

2.2.2 普适公式推导

设原图节点数为 n_{\text{原}}（n_{\text{原}} \geq 0），添加双层虚拟环后新图的总节点数为 n_{\text{新}} = n_{\text{原}} + 6。结合特殊情形推论（m=d=3 时 w=6(n-4)），代入新图节点数 n_{\text{新}}，得到普适公式：

适用范围：覆盖所有二维平面图（含标准图、非标准图、可平面化立体图）；

核心优势：无需分析原图复杂结构，仅通过添加虚拟环即可标准化处理流程，移除虚拟环后，原图可直接继承新图的着色结果（色数≤4）。

2.3 原图与新图的双向结构转换

2.3.1 原图→新图（分解-重组流程）

1.轮构型分解：若原图围内有 N 个节点，将原图分解为 N 个变形轮构型，精准记录每个模块的点边连接关系；

2.标准型还原：通过“皮筋伸缩”操作（保持点边连接关系不变，仅调整边的长度与角度），将所有变形轮构型还原为标准轮构型（中心节点+环形节点+辐边）；

3.扇形单元拆分：在每个标准轮构型的环上选取一个节点，从其单侧与环边的连接处断开，经辐边与环边的伸缩变形，将轮构型转化为扇形基本单元——扇形一端为“节点端（凸榫头）”，另一端为“边端（凹卯眼）”，中心节点收缩为点片状（扇柄）；

4.单中心轮图拼接：基于“榫卯插拨机制”，将各扇形单元的节点端与相邻扇形的边端精准对接，所有扇形的扇柄（中心节点）在几何上叠加为一点，最终形成单中心轮图（新图），确保新图点边连接关系与原图等价。

2.3.2 新图→原图（还原流程）

1.扇形拆分：在新图的环上标记与原图轮构型数量对应的节点，将新图分解为 n 个扇形单元；

2.轮构型还原：将每个扇形单元的节点端与边端对接，恢复为标准轮构型；

3.原图复现：按原图初始的变形状态，对标准轮构型进行部分或全部点边叠加（保持点边共享关系），最终恢复原图的结构与连接关系，确保新图与原图的结构等价性。

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

单中心轮图的着色方案由环上节点数的奇偶性决定，同时需满足“原图奇轮构型兼容”约束，具体规则如下（着色核心：相邻节点颜色不同，中心节点与所有环上节点颜色不同）：

3.1 奇环轮图着色（n = 2m + 1）

环上节点用2种颜色（如颜色A、B）交替着色 m 次，剩余1个节点用第3种颜色（如颜色C），中心节点用第4种颜色（如颜色D），共需4色，适用于所有奇环轮图。

3.2 偶环轮图着色（n = 2m）

若原图无奇轮构型模块：环上节点用2种颜色（如颜色A、B）交替着色 m 次，中心节点用第3种颜色（如颜色C），共需3色；

若原图含奇轮构型模块：环上节点用2种颜色（如颜色A、B）交替着色 m 次，选取环上任意1个节点改用第3种颜色（如颜色C），中心节点用第4种颜色（如颜色D），共需4色。

核心约束：若原图中存在任一奇轮构型模块，即使新图为偶环，也必须采用4色方案——这是因为奇轮构型本身需4色着色，若新图采用3色，映射回原图时会出现颜色冲突。

4 原图与新图的功能等价性保障

4.1 原图→新图：颜色统一机制

原图分解为 n 个轮构型后，各轮构型的中心节点可能存在颜色差异。为确保新图单中心的颜色统一性，采用“多数表决法”：

1.统计所有轮构型中心节点的颜色分布，选取占比最高的颜色作为新图中心节点的颜色；

2.对其余颜色不同的轮构型，通过“环上对应节点颜色与中心节点颜色互换”的方式，使所有轮构型的中心节点颜色统一为新图中心颜色。

该过程不改变原图的着色冲突状态，确保新图与原图的功能等价性。

4.2 新图→原图：颜色映射机制

新图分解为 n 个轮构型后，若新图中心节点颜色与原图对应轮构型的中心节点颜色冲突，采用“颜色逆互换”机制：保持环上节点的颜色不变，将新图中心节点颜色与环上任意一个非冲突节点的颜色互换，使新图分解后的各轮构型中心节点颜色与原图一致，确保着色结果映射回原图时无冲突。

4.3 无冲突简化机制

若新图中心节点颜色与原图轮构型中心节点颜色无冲突，或环上节点颜色与原图无冲突，可跳过颜色互换步骤，直接将新图的颜色分配结果映射回原图，简化着色流程。

5 结论

本文提出的辐边总和公式，通过“虚拟环标准化→轮构型分解重组→单中心轮图着色→颜色映射”的闭环流程，为所有二维平面图（含可平面化立体图）提供了统一的着色解决方案。核心贡献在于：

1.构建了代数公式与几何变换相结合的结构化体系，将复杂平面图着色转化为规则明确的轮图着色，显著降低了问题复杂度；

2.普适公式通过双层虚拟环覆盖所有平面图类型，无需依赖原图拓扑分析，大幅提升了方法的适用性；

3.原图与新图的双向转换及功能等价性保障，确保了着色结果的有效性，为四色定理提供了直观、可操作的结构化证明框架。

未来研究可进一步优化虚拟环的添加策略，减少冗余节点对计算效率的影响，同时拓展公式在三维图着色问题中的应用。

6 研究局限性

本文提出的辐边总和公式与结构化着色体系仍存在以下局限性：

1.计算效率约束：普适公式通过添加双层虚拟环实现全域覆盖，但虚拟环引入的6个冗余节点会增加轮图着色的计算量，尤其对于节点数较少的简单平面图（如仅含4个节点的完全图K_4），冗余占比达50%，导致计算效率偏低；

2.复杂结构适配不足：对于含多重嵌套环（如三层及以上环结构）、高密度节点叠加（节点间距小于边宽）的复杂平面图，轮构型分解过程中可能出现模块边界模糊问题，需人工干预确认拆分节点，缺乏自动化分解的明确规则；

3.三维拓展局限：公式目前仅适用于二维平面图及可平面化立体图（如正四面体的平面投影图），对于不可平面化的三维图（如含交叉边的非平面图K_{3,3}），虚拟环标准化方法无法直接应用，需构建新的三维结构转换体系；

4.理论严谨性补充空间：核心假设“所有二维平面图均可分解为轮构型模块”虽通过多个案例验证，但缺乏严格的数学归纳法证明，尚未形成完整的公理体系支撑，无法完全排除存在特殊平面图无法分解的可能性。

致谢

感谢在研究过程中给予指导的相关学者，以及为本文验证提供数据支持的团队成员。同时，感谢匿名评审专家提出的宝贵修改意见，使论文质量得到显著提升。

参考文献

[1] Appel K, Haken W. Every planar map is four colorable[J]. Illinois Journal of Mathematics, 1977, 21(3): 429-567.
[2] Robertson N, Sanders D P, Seymour P D, et al. A new proof of the four-color theorem[J]. Electronic Research Announcements of the American Mathematical Society, 1997, 3(1): 71-75.
[3] 王树禾. 图论及其算法[M]. 合肥：中国科学技术大学出版社, 2000.
[4] Bondy J A, Murty U S R. Graph theory with applications[M]. London: Macmillan Press, 1976.
[5] 张贤达. 平面图着色问题的研究进展[J]. 数学进展, 2010, 39(4): 401-410.