一个正方形被剖分为4个正方形，剖分图的边数为12，若一个正方形被剖分为2005个凸多边形，试求剖分图中边数的最大值。

Question

一个正方形被剖分为 4 个正方形，剖分图的边数为 12 ，若一个正方形被剖分为 2005 个凸多边形，试求剖分图中边数的最大值。

Answer 1

解析：由欧拉定理可知，简单多面体的顶点数 ，面数 ，棱数 有关系：

由欧拉定理容易看出，若一个凸多边形被剖分为 个凸多边形，则剖分图中的顶点数 ，多边形数 ，边数 有关系：                                （ 1 ）

下面在一般的情况下，即正方形被剖分为 个凸多边形时，求剖分图中边数的最大值，设剖分图中的顶点数为 ，多边形数为 ，边数为

（一）先求边数的上界

设原正方形的 4 个顶点是 ，若凸多边形的顶点 V 则易知

≥ （这里用 表示通过顶点 的边数），于是有   ≤

这样的顶点 有 个，于是有 个上面的不等式，将它们相加求和，并注意到除去正方形四边的每条边恰是两个凸多边形的边，有

≤

即有 ≥

因为 ≥ ， ≥ ， ≥ ， ≥ ，

所以 ≥                               （ 2 ）

由公式（ 1 ），有

，

                              （ 3 ）

将（ 2 ）式代入（ 3 ）式，并整理有

≤

≤                                        （ 4 ）

（二）构造例子，使边数

过正方形的一边相继作 条邻边的平行线，正方形被剖分为 个矩形，

易知，边数

               

综合两方面，剖分图中边数的最大值为 ，所以正方形剖分为 个凸多边形的边数最大值为

作业帮用户 2017-01-20