染色问题

染色问题是指用一定数量的颜色给图形中的区域或点涂色，要求相邻（有公共边或边相连）的区域或点颜色不同，计算所有可能的涂色方案数。

- 先确定图形结构，明确哪些是相邻关系。 - 通常从某个区域或点开始，依次考虑每个位置的颜色选择。 - 注意首尾是否相连，若构成环形，需要特殊处理相邻关系。 - 可以使用“先不考虑首尾限制，再减去首尾相同的情况”的补集方法。

对于用m种颜色给n个区域（或点）环形染色（相邻不同），方法数为 (m-1)^n + (-1)^n × (m-1)。无固定公式时，掌握分类讨论和补集思想。

- 容易忘记检查首尾是否相邻，尤其是环形图形。 - 在“先不考虑首尾”的方法中，容易重复计算或漏算首尾相同的情况。 - 分类讨论时，要注意每个位置与前后位置的关系，不要遗漏约束。

竞赛难度下，染色问题常与环形、递推、分类讨论结合，需要灵活运用补集思想或公式，不能直接套用简单乘法。重点考察学生的逻辑推理能力和对相邻关系的敏感度。

用红、黄、蓝三种颜色给一个正五边形的五个顶点（A、B、C、D、E按顺时针排列）染色，要求相邻顶点（即五边形的边连接的两个顶点）颜色不同，一共有多少种不同的染色方法？

本题是典型的环形染色问题，五个顶点围成一圈，相邻顶点不能同色。可以先假设五边形是一条直线（不考虑首尾相连），算出所有染色数，再减去首尾（A和E）颜色相同的情况。注意在计算首尾相同时，要确保其他相邻关系也满足。

1. 先考虑如果不限制A和E是否相同，只要求相邻顶点（即A与B、B与C、C与D、D与E）颜色不同。那么可以从A开始染色： - A有3种颜色可选。 - B不能与A同色，有2种颜色可选。 - C不能与B同色，有2种可选。 - D不能与C同色，有2种可选。 - E不能与D同色，有2种可选。 因此总方案数为：3 × 2 × 2 × 2 × 2 = 48（种）。 2. 但上述48种中包含了A与E同色的情况，而题目要求A与E也不能同色（因为A和E也是相邻的），所以需要去掉A与E同色的所有方案。 3. 下面计算A与E同色时的方案数。 - 第一步：A有3种颜色可选。 - 因为A与E同色，所以E的颜色与A相同，固定。 - 现在考虑B、C、D的染色，它们满足： * B不能与A同色（因为相邻），有2种可选。 * C不能与B同色，有2种可选。 * D不能与C同色，有2种可选。 另外，D还与E相邻，而E与A同色，所以D也不能与A同色。 因此D需要同时满足：D ≠ C 且 D ≠ A。 - 我们先不管D≠A的限制，B、C、D的初步可选为：B有2种，C有2种，D有2种，共2×2×2=8种（对于固定的A颜色）。 - 但这8种中，有些D的颜色恰好等于A（即D与A同色），需要去掉。 - 计算D等于A的情况：当D = A时，此时C不能等于D（即不能等于A），且C不能等于B，所以C只能从剩下的1种颜色中选（因为B≠A，B有2种选择，但C只要不等于B且不等于A即可，若B取某色，则C只能取剩下的唯一一种颜色）。另外B本身有2种选择（除了A以外的两种）。所以满足D=A的方案数为：B有2种，C有1种，D固定为A，共2×1=2种。 - 因此，满足D≠A的方案数为：8 - 2 = 6种（对于固定的A颜色）。 - A有3种颜色可选，所以A与E同色的总方案数为：3 × 6 = 18（种）。 4. 所以，满足所有相邻顶点（包括A与E）颜色不同的方案数为：48 - 18 = 30（种）。

30种

对于环形染色问题，可以先用线性排列（不考虑首尾相邻）求出总数，再减去首尾相同的情况。在计算首尾相同时，要特别注意中间区域与首尾的约束，通过分类讨论或列举准确求出。此方法可以推广到任意m种颜色、n个顶点的环形染色问题。