NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 20 题

以下图中一定可以进行黑白染色的有（ ）。（黑白染色：为各个结点分别指定黑白两种颜色之一，使相邻结点颜色不同。）

拿到黑白染色题，别急着画，先想本质：这其实就是判断图里有没有奇数长度的环。没有奇环，就能像下棋一样黑白相间；一有奇环，两边颜色就打架了。所以思路就一条：把图拆成‘全是偶环’和‘混有奇环’两类，看选项属于哪一类。

最容易把‘二分图’和‘连通图’搞混。二分图定义就是不含奇环，所以一定可染色；但连通图只要求所有点能走到一起，它完全可以包含一个三角形（K3），这种图就不行。另一个坑是看到树就以为所有树都行，其实树只是二分图的一个特例，结论没错，但别把‘树’和‘二分图’当成两个并列的大类去记，容易在多选题里把树漏掉或者把非树的二分图误判。

考点概念：二分图与两色染色

能用黑白两色给所有结点染色且相邻颜色不同，等价于该图是二分图。二分图的核心判定条件只有一个：图中不存在奇数长度的环。只要没有奇环，就能把点分成两个集合，集合内无边，集合间全连，从而完成染色；一旦存在奇环，染色必然冲突。

命题视角：为什么考这个

命题人喜欢用‘黑白染色’这种生活化描述来考二分图，因为直观、好记，但容易让人只盯着‘二分图’这个名词，忽略背后的奇环本质。在选择题里，他们常把‘二分图’‘树’‘连通图’‘完全图’混在一起，让你判断哪些‘一定’可染色。这里的‘一定’是关键词——只要存在反例（哪怕只有一种特殊情况），选项就不成立。