第二十六课简单染色问题

有很多同学喜欢画画，有的喜欢画人物，有的喜欢画花草，有的喜欢画水彩画，有的喜欢画油画．有一些画靠优美的线条取胜，也有一些画以绚丽的色彩夺目．然而很少有人知道在数学问题中也有一些与色彩有关．这就是所谓的“染色问题”．在这一课我们就介绍一些简单的染色问题．

例 1 如图 26—1 所示，用五种不同的颜色分别使 A、B、C、D、E 染色，要求相邻两区域所染的颜色不同，求共有多少种不同的染色方式？

第二十六课简单染色问题 - 图1

分析首先我们设定一种染色顺序，不妨假定按 A、B、C、D、E 的顺序．

由于 A 与 D 不相邻，则 A 与 D 的颜色可以相同，也可以不同．

若 A 与 D 颜色相同，则此时，A 有 5 种染色方式，B 不能与 A 同色，故只有 4 种染色方式，而 C 不能与 AB 同色，故只有 3 种染色方式， E 不能与 A、C 同色，即也有 3 种染色方式，由乘法原理，共有 5×4×3

×3=180 种不同的染色方式．

若 A 与 D 颜色不同时，A 还是 5 种染色方式，B 还是 4 种染色方式，C 还是 3 种染色方式，而 D 此时与 A、B、C 的颜色都不同，所以只有 2 种染色方式，E 不能与 A、C、D 同色，即也有 2 种染色方式，由乘法原理，共有 5×4×3×2×2=240 种不同的染色方式．

解由以上分析，共有不同的染色方式5×4×3×3＋5×4×3×2×2

=180＋240=420（种）

例 2 有一个 5×5 的方格棋盘，如图 26—2 所示每一个小方格中有一只小甲虫，假定在同一时刻，所有小甲虫都爬到邻格中（横向与纵向的格，不能斜爬），问此时能否会出现空格？

第二十六课简单染色问题 - 图2

分析初看这个问题，似乎无从下手，但如果我们利用“染色”的手段，就会使问题简化，很轻松的得到正确答案．

解将 5×5 棋盘用黑白两种颜色相间染色，如图 26—3 所示，此时

共有黑色格 13 个，白色格 12 个．当每个小格中的甲虫同时爬向邻格时，即黑格中的甲虫爬到白格中，白格中的甲虫爬到黑格中．由于黑格比白格多一格，则原来白格中的甲虫爬到黑格后必空一格，所以该题的答案是肯定的．

第二十六课简单染色问题 - 图3

例 3 至少需要几种颜色才能使图 26—4 中所有有公共端点的线段涂上不同的颜色？

第二十六课简单染色问题 - 图4

分析由于 AD、AB、AE 共点于 A，所以需要 3 种颜色对这三条线段染色．由于 BE 与 AD 不相邻，CD 与 AE 不相邻．CE 与 AB 不相邻，因此它们可以分别染上相同的颜色．这样 BC 不能再与 BE、CE、CD 中的任一条同色，它应染上另一种颜色．解由以上分析可知，至少需要 4 种颜色才能使图中所有相邻的线段涂上不同的颜色．

例 4 马能否从半个棋盘上的任一点出发，不重不漏地跳遍半个棋盘的所有点？

分析由马走“日”的特点，我们将半个棋盘上的所有点进行红黑两种染色，即相邻的点染上不同的颜色（如图 26—5）．设 A 点一类为黑点，相邻点则为红点．不难看出，马每跳一步都是从一种色点到另一种色点．即马在连续跳动时，两种颜色的点交错出现．如果马能不重不漏地跳遍半个棋盘，则两种颜色点的个数应当相同或马的起跳点所在的一类色点多一个．

第二十六课简单染色问题 - 图5