每日一题[1679]剖分

n 边形及 n3 条在 n 边形内不相交的对角线组成的图形称为一个剖分图.求证:当且仅当 3n 时,存在一个剖分图是可以一笔划的圈(即可以从一个顶点出发,经过图中各线段恰一次,最后回到出发点).

解析

因为 n3 条在形内互不相交的对角线将凸 n 边形分为 n2 个顶点均是 n 边形顶点的小区域,每个区域的内角和不小于 πn 边形的内角和为 (n2)π,所以每个小区域都是三角形.

必要性     用归纳法容易证明可将每个三角形区域涂成白蓝两色之一,使得有公共边的三角形不同色.假设已按照这样的要求染色,由于剖分图为可以一笔画的圈,所以由每个顶点引出的线段都是偶数条.从而每个顶点都是奇数个三角形的顶点,因此以原多边形外边界为一边的三角形区域有着相同的颜色,不妨设为白色;另一方面,剖分图的每条对角线都是两种不同颜色三角形的公共边,所以设白三角形有 m1 个,蓝三角形有 m2 个,则n=3m13m23n.

充分性    设 n=3m,多边形为 A1A2A3m,连接 3m3 条对接线,形成 m1 个三角形 A1A3iA3i+2i=1,2,,m1),然后由 A1 出发,依次走过这些三角形,再走过凸多边形的外边界即可一笔画并回到初始点 A1,命题得证.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复