小地图涂色:相邻区域不同色
为具体小地图构造少色方案并证明两色不足。
视频暂时无法加载。请检查网络后重试,或直接下载视频。
下载视频
展开视频文字稿
- 三个区域甲、乙、丙两两共享一段边。相邻区域必须使用不同颜色,问最少几色。
- 先给甲红色。乙和甲相邻,所以乙不能红,只能先用第二种蓝色。
- 丙同时和甲、乙共享边,它既不能用红色,也不能用蓝色。
- 因此两种颜色一定会在丙这里冲突,必须给丙第三种颜色,例如黄色。
- 红、蓝、黄的方案让三对相邻区域都不同色,所以三色既够用,也是下限。
- 答案是三色。只在一个点上碰到不算相邻;这里三对区域都共享一段边。
逻辑思维
下界与构造,并用反向检查确认。
看一个例子
三个区域A、B、C两两共享边,最少用几种颜色使相邻不同?
3种。给A红B蓝C黄,三对邻接均异色。
马上试一题
第三个区域同时邻前两色,需第三色。