NOIP 提高 2015 第一轮 第 20 题：在二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先

题目

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

答案

A、C

题解

考点定位

本题考「黑白染色=二分图判定（不定项）」,对应大纲 4.3.4 图着色（难度【3】）。

解题过程

可黑白染色 ⟺ 二分图（无奇圈）：

• 二分图 ✓（定义）；
• 完全图 ✗（K₃ 起含奇圈）；
• 树 ✓（无环必无奇圈）；
• 连通图 ✗（含奇圈的连通图不可）。

答案：A、C。

易错提醒

① 黑白染色 ⟺ 二分图 ⟺ 无奇圈；② 树是二分图的特例（按深度奇偶分层）。