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

朱明君

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

作者：朱火华
学科领域：图论与组合数学
日期：2026年3月17日

摘要

本文针对连通平面图，引入边界顶点数 m，建立平面三角化图的统一计数公式：边数 e = 3n - m - 3，内部三角形数 a = 2n - m - 2。该公式基于“外弦内化”构造法推导，统一了多边形三角剖分、最大平面图及退化稠密平面图，并与欧拉公式拓扑自洽。进一步研究表明，当边界顶点数 m 从 n 递减至 2 时，边数从 2n-3 连续递增至 3n-5，恰好覆盖连通平面图边数区间中最稠密的上半段。这一结果提供了稠密平面图结构的统一刻画，为平面图计数与极值结构研究奠定基础。

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

1 引言

连通平面图的边数满足 n-1 ≤ e ≤ 3n-5，其中最稠密的结构由各类三角化图构成。然而，现有结果（如多边形三角剖分、最大平面图等）分散于不同图类，缺乏统一的代数表达。本文以边界顶点数 m 为单一参数，建立简洁的统一公式，揭示从外平面图到最大平面图乃至退化情形的连续过渡规律，为稠密平面图的系统研究提供理论工具。

2 预备知识

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

定义（平面三角化图）
若连通平面图的所有内部面均为三角形，则称其为平面三角化图。设其外部面是一个 m 边形，m 称为边界顶点数，满足 2 ≤ m ≤ n。特别地：

- 当 m = n 时，图为简单 n 边形的三角剖分（所有顶点均在外部面上）；
- 当 m = 3 时，图为最大平面图（外部面亦为三角形）；
- 当 m = 2 时，外部面退化为二边形（由两条平行边构成）。此时允许图含有重边，内部面仍由三角形填充，这是平面三角化图在极值意义上的退化情形。

在本文中，除 m=2 的退化情形外，我们默认图是简单的（无重边、无自环）。

3 统一公式与推导

3.1 基准情形

当所有顶点位于外部面时，m = n，图即为 n 边形的三角剖分。此时：

- 内部三角形数 a= n - 2；
- 总边数 e= n + (n - 3) = 2n - 3（n 条边界边加上 n-3 条内部对角线）。

3.2 外弦内化构造

选取边界上按顺时针顺序排列的三个连续顶点 A, B, C，添加边 AC（称为外弦）。该操作将顶点 B 从边界移入内部，同时新增一个三角形 △ABC 和一条边 AC（需确保 AC 尚未存在，以保持图的简单性；当 m=2 时允许重边，此时可视为构造的极限情形）。该操作每次引起的变化：

- 边界顶点数 m 减少 1；
- 总边数 e 增加 1；
- 内部三角形数 a 增加 1。

操作的可行性：在非退化情形下，只要 m ≥ 4，边界上总存在三个连续顶点，使得连接首尾不会破坏图的平面性（因为新增边完全位于当前外部面内）。重复操作直至达到目标 m 值，构造过程始终保持图的三角化性质。

3.3 统一公式

设从基准情形出发，执行 k = n - m 次外弦内化操作，使边界顶点数降至目标值 m。叠加增量得统一公式：

a = 2n - m - 2,  (2)
e = 3n - m - 3.  (3)

公式（2）和（3）以单一参数 m 统一描述了平面三角化图的内部三角形数与边数。

4 验证与自洽性

4.1 典型情形验证

- m = n：e = 2n-3，a = n-2，对应多边形三角剖分（外平面图）。
- m = 3：e = 3n-6，a = 2n-5，对应最大平面图。
- m = 2：e = 3n-5，a = 2n-4，对应外部面为二边形的退化最密情形。

4.2 欧拉公式自洽性

平面图总面数 f = a + 1（外部面加上所有内部三角形）。将公式（2）和（3）代入欧拉公式（1）：

n - e + (a+1)
= n - (3n - m - 3) + (2n - m - 2 + 1)
= n - 3n + m + 3 + 2n - m - 1
= 2，

等式恒成立，表明公式与平面图基本拓扑定理一致。


5 稠密性刻画

连通平面图的边数取值范围为 [n-1, 3n-5]，共有 2n-3 个整数值。对于平面三角化图，当边界顶点数 m 从 n 递减至 2 时，边数

e = 3n - m - 3

从 2n-3 严格递增至 3n-5，恰好取遍区间 [2n-3, 3n-5] 内的所有 n-1 个整数值。

这一结果表明：

- 平面三角化图是连通平面图中边数最大的子类，它精确覆盖了所有可能的三角化结构，即边数不小于 2n-3 的连通平面图均可通过添加边（三角化）转化为平面三角化图。
- 从外平面图（m=n）到最大平面图（m=3）再到退化极值图（m=2），边数随内部顶点增加而线性增长：每增加一个内部顶点（即 m 减少 1），边数和三角形数各增加 1。
- 任何边数不小于 2n-3 的连通平面图均可通过连续外弦内化操作转化为三角化图，反之亦然，故三角化图构成稠密平面图的结构骨架。

因此，公式（2）和（3）不仅提供了计数工具，更揭示了稠密平面图从稀疏到极值的连续过渡规律。

6 结论

本文建立了平面三角化图的统一计数公式：

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

以边界顶点数 m 为唯一参数，统一描述了多边形三角剖分、最大平面图及退化情形。公式推导基于直观的“外弦内化”构造，与欧拉公式完全自洽。进一步分析表明，该图类精确覆盖了平面图边数区间中最稠密的上半段，揭示了稠密平面图的结构层次与增长规律。这一结果可应用于平面图计数、生成算法设计及极值结构研究，为相关领域提供基础理论支撑。

参考文献

[1] Bondy J A, Murty U S R. Graph Theory[M]. Springer, 2008.
[2] Diestel R. Graph Theory[M]. 5th ed. Springer, 2017.
[3] Tutte W T. A census of planar triangulations[J]. Canadian Journal of Mathematics, 1962, 14: 21–38.
[4] 徐俊明. 图论及其应用[M]. 第3版. 中国科学技术大学出版社, 2010.