平面三角化图纯代数计数公式，最终定稿。

朱明君

平面三角化图纯代数计数公式，最终定稿。

一、基本定义
设平面三角化图满足：
n：总顶点数，n ≥ 2；
m：边界顶点数，1 ≤ m ≤ n；
a：三角形个数；
e：总边数，含边界边与内部对角线。

二、构造原理与公式推导
初始状态，全边界三角剖分。
当所有顶点均在边界，m = n 时：
三角形数 a₀ = n − 2；
推导依据：简单多边形的三角剖分必然产生 n − 2 个三角形。
边数 e₀ = 2n − 3；
组成：n 条边界边 + n − 3 条内部对角线。

外弦内化操作：
每次操作选取边界环上连续三点 A、B、C，添加外弦边 AC 构成新三角形 ABC，使 B 转为内部顶点。
增量变化：
三角形数 +1，边数 +1，边界顶点数 −1。
操作次数 k = n − m，直至边界顶点数降至 m。

终止条件：
当边界顶点数 m 达到目标值时停止，此时内部顶点数为 n − m。

三、统一计数公式
通过线性叠加操作增量，得到纯代数表达式：
a = a₀ + k = n − 2 + n − m = 2n − m − 2；
e = e₀ + k = 2n − 3 + n − m = 3n − m − 3。

四、退化情形说明 n=2，m=1
对于 n=2，m=1，公式给出 e = 3n − m − 3 = 6 − 1 − 3 = 2；
或等价地 e = 2n + (n − m − 3) = 4 + (2 − 1 − 3) = 2。
此时图形可理解为：一个边界顶点（自环形成1边形）与一个内部顶点相连，构成两条边，例如一条自环和一条连接边，符合代数结果。
尽管结构退化，但公式仍保持自洽。

五、公式验证
全边界情形，m = n：
三角形数 a = 2n − n − 2 = n − 2；
边数 e = 3n − n − 3 = 2n − 3；
与初始状态一致。

最大平面图，m = 3：
三角形数 a = 2n − 3 − 2 = 2n − 5；
边数 e = 3n − 3 − 3 = 3n − 6；
满足最大平面图边数公式。

六、特性分析
欧拉公式验证：
代入平面图欧拉公式 n − e + f = 2，f = a + 1 为总面数。
代入后化简等式恒成立，证明拓扑一致性。

内部顶点贡献：
每个内部顶点通过外弦操作引入，严格贡献 1 个三角形、1 条边，体现线性可加性。

参数独立性：
公式仅依赖 n 和 m，无需引入面数、嵌入几何等额外参数，适用于算法复杂度分析、组合优化问题、平面图生成与验证。

七、双基准表述
三角形数基准：
a = 初始值 n − 2 + 增量 n − m；
基准点：n − m = 0，即全边界；
每增加一个内部顶点，a 增加 1。

边数基准：
e = 初始值 2n − 3 + 增量 n − m；
基准点：n − m = 0，即全边界；
每增加一个内部顶点，e 增加 1。

八、应用示例
问题：构造一个总顶点数 n=6、边界顶点数 m=4 的平面三角化图，计算 a 和 e。
解：
直接代入公式：
a = 2×6 − 4 − 2 = 6；
e = 3×6 − 4 − 3 = 11。

验证：
初始全边界 m=6 时，a=4，e=9；
执行 2 次外弦操作后，a=4+2=6，e=9+2=11，结果一致。

本公式通过严格的代数构造与验证，为平面三角化图提供了简洁、通用的计数工具，兼具理论严谨性与实用价值。面三角化图纯代数计数公式，最终定稿。

一、基本定义
设平面三角化图满足：
n：总顶点数，n ≥ 2；
m：边界顶点数，1 ≤ m ≤ n；
a：三角形个数；
e：总边数，含边界边与内部对角线。

二、构造原理与公式推导
初始状态，全边界三角剖分。
当所有顶点均在边界，m = n 时：
三角形数 a₀ = n − 2；
推导依据：简单多边形的三角剖分必然产生 n − 2 个三角形。
边数 e₀ = 2n − 3；
组成：n 条边界边 + n − 3 条内部对角线。

外弦内化操作：
每次操作选取边界环上连续三点 A、B、C，添加外弦边 AC 构成新三角形 ABC，使 B 转为内部顶点。
增量变化：
三角形数 +1，边数 +1，边界顶点数 −1。
操作次数 k = n − m，直至边界顶点数降至 m。

终止条件：
当边界顶点数 m 达到目标值时停止，此时内部顶点数为 n − m。

三、统一计数公式
通过线性叠加操作增量，得到纯代数表达式：
a = a₀ + k = n − 2 + n − m = 2n − m − 2；
e = e₀ + k = 2n − 3 + n − m = 3n − m − 3。

四、退化情形说明 n=2，m=1
对于 n=2，m=1，公式给出 e = 3n − m − 3 = 6 − 1 − 3 = 2；
或等价地 e = 2n + (n − m − 3) = 4 + (2 − 1 − 3) = 2。
此时图形可理解为：一个边界顶点（自环形成1边形）与一个内部顶点相连，构成两条边，例如一条自环和一条连接边，符合代数结果。
尽管结构退化，但公式仍保持自洽。

五、公式验证
全边界情形，m = n：
三角形数 a = 2n − n − 2 = n − 2；
边数 e = 3n − n − 3 = 2n − 3；
与初始状态一致。

最大平面图，m = 3：
三角形数 a = 2n − 3 − 2 = 2n − 5；
边数 e = 3n − 3 − 3 = 3n − 6；
满足最大平面图边数公式。

六、特性分析
欧拉公式验证：
代入平面图欧拉公式 n − e + f = 2，f = a + 1 为总面数。
代入后化简等式恒成立，证明拓扑一致性。

内部顶点贡献：
每个内部顶点通过外弦操作引入，严格贡献 1 个三角形、1 条边，体现线性可加性。

参数独立性：
公式仅依赖 n 和 m，无需引入面数、嵌入几何等额外参数，适用于算法复杂度分析、组合优化问题、平面图生成与验证。

七、双基准表述
三角形数基准：
a = 初始值 n − 2 + 增量 n − m；
基准点：n − m = 0，即全边界；
每增加一个内部顶点，a 增加 1。

边数基准：
e = 初始值 2n − 3 + 增量 n − m；
基准点：n − m = 0，即全边界；
每增加一个内部顶点，e 增加 1。

八、应用示例
问题：构造一个总顶点数 n=6、边界顶点数 m=4 的平面三角化图，计算 a 和 e。
解：
直接代入公式：
a = 2×6 − 4 − 2 = 6；
e = 3×6 − 4 − 3 = 11。

验证：
初始全边界 m=6 时，a=4，e=9；
执行 2 次外弦操作后，a=4+2=6，e=9+2=11，结果一致。

本公式通过严格的代数构造与验证，为平面三角化图提供了简洁、通用的计数工具，兼具理论严谨性与实用价值。