培玉 · 一试
一试训练题
F2填空题经典的计数模型
给图中等6个区域进行染色，每个区域只染1种颜色，且相邻的区域不同色。若有4种颜色可供选择，则共有种不同的染色方案。
作答
分数写 a/b，根号写 √ 或 sqrt，π 写 pi 也可以。
标准答案：
解析
提示
先读清内圈和外圈各自的邻接关系，优先给彼此两两相邻的三区着色。
思路
固定这三色后，每个外区的允许色列表很短；再用外区之间的邻接条件判断第四色能出现几次。
解答
内部两两相邻，染成三色有种。不妨颜色分别为1、2、3，第四色为4。由图邻，故只能为2或4；邻，只能为3或4；邻，只能为1或4。外侧也两两相邻，故4至多用一次：均不选4有1种，恰一个选4有3种，共4种。答案。
复核
若实际上只使用三色，外圈对应内圈的三个可用色都被确定，先选三色调色板并排列内圈，共 种。恰用四色的72种与它们合计为96。把第四色同时放到任意两个外区会违反外圈相邻条件，不能按三个二选一直接算成8种。
方法总结
图形染色可先固定一个小团，使其他顶点得到明确的允许色列表。列表选择并非彼此独立，还要施加剩余顶点之间的边；尤其同一个新颜色的重复使用可能被后续邻接禁止。
为什么评为 F2（会透露解法方向）
需识别并应用内外三角形；局部列表染色模型
已记下，谢谢！