Question

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

Answer 1

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

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

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

（一）先求边数的上界

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

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

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

≤

即有 ≥

因为 ≥，≥，≥，≥，

所以 ≥                              （2）

由公式（1），有

，

                              （3）

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

≤

≤                                       （4）

 

（二）构造例子，使边数

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

 

易知，边数

               

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