【名题赏析】3.3 三角形剖分、画廊问题和卡特兰数（3）
解名题，学数学！...
今天跟大家一起解决画廊问题。没看过前两节的请移步：
【名题赏析】3.1 三角形剖分（1）
【名题赏析】3.2 三角形剖分（2）
猜测答案
画廊问题（Art Gallery Problem）：
一个展览馆画廊的墙形成一个 n 边多边形（可凸可凹）。保安位于画廊内某些固定位置。假设保安能转头，但不能走动（即静态保安，摄像头），为了保证每寸墙都能被保安看到，最少需要多少保安（考虑最坏的情况）？
n=6，G=2
n=19，G=6
n=21，G=7
猜测一下，答案应该是多边形边数除以 3 取整。而所谓最坏的情况，即如上图所示的含有很多 “ 尖刺 ” 的多边形，看起来比一般的多边形需要更多保安。
（注：将一个数取整指求不超过该数的最大整数。准确的说，此处取整是下取整，即 floor function）
顶点染色：颜色
由上节，任意多边形都可以三角形剖分。现规定：剖分后，多边形的顶点若在同一个三角形，则称这些顶点是相邻的。点 P、Q 相邻，点 P、R 不相邻
顶点染色：方法
（注：顶点染色方案用强归纳法比较容易解释。由于初中阶段大部分学生没有学习过数学归纳法，故此处选用逆向思维的方式进行说明，丧失了一些严谨性，特此说明！）
记住，现在要说明：如何用三种颜色对多边形的顶点进行染色，可使得相邻顶点的颜色相异？
首先，利用对角线对多边形进行剖分，再用三种颜色（红、黄、蓝）对所有单个三角形的顶点进行染色，保证每个三角形三个顶点的颜色相异。
然后，把多边形剖分的过程反过来 —— 将三角形逐步拼接成原来的多边形。不过，这次要特别注意颜色，即在拼接过程中，要保证拼接的顶点颜色完全一致。
如果出现拼接的顶点颜色不一致的情况，把其中一个多边形的顶点颜色进行适当调换即可（一定能调换成功！）。下面三幅图说明了这个过程：
拼接处的顶点颜色不匹配，不能拼接
对其中一个多边形的顶点颜色进行了调换
拼接处的顶点颜色匹配后，再进行拼接！
解决画廊问题
由前述，可用三种颜色对多边形的顶点进行染色，使得剖分后的每个三角形，其顶点颜色都不同。
三种颜色的顶点中，数量最小的顶点数一定不超过 [ n /3 ] 个 ，若不然，则每种颜色的顶点数都大于[ n /3 ] 个，即至少 （[ n /3 ] +1 ）个，这会使得多边形的总顶点数超过 n。
这样，只需把保安放置在数量最少的颜色的顶点上，就可以看守住多边形画廊 —— 因为所有剖分得到的三角形都有这种颜色的顶点，而顶点处的保安一定可以看守住该三角形。
故，不管多边形画廊形状如何，[ n /3 ] 个保安的都已足够。这就是画廊问题的解答。
画廊问题的解答是优美的，利用三角形的剖分和多边形顶点染色，巧妙的放置静态保安的位置，保证了画廊的安全。
数学家还研究了大量与之相关的问题。例如：改变画廊的形状，改变保安的限制后需要保安的数量，通过计算机进行多边形剖分的算法优劣和速度等等。
最坏的情形
由最开始的分析知，构造 “ 尖刺 ” 尽可能多的多边形画廊即可，我们可以构造出 “ 梳子形 ” 画廊，此时必须要有[ n /3 ]个 静态保安才能看守全部区域。
关注 初中理科班数学
微信扫一扫关注公众号
