平面三角化图边数与三角形数统一公式

朱明君

平面三角化图边数与三角形数统一公式及稠密性刻画

（精简打印版）
作者：朱火华
学科领域：图论与组合数学

摘要

本文针对连通平面图，引入边界顶点数 m，给出平面三角化图统一计数公式：边数 e = 3n - m - 3，内部三角形数 a = 2n - m - 2。公式以“外弦内化”构造法推导，统一了多边形三角剖分、最大平面图与退化稠密平面图，并与欧拉公式拓扑自洽。结果表明：平面三角化图边数从 2n-3 到 3n-5 连续取值，精确覆盖平面图边数区间最稠密上半段，为稠密平面图结构与计数提供统一刻画。

关键词：平面图；平面三角化图；三角剖分；边数公式；欧拉公式


1 引言

连通平面图边数满足 n-1 ≤ e ≤ 3n-5，其中最稠密结构由各类三角化图构成。现有结果分散，缺乏统一表达。本文以边界顶点数 m 为参数，建立简洁代数公式，实现稠密平面图的统一描述。

2 预备知识

设连通平面图 G 有 n 个顶点，e 条边，f 个面，满足欧拉公式：
n - e + f = 2。

定义（平面三角化图）：内部面均为三角形，外部面为 m 边形，2 ≤ m ≤ n。

- m = n：多边形三角剖分；
- m = 3：最大平面图；
- m = 2：外部面退化为二边形。

3 统一公式与推导

3.1 基准情形

全边界顶点 m = n，即 n 边形三角剖分：
a = n - 2，e= 2n - 3。

3.2 外弦内化构造

每次将一个边界顶点转为内部顶点，边数与三角形数各加 1，边界顶点数减 1。
共执行 k = n - m 次，得到统一公式：

a = 2n - m - 2，
e = 3n - m - 3。

4 验证与自洽性

- m = n：e = 2n - 3，多边形三角剖分；
- m = 3：e = 3n - 6，最大平面图；
- m = 2：e = 3n - 5，最密退化平面图。

将 f = a + 1 代入欧拉公式：
n - e + (a + 1) = 2，
等式恒成立，公式拓扑自洽。

5 稠密性刻画

连通平面图边数区间：[n-1，3n-5]。
当 m 从 n 降到 2 时，
e = 3n - m - 3
从 2n - 3 递增到 3n - 5，共取 n-1 个值，
恰好覆盖平面图边数最稠密的上半区间。

6 结论

本文给出平面三角化图统一公式：
e = 3n - m - 3，a = 2n - m - 2。
以单一参数 m 统一稠密平面图族，结构清晰、推导构造性强、与欧拉公式自洽。
公式精确刻画平面图稠密结构，可用于平面图计数、生成算法与极值结构研究。