二分图、匹配、平面图与着色入门

图论的一个好用之处，是它能把现实问题里的“能不能配对”“能不能画清楚”“能不能避开冲突”变成点和边的问题。人员能做哪些任务，是二分图；一门课和另一门课不能同一时段考试，是冲突图；几个区域相邻不能同色，是图着色；一张网络图能不能在纸面上画得没有交叉，是平面图。

本章不追求把匹配、平面图和着色的完整理论一次讲完。我们先建立足够清楚的入口：看懂模型、说准定义、会做小规模判断，并能把这些语言用到任务分配、排课、地图着色和冲突约束中。

学习目标

学完本章，你应该能够：

判断一个图是否可以看成二分图，并解释“两边交替”的直觉。
识别匹配、最大匹配、完美匹配，并用小图寻找较大的匹配。
用 Hall 条件的直觉发现“某组人选择太少”的瓶颈。
区分“当前画法有交叉”和“这个图不是平面图”。
在连通平面图中正确数顶点、边和面，并使用欧拉公式。
把地图着色、排课、资源分配写成图着色或冲突图问题。

本章的几个主题看起来分散，其实都在问同一类问题：给定一组限制，能否为对象安排位置、伙伴、颜色或时间，使相互冲突的对象不撞在一起。

二分图：把对象分成两边

一个图是二分图，意思是它的顶点可以分成两个集合，通常记作左部和右部，使得每条边都连接左部的一个顶点和右部的一个顶点。左部内部没有边，右部内部也没有边。

如果用 $G=(V,E)$ 表示图，二分图就是存在两个不相交集合 $L$ 和 $R$ ，满足：

V=L\cup R,\quad L\cap R=\varnothing

并且每条边的一端在 $L$ ，另一端在 $R$ 。

二分图示意图：左部人员节点与右部任务节点之间只跨组连接，旁边反例展示同组边不允许。

二分图将顶点分成左部和右部，边只能连接不同部分的顶点；同组顶点之间不能有边。

常见模型

二分图适合描述“两类对象之间的可行关系”。例如：

左边是学生，右边是项目，边表示某个学生愿意做某个项目。
左边是工人，右边是班次，边表示某个工人能上某个班次。
左边是课程，右边是教室，边表示某门课能安排在某间教室。
左边是用户，右边是商品，边表示用户对商品有过互动。

这里的关键不是对象叫什么，而是关系是否只发生在两类对象之间。如果同一类对象之间也要连边，通常就不是这个二分图模型，或者需要重新定义顶点类型。

用两种颜色检查二分性

一个实用判断方法是给图的顶点交替染两种颜色。任选一个顶点染成蓝色，它的邻居染成绿色，邻居的邻居再染成蓝色。只要某条边的两端被迫染成同一种颜色，就说明这张图不能二分。

这个方法背后的直觉是：二分图中的路径会在左部和右部之间来回跳。长度为奇数的回路会让最后一步回到起点时颜色对不上，所以有奇数长度回路的图不能二分。反过来，如果没有奇数回路，就可以按距离奇偶给每个连通分量分两边。

二分图的左右两边不是由画面左右决定的，而是由顶点能否被分成两组决定的。同一张二分图可以被画成很多样子；只要存在一种合法分组，它就是二分图。

匹配：不重复使用端点的配对

在图中，匹配是一组选出的边，要求任意两条被选中的边都没有公共端点。放在二分图里看，就是每个人最多分到一个任务，每个任务也最多分给一个人。

如果一个顶点碰到了某条匹配边，就说这个顶点被匹配；否则它是未匹配顶点。匹配中边的条数叫匹配大小。最大匹配是边数尽可能多的匹配。完美匹配则更强：每个顶点都被匹配。

二分图匹配与增广路径示意图，蓝色粗线表示已选匹配边，橙色虚线路径表示从未匹配人员到未匹配任务的可替换路径。

匹配与增广路径：沿交替路径替换，可使匹配数增加 1。

为什么增广路径有用

假设我们已经选了一些匹配边。若能找到一条从未匹配左部顶点出发、到未匹配右部顶点结束的路径，并且这条路径上的边在“未选、已选、未选、已选……”之间交替出现，那么这条路径叫增广路径。

沿着这条路径做一次替换：把原来没选的边选上，把原来选上的边取消。由于路径两端都是未匹配顶点，替换后匹配边数会增加 $1$ 。

对小图来说，找更大匹配时不要只盯着单条边。先看有没有从未匹配点到未匹配点的交替路径；一旦找到，沿路径翻转就能改进当前匹配。

交互：尝试形成匹配

下面的交互工具把“每个端点最多用一次”做成了即时检查。你可以点选人员与任务之间的边，观察什么时候选择仍是匹配，什么时候出现重复使用端点。

例题：为三名助教安排三项任务

有三名助教 $A,B,C$ 和三项任务 $1,2,3$ 。可行关系如下：

$A$ 能做 $1$ 或 $2$ ；
$B$ 能做 $2$ ；
$C$ 能做 $2$ 或 $3$ 。

问：能否给每名助教安排一个不同任务？

先把问题画成二分图。左部是助教 $A,B,C$ ，右部是任务 $1,2,3$ 。一条边表示“这名助教能做这项任务”。

观察限制最强的顶点。 $B$ 只能做任务 $2$ ，所以若想所有人都被安排， $B$ 必须匹配到 $2$ 。

$A$ 还可以做任务 $1$ ， $C$ 还可以做任务 $3$ 。于是选择边 $A1$ 、 $B2$ 、 $C3$ 。

这三条边没有公共端点，覆盖了所有助教，也覆盖了所有任务，所以这是一个完美匹配。

Hall 定理的直觉：瓶颈集合

在人员与任务数量相同的二分图中，我们常问：能不能让每个人都匹配到不同任务？Hall 定理给出了准确条件。设 $S$ 是左部中的任意一组顶点， $N(S)$ 表示这组顶点在右部能连接到的所有邻居。若存在覆盖左部的匹配，就必须对每个 $S$ 都有：

\lvert N(S)\rvert \ge \lvert S\rvert

这句话很朴素：任意一组人合起来能选择的任务数，不能少于这组人的人数。否则即使其他地方再宽松，这组人内部也必定有人没任务。

用二分图展示霍尔条件的瓶颈集合：三位申请者只连接到两个可选岗位，因此可选岗位数少于这组人数。

瓶颈集合说明 Hall 条件：当某组人的可选岗位少于这组人数时，无法为每个人匹配不同岗位。

不做完整证明，但要会用

Hall 定理的完整证明需要更细的匹配论证，本章只使用它的判断思路。遇到“能否每人一个不同选择”的问题时，可以先找瓶颈集合：

是否有两个人都只能选同一个岗位？
是否有三门课都只能安排在两间教室？
是否有一组学生的可选项目合起来太少？

如果找到了这样的集合，就能立刻说明完美匹配不存在。如果所有集合都满足 Hall 条件，则完美匹配存在；这是定理的强结论。

Hall 条件不是只检查单个人，也不是只检查全体人。它要求检查左部的每一个子集。实际解题时，我们通常先找最可能拥挤的那几组，而不是机械列出所有子集。

练习：左部为 $a,b,c$ ，右部为 $1,2,3$ 。边为 $a1,a2,b1,b2,c2$ 。是否存在覆盖左部的匹配？

平面图：能否画成没有交叉

一张图是平面图，意思是它可以画在平面上，使得边只在公共端点处相交。这里要注意“可以画成”这几个字。某个画法有交叉，不代表这个图不是平面图；也许换一种摆放方式，交叉就消失了。

同一个四顶点六边图的交叉画法与重新画成无交叉平面画法的对比图

同一个图可以通过重新画变成没有边交叉的平面画法，顶点和边未改变。

图和画法的区别

图由顶点和边决定，画法只是把它放到纸面上的一种方式。对平面图来说，我们关心的是是否存在一种没有交叉的画法。画好之后，边把平面分成若干区域，这些区域叫面。最外面的无界区域也算一个面。

如果一个图无论怎么重画都有边交叉，它就不是平面图。经典的两个非平面图是 $K_5$ 和 $K_{3,3}$ 。本章不证明这两个结论，但要记住它们常作为判断非平面性的入口。

边相交的地方如果不是原图中的顶点，就不能把交点临时当成新顶点来数。平面图要求边只在原本共享的端点相交。

欧拉公式：顶点、边、面之间的平衡

对连通平面图，如果某个没有交叉的画法有 $V$ 个顶点、 $E$ 条边、 $F$ 个面，那么：

V-E+F=2

这就是欧拉公式。它不是在说每张图都有两个面，也不是说顶点、边、面可以随便数；它说的是连通平面图的三个计数之间有固定平衡。

欧拉公式 V - E + F = 2 的中文教学信息图，展示平面图中的顶点、边、面和外面。

欧拉公式的计数对象：顶点 V、边 E、面 F，其中外部无界区域也算作一个面。

一个直觉证明

从一棵树开始看最容易。一棵连通树没有回路，所以它只有一个面，也就是外面。树有 $E=V-1$ ，因此：

V-E+F=V-(V-1)+1=2

如果在平面画法里加一条不交叉的边，并且这条边连接已经存在的两个顶点，它会把某个面切成两个面。于是 $E$ 增加 $1$ ， $F$ 也增加 $1$ ， $V-E+F$ 不变。许多连通平面图可以看成从生成树开始逐步加边得到，所以这个值一直保持为 $2$ 。

交互：观察欧拉公式

下面的工具让你切换几个连通平面图，并观察添加或删除不交叉边时 $V$ 、 $E$ 、 $F$ 的变化。特别留意外部区域也算一个面。

用欧拉公式排除非平面图

对简单连通平面图，若 $V\ge 3$ ，每个面至少由三条边围成。数所有面的边界时，每条边最多被数两次，所以可得到常用不等式：

E\le 3V-6

例如 $K_5$ 有 $V=5$ 、 $E=10$ 。如果它是平面图，就应有：

10\le 3\cdot 5-6=9

这不可能，所以 $K_5$ 不是平面图。

对于没有三角形的简单连通平面图，每个面至少由四条边围成，可以得到更强的不等式：

E\le 2V-4

$K_{3,3}$ 是二分图，没有三角形。它有 $V=6$ 、 $E=9$ 。若它是平面图，就应有 $9\le 2\cdot 6-4=8$ ，矛盾。因此 $K_{3,3}$ 不是平面图。

练习：一个连通平面图有 $8$ 个顶点、 $11$ 条边。它有几个面？

图着色：把冲突变成相邻不能同色

图着色是给图的每个顶点分配颜色，使得相邻顶点颜色不同。若能用 $k$ 种颜色完成，就说这个图是 $k$ 可着色的。最少需要的颜色数叫色数，常记作 $\chi(G)$ 。

着色听起来像画图，实质是资源分配。颜色可以代表考试时段、无线频道、寄存器、会议室批次或地图颜色。边表示冲突：两端不能拿同一种资源。

图着色用于排课的中文信息图，左侧展示课程冲突图，右侧展示三个时段的分配结果。

图着色把相互冲突的课程分配到不同颜色或时段中，用于说明排课中的冲突约束。

地图着色

地图着色可以这样建模：每个区域变成一个顶点，如果两个区域共享一段边界，就在对应顶点之间连边。给地图上色，就是给这个冲突图上色。共享一点角落通常不算相邻，因为它不会形成一整段边界冲突。

平面图和地图着色之间有很深的联系。四色定理说明，每张平面地图都可以用不超过四种颜色染色，使相邻区域颜色不同。这个定理的证明很长，本课程只把它当作背景事实，不把它作为证明训练目标。

排课冲突图

排课也可以变成着色问题。把每门考试看成一个顶点。如果两门考试有学生重叠，就连一条边。给顶点染颜色，就是给考试安排时段。相邻顶点不能同色，表示有共同学生的两门考试不能同一时段。

贪心着色的作用和局限

一个简单办法是按某个顺序处理顶点：轮到一个顶点时，给它分配当前可用的最小颜色，避开已经染色的邻居。这个方法叫贪心着色。

贪心着色很快，也常能给出不错方案。但它不保证用最少颜色，因为顶点顺序会影响结果。同一张图，换一个处理顺序，可能使用不同数量的颜色。

“我找到一种用 4 色的方案”只能说明这个图至多需要 4 色，不能说明它至少需要 4 色。要证明“必须用 4 色”，还要说明任何 3 色方案都会失败。

综合建模：从限制到图

遇到现实问题时，先不要急着套定理。更可靠的做法是把对象、关系和目标分开。

明确顶点代表什么。若顶点是人员和任务两类对象，问题可能走向二分图；若顶点是课程、区域或事件，问题可能走向冲突图。

明确边代表什么。边可以表示“可以配对”，也可以表示“不能同时发生”。这两种含义方向相反，建模时不能混用。

明确目标是什么。想让每个人分到任务，是匹配问题；想用尽量少的时段避开冲突，是着色问题；想分析画法和区域，是平面图问题。

最后选择工具。匹配看端点是否重复，Hall 条件看瓶颈集合，平面图看是否存在无交叉画法，着色看相邻顶点是否同色。

模型选择对照

场景	顶点	边表示	目标
人员分配任务	人员与任务	可以承担	找大匹配或完美匹配
学生选择项目	学生与项目	愿意选择	检查是否每人一个项目
地铁线路示意图	站点	线路连接	判断画法、区域或连通结构
地图染色	区域	共享边界	相邻区域不同色
考试排课	课程	有学生冲突	相邻课程不同时间

同一个现实问题有时能建出不同的图。关键是让边的含义和目标一致：可行关系通常适合匹配；冲突关系通常适合着色。

自测练习

练习 1：一个三角形图是否是二分图？

练习 2：在一个二分图中，左部有 $4$ 个顶点，右部有 $4$ 个顶点。如果某三个左部顶点的邻居合起来只有两个右部顶点，能否存在覆盖左部的匹配？

练习 3：一个连通平面图有 $6$ 个顶点、 $9$ 条边。它有几个面？

练习 4：若一个简单图有 $5$ 个顶点和 $10$ 条边，它能是平面图吗？

练习 5：某考试冲突图中有三门课程两两冲突。至少需要几个考试时段？

本章小结

二分图把两类对象之间的可行关系分开，匹配从中选择互不抢端点的边。Hall 条件提醒我们检查瓶颈集合：一组对象的可选对象数不能少于这组对象本身。

平面图关注的是是否存在无交叉画法，而不是当前画法是否交叉。对连通平面图，欧拉公式 $V-E+F=2$ 把顶点、边、面连在一起，也能给出判断非平面图的简单工具。

图着色把“相邻不能同色”变成资源分配语言。地图着色、考试排课、频道分配和冲突约束都可以用同一套图语言表达。学会选择模型，比记住某个孤立公式更重要。