数学大学
C. Fisk's Proof
计算几何 · 03. Triangulation
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
C. Fisk's Proof
计算几何 · 03. Triangulation
Domination
支配（domination）：一种颜色的顶点能「看见」整个三角剖分——守卫的数学化。
支配集
选中颜色类的顶点覆盖所有三角形
守卫对应
支配集的顶点即守卫的驻扎位置
Pigeon-Hole Principle
鸽巢原理收尾：n 个顶点染三色，最少的一类至多 ⌊n/3⌋ 个。
三染色
剖分后对顶点做 3-着色
抽屉论证
三类均分则每类恰约 n/3
Generalization
推广：移动守卫、正交多边形、带洞情形——Fisk 证明是众多变体的起点。
移动守卫
守卫可沿边巡逻时守卫数可减半
正交多边形
直角多边形只需 ⌊n/4⌋ 个垂直视守卫
本节要点
- ✓Fisk 证明：三角剖分 + 三染色 + 鸽巢
- ✓最小色类即支配集 = 守卫位置
- ✓变体（正交、带洞）有各自的界
延伸主题：手染一次三角剖分了解正交多边形的 ⌊n/4⌋ 界
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1为什么三角剖分后的图一定能 3-着色？
参考答案多边形的三角剖分图是外平面图（所有顶点在同一个外圈上），外平面图必可 3-着色：沿对角线逐个添加三角形，每新增一个顶点时其两个相邻顶点已用掉两种颜色，只剩第三种可用。
2为什么选中色的守卫能看住整个画廊？
参考答案三角剖分把画廊切成若干三角形，每个三角形三个顶点三色俱全；守卫驻在选中色的顶点上，位于每个三角形的某个顶点处，而三角形内部任何位置都能从其顶点直视——整屋全覆盖。
3三染色失败时（某些剖分不可三染色）怎么办？
参考答案简单多边形的任何三角剖分都可三染色（Fisk 定理保证），所以对无洞多边形不会失败。带洞多边形才需要改用四染色或近似方法。