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

朱明君

辐边总和公式及其在二维平面图着色中的应用
作者：朱火华
日期：2025年11月25日
1. 引言
二维平面图的着色问题是图论中的经典难题。四色定理指出，任何平面图都能用四种颜色完成着色。本文提出辐边总和公式，通过将任意二维平面图（原图）简化为单中心轮图（新图），实现着色过程的规范与简化。新图与原图在结构与功能上的等价性确保了着色结果的可映射性，为平面图着色提供了系统方法。辐边总和数等于新单中心轮的辐边数，也等于环上节点数与新图环边数。
2. 辐边总和公式与图结构转换
2.1 辐边总和公式
辐边总和公式适用于由外向内两层及以上环加中心区域结构的标准二维平面图，也包括中心区域任意结构的平面图。计算时，每轮构型的辐边独立计算后相加。在二维平面图中，除外围节点外，围内每个节点均为轮构型中心，点边可共享，轮构型间部分或全部点边叠加（即所有二维平面图都是由轮构型模块叠加而成）。该公式的目的是将其转换为单中心轮图，以简化着色（单中心轮图仅需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，则 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。
2.3原图与新图的结构转换
2.3.1 原图分解至新图的转换步骤
1. 将原图分解，若原图围内有 N 个节点，则可分解出 N 个变形轮构型，并记录其几何形状；
2. 通过边与辐边的“皮筋伸缩”操作，将变形轮构型还原为标准轮构型；
3. 选取各标准轮构型环上某一节点的一侧与边的连接处断开，经边与辐边伸缩形成扇形，使中心节点呈点片状，扇形两端分别为节点端与边端（注：中心节点为扇柄中的扇钉或点片，辐边为扇骨，环边为扇纸）；
4. 将所有扇形拼接为单中心轮图：扇形一侧的节点端与另一扇形一侧的边端连接，所有扇形扇柄以点片叠加。
2.3.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. 结论
本文提出的辐边总和公式借助虚拟环包裹与轮构型转换，将二维平面图简化为单中心轮图，利用轮图着色特性实现四色以内的着色方案。原图与新图的双向转换及功能等价性保证了结构功能的全面等价。着色结果的有效性为平面图着色问题提供了可操作的理论框架。
关键词：二维平面图；辐边总和公式；轮构型；图着色；四色定理
附录一：
一，原图与新图的结构转换
原图（标准二维平面图）点边共享，因此可以分解出轮构型模块。
原图参数：n=7，m=4，d=3，计算公式为 6(7-4-1)+(4-3)=13。
原图分解至新图的转换步骤：
1.原图内有3个节点，可分解为3个变形轮构型模块，记录其几何形状；
即构型1为1+5，构型2和3分别为1+4，总计5+4+4=13 。
通过边与辐边的“皮筋伸缩”操作，将变形轮构型还原成标准轮构型。
(原图分解为3个轮构型后，若中心节点颜色有差异，选取占比最多的颜色作为新图中心颜色，其余轮构型将环上对应节点颜色与中心节点颜色互换，以确保新图与原图功能等价
2.选取各标准轮构型环上一节点的一侧与边的连接处断开，
3.经边与辐边伸缩形成扇形，中心节点呈点片状，扇形两端分别为节点端与边端；
将所有扇形拼接为单心轮：扇形一侧节点端与另一扇形一侧边端连接，所有扇形扇柄以点片叠加。
附录二：
新图还原至原图的转换步骤
1.从新图环上标记节点分解出3个扇形；
将各扇形两端连接，还原成标准轮构型；

(新图分解为3个轮构型时，若中心节点颜色与原图中心颜色冲突，将新图中心节点颜色与环上节点颜色互换，
按原变形状态通过部分或全部点边叠加，恢复原图结构，确保新图与原图结构等价。
附录三：
原图与新图的功能等价性
4.1 原图到新图的功能保持
原图分解为3个轮构型后，若中心节点颜色有差异，选取占比最多的颜色作为新图中心颜色，其余轮构型将环上对应节点颜色与中心节点颜色互换，使所有中心节点颜色统一，确保新图与原图功能等价。
原图
新图

新图轮构型1：中心节点颜色由原图的3改为1；环上原本颜色为1的节点，颜色改为3（实现中心与环上对应节点颜色互换）。
新图轮构型2：中心节点颜色为1；环上节点颜色沿用原图轮构型2中环上节点的颜色。
新图轮构型3：中心节点颜色由原图的2改为1；环上原本颜色为1的节点，颜色改为2（实现中心与环上对应节点颜色互换）。
附录四：
新图到原图的颜色一致性映射
新图分解为3个轮构型时，若中心节点颜色与原图中心颜色冲突，将新图中心节点颜色与环上节点颜色互换，使新图中心节点颜色与原图一致，维持二者功能等价。### 等价性
#### 新图

## 原图

1. **原图轮构型1**：
   - 中心节点颜色：由新图的颜色1调整为3；
   - 环上节点颜色：原本为颜色3的节点，调整为1；
   - 核心逻辑：中心节点与环上颜色为3的节点实现颜色互换。
2. **原图轮构型2**：
   - 中心节点颜色：固定为1；
   - 环上节点颜色：直接沿用新图轮构型2中环上节点的颜色（无修改）。
3. **原图轮构型3**：
   - 中心节点颜色：由新图的颜色1调整为2；
   - 环上节点颜色：原本为颜色2的节点，调整为1；
   - 核心逻辑：中心节点与环上颜色为2的节点实现颜色互换。
### 附录二：四色定理结构化证明术语体系
#### 一、核心定义
1. **标准二维平面图（三角剖分图）**：
   - 指满足“由外向内至少两层环加中心区域”标准结构的平面图。
   - 中心区域：可包含任意平面子图（包括可平面化的立体图）。
   - 核心性质：具有点边共享性，即全图可被分解为若干“轮构型”基本模块。
2. **轮构型**：
   - 一种以单个中心节点、一个环绕该中心的节点环，以及连接中心与环上每一节点的“辐边”为特征的图结构范式。
   - 核心参数：辐边总和数（w），即所有辐边的总数。
3. **原图轮构型分解**：
   - 将标准二维平面图（原图）按其围内节点数拆分为相应数量轮构型模块的操作。其中，围内节点包括中心区域所有节点及第二层环全部节点。
4. **轮构型模块分解**：
   - 对单个轮构型模块进行的细分操作：
     - 操作：于模块环上任选一节点，从其单侧断开与环边的连接，通过辐边与环边的伸缩变形，使模块变为扇形基本单元。
     - 接口机制：扇形边界形成两类接口：
       - 节点端（凸，榫头）：对应原图中节点的连接位置。
       - 边端（凹，卯眼）：对应原图中边的中间位置。
     - 二者构成榫卯插拨机制。状态概括为：分则为扇形，合则为圆扇。
5. **拼接**：
   - 将分解所得的扇形单元重组的操作：
     - 方式：依榫卯机制，将各扇形的节点端与相邻扇形的边端精确对接。
     - 核心：所有扇形的中心节点（扇柄）在几何上叠加为一点。
     - 结果：生成一个全新的单中心轮图（即标准轮构型）。
6. **虚拟环**：
   - 为使任意平面图满足“标准二维平面图”形式而引入的固定辅助结构。
   - 结构：具有固定参数的双层环。
   - 功能：包裹原图，使其成为新标准图的“中心区域”，从而实现流程起点的统一与标准化。
#### 二、体系自洽性说明
1. **概念自洽**：所有核心概念（如标准图、轮构型、榫卯接口、虚拟环）均围绕“分解-重组-着色”这一核心变换流程定义，彼此支撑，形成闭环。
2. **操作确定**：从预处理（添加虚拟环）、分解（获得扇形模块、拼接（生成新单中心轮图）、着色与逆映射，每一步均由明确且可重复的几何与组合操作严格界定。
3. 逻辑闭环：虚拟环作为关键桥梁，将任意输入图转化为具有统一结构的标准图，确保后续变换流程的普遍适用性。整个体系从输入到输出，构成一个完整的逻辑链条。
4. 结论普适：本术语体系为所有可平面化图提供了一个统一的结构化分析与处理框架，通过上述确定的操作流程，最终确保四色着色方案的存在性。
5. 虚拟环：一个具有固定参数（共6节点，每层3节点）的双层环结构。
附录三：
公式扩展应用与补充说明
1.非标准图（含孔洞）修正：
2.修正项：\( z = (N_{\text{外}} - 3v_{\text{外}}) + 2(N_{\text{内}} - 3v_{\text{内}}) \)（\( N \)：边数和，\( v \)：孔洞个数）
3.修正公式：\( w = 6(n - m - 1) + (m - d) - z \)
4.单层外围环结构修正：
5.以三边形为模，理论边数 \( e_{\text{理论}} = 2d - 3 \)（\( d \)为围内节点数）。比较实际边数 \( a \) 与 \( e_{\text{理论}} \)，引入修正项 \( \pm z \)。
综合公式：\( w = 6(n - m - 1) + (m - d) \pm z - [(N_{\text{外}} - 3v_{\text{外}}) + 2(N_{\text{内}} - 3v_{\text{内}})] \)
6.普适简化公式：
7.适用于单/多层外环加中心区结构：\( w = n + 3d - 4 \pm z - [(N_{\text{外}} - 3v_{\text{外}}) + 2(N_{\text{内}} - 3v_{\text{内}})] \)，此处修正项 \( \pm z \) 基于树型模理论边数 \( e_{\text{理论}} = d - 1 \)的比较。
8.重要注记：本公式体系适用于平面图，对 \( K_n \) 全阶图（如 \( K_5 \)、\( K_{3,3} \) 等非平面图）不适用。
9.辅助计算公式（与传统欧拉公式无关）
设 \( n \) 为节点数，\( m \) 为外围节点数。
三边形个数：\( a = (n - 2) + (n - m) \)
边的个数：\( e = 2n + (n - m - 3) \)