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

朱明君

辐边总和公式及其在二维平面图着色中的应用
作者：朱火华
日期：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. 结论
本文提出的辐边总和公式借助虚拟环包裹与轮构型转换，把二维平面图简化为单中心轮图，利用轮图着色特性实现四色以内的着色方案。原图与新图的双向转换及功能等价性保证了着色结果的有效性，为平面图着色问题提供了可操作的理论框架。
关键词：二维平面图；辐边总和公式；轮构型；图着色；四色定理

附录：公式扩展应用与补充说明
1.非标准图（含孔洞）修正： 修正项：z = (N外 - 3v外) + 2(N内 - 3v内) (N:边数和, v:孔洞个数)
修正公式：w = 6(n - m - 1) + (m - d) - z
2. 单层外围环结构修正：
以三边形为模，理论边数 e理论 = 2d - 3 (d为围内节点数)。比较实际边数 a 与 e理论 引入修正项 ±z。 综合公式：w = 6(n - m - 1) + (m - d) ± z - [(N外 - 3v外) + 2(N内 - 3v内)]
3. 普适简化公式：
适用于单/多层外环加中心区结构：w = n + 3d - 4 ± z - [(N外 - 3v外) + 2(N内 - 3v内)]
此处修正项 ±z 基于树型模理论边数 e理论 = d - 1 的比较。

重要注记：本公式体系适用于平面图，对Kn全阶图（如K5, K3,3等非平面图）不适用。

辅助计算公式（与传统欧拉公式无关）
设 n 为节点数，m 为外围节点数。
三边形个数：a = (n - 2) + (n - m)
边的个数：e = 2n + (n - m - 3)

朱明君

https://www.doubao.com/podcast/14055585cdab

朱明君

四色定理结构化证明术语体系（最终定稿）

一、核心定义

1. 二维平面图（三角剖分标准图）
经三角剖分的平面图，呈“由外向内至少两层环 + 中心区域”标准结构。

· 点边共享性：可分解为轮构型模块。
· 中心区域：可容纳任意平面图（包括可平面化的立体图）。
· 节点归属：
  · 围内节点：包括中心区域所有节点及第二层环全部节点，每个围内节点作为一个轮构型模块的中心。
  · 外围节点：指最外层环节点，不作为轮构型中心，仅作为模块间的连接节点。

2. 轮构型
含辐边的图结构范式，核心参数为 辐边总和数 w（所有辐边的总数）。

3. 轮构型分解
将标准图 G_{\text{标}} 按 围内节点数 N 拆分为 N 个轮构型模块（N = n_{\text{原}} + 3，其中 n_{\text{原}} 为原图节点数）。

· 操作：在每个模块环上选择一节点的一侧，断开其与边的连接，通过辐边与环边的伸缩变形使模块成为扇形。
· 接口机制：
  · 节点端：对应原图中节点的连接位置，在模块边界上呈现为“凸”形接口（可想象为榫头）。
  · 边端：对应原图中边的中间位置，在模块边界上呈现为“凹”形接口（可想象为卯眼）。
  · 节点端与边端形状互补，构成榫卯插拨机制。
· 结果：分则为扇形，合则为圆扇。

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）。
· 围内节点数 N = n_{\text{原}} + 3 = n_{\text{新}} - 3。

2. 公式体系

· 基础公式：
  w = 6(n_{\text{新}} - m - 1) + (m - d)
  \]  
  系数 6 源于最小解（当 n_{\text{新}} = 4, m = d = 2 时 w = 6）。
· 简化公式（当 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{原}} 得到标准图 G_{\text{标}}（n_{\text{新}} = n_{\text{原}} + 6）。
3. 分解：对 G_{\text{标}} 进行轮构型分解，得到 N = n_{\text{原}} + 3 个扇形模块。
4. 拼接：将各模块的节点端与边端依次对接，中心节点叠加为一点，生成新单中心轮图。
5. 计算验证：新轮图的辐边总数 w 必满足 w = 6(n_{\text{原}} + 2)。
6. 着色映射：
   · 基于 w 的奇偶性对新轮图着色（偶数用 3 色，奇数用 4 色）。
   · 通过逆映射移除虚拟环，经局部调整得到原图 G_{\text{原}} 的有效四色着色方案。

四、体系自洽性说明

· 符号统一：所有参数明确定义，m, d 固定为 3，无歧义。
· 逻辑闭环：虚拟环衔接任意输入与普适公式，推导严格一致。
· 操作确定：分解、拼接、着色映射每一步均有清晰界定，结果可复现。
· 结论普适：公式 w = 6(n_{\text{原}} + 2) 适用于一切可平面化图，保证四色着色存在性。

---

修改说明：

1. 在定义 3 中明确“节点端”和“边端”的具体形状（凸形榫头、凹形卯眼）和互补关系，使榫卯机制更易理解。
2. 在定义 4 中强调拼接时节点端与边端的对接动作，增强操作直观性。
3. 保持其他部分不变，确保逻辑连贯性。

此版本在保持严格性的同时，通过直观的几何类比提升了可理解性，为四色定理的结构化证明提供清晰、自洽的概念基础。