二分图、匹配、平面图与着色入门
图论的一个好用之处，是它能把现实问题里的“能不能配对”“能不能画清楚”“能不能避开冲突”变成点和边的问题。人员能做哪些任务，是二分图；一门课和另一门课不能同一时段考试，是冲突图；几个区域相邻不能同色，是图着色；一张网络图能不能在纸面上画得没有交叉，是平面图。
本章不追求把匹配、平面图和着色的完整理论一次讲完。我们先建立足够清楚的入口：看懂模型、说准定义、会做小规模判断，并能把这些语言用到任务分配、排课、地图着色和冲突约束中。
学习目标
学完本章，你应该能够：
- 判断一个图是否可以看成二分图，并解释“两边交替”的直觉。
- 识别匹配、最大匹配、完美匹配，并用小图寻找较大的匹配。
- 用 Hall 条件的直觉发现“某组人选择太少”的瓶颈。
- 区分“当前画法有交叉”和“这个图不是平面图”。
- 在连通平面图中正确数顶点、边和面，并使用欧拉公式。
- 把地图着色、排课、资源分配写成图着色或冲突图问题。
本章的几个主题看起来分散，其实都在问同一类问题：给定一组限制，能否为对象安排位置、伙伴、颜色或时间，使相互冲突的对象不撞在一起。
二分图：把对象分成两边
一个图是二分图，意思是它的顶点可以分成两个集合，通常记作左部和右部，使得每条边都连接左部的一个顶点和右部的一个顶点。左部内部没有边，右部内部也没有边。
如果用 表示图，二分图就是存在两个不相交集合 和 ，满足：
并且每条边的一端在 ，另一端在 。
二分图将顶点分成左部和右部，边只能连接不同部分的顶点；同组顶点之间不能有边。
常见模型
二分图适合描述“两类对象之间的可行关系”。例如：
- 左边是学生，右边是项目，边表示某个学生愿意做某个项目。
- 左边是工人，右边是班次，边表示某个工人能上某个班次。
- 左边是课程，右边是教室，边表示某门课能安排在某间教室。
- 左边是用户，右边是商品，边表示用户对商品有过互动。
这里的关键不是对象叫什么，而是关系是否只发生在两类对象之间。如果同一类对象之间也要连边，通常就不是这个二分图模型，或者需要重新定义顶点类型。
用两种颜色检查二分性
一个实用判断方法是给图的顶点交替染两种颜色。任选一个顶点染成蓝色，它的邻居染成绿色，邻居的邻居再染成蓝色。只要某条边的两端被迫染成同一种颜色，就说明这张图不能二分。
这个方法背后的直觉是：二分图中的路径会在左部和右部之间来回跳。长度为奇数的回路会让最后一步回到起点时颜色对不上，所以有奇数长度回路的图不能二分。反过来，如果没有奇数回路，就可以按距离奇偶给每个连通分量分两边。
二分图的左右两边不是由画面左右决定的，而是由顶点能否被分成两组决定的。同一张二分图可以被画成很多样子；只要存在一种合法分组，它就是二分图。
匹配：不重复使用端点的配对
在图中，匹配是一组选出的边，要求任意两条被选中的边都没有公共端点。放在二分图里看，就是每个人最多分到一个任务，每个任务也最多分给一个人。
如果一个顶点碰到了某条匹配边，就说这个顶点被匹配；否则它是未匹配顶点。匹配中边的条数叫匹配大小。最大匹配是边数尽可能多的匹配。完美匹配则更强：每个顶点都被匹配。
匹配与增广路径：沿交替路径替换，可使匹配数增加 1。
为什么增广路径有用
假设我们已经选了一些匹配边。若能找到一条从未匹配左部顶点出发、到未匹配右部顶点结束的路径，并且这条路径上的边在“未选、已选、未选、已选……”之间交替出现，那么这条路径叫增广路径。
沿着这条路径做一次替换：把原来没选的边选上，把原来选上的边取消。由于路径两端都是未匹配顶点，替换后匹配边数会增加 。
对小图来说，找更大匹配时不要只盯着单条边。先看有没有从未匹配点到未匹配点的交替路径；一旦找到，沿路径翻转就能改进当前匹配。
交互：尝试形成匹配
下面的交互工具把“每个端点最多用一次”做成了即时检查。你可以点选人员与任务之间的边，观察什么时候选择仍是匹配，什么时候出现重复使用端点。
例题：为三名助教安排三项任务
有三名助教 和三项任务 。可行关系如下：
- 能做 或 ；
- 能做 ；
- 能做 或 。
问：能否给每名助教安排一个不同任务？
先把问题画成二分图。左部是助教 ，右部是任务 。一条边表示“这名助教能做这项任务”。
观察限制最强的顶点。 只能做任务 ，所以若想所有人都被安排， 必须匹配到 。
Hall 定理的直觉：瓶颈集合
在人员与任务数量相同的二分图中，我们常问：能不能让每个人都匹配到不同任务？Hall 定理给出了准确条件。设 是左部中的任意一组顶点， 表示这组顶点在右部能连接到的所有邻居。若存在覆盖左部的匹配，就必须对每个 都有：
这句话很朴素：任意一组人合起来能选择的任务数，不能少于这组人的人数。否则即使其他地方再宽松，这组人内部也必定有人没任务。
瓶颈集合说明 Hall 条件：当某组人的可选岗位少于这组人数时，无法为每个人匹配不同岗位。
不做完整证明，但要会用
Hall 定理的完整证明需要更细的匹配论证，本章只使用它的判断思路。遇到“能否每人一个不同选择”的问题时，可以先找瓶颈集合：
- 是否有两个人都只能选同一个岗位？
- 是否有三门课都只能安排在两间教室？
- 是否有一组学生的可选项目合起来太少？
如果找到了这样的集合，就能立刻说明完美匹配不存在。如果所有集合都满足 Hall 条件，则完美匹配存在；这是定理的强结论。
Hall 条件不是只检查单个人，也不是只检查全体人。它要求检查左部的每一个子集。实际解题时，我们通常先找最可能拥挤的那几组，而不是机械列出所有子集。
练习：左部为 ，右部为 。边为 。是否存在覆盖左部的匹配？
不存在。取 ，它们的邻居只有 ，所以 。三个人合起来只能选择两个任务，不可能都匹配到不同任务。
平面图：能否画成没有交叉
一张图是平面图，意思是它可以画在平面上，使得边只在公共端点处相交。这里要注意“可以画成”这几个字。某个画法有交叉，不代表这个图不是平面图；也许换一种摆放方式，交叉就消失了。
同一个图可以通过重新画变成没有边交叉的平面画法，顶点和边未改变。
图和画法的区别
图由顶点和边决定，画法只是把它放到纸面上的一种方式。对平面图来说，我们关心的是是否存在一种没有交叉的画法。画好之后，边把平面分成若干区域，这些区域叫面。最外面的无界区域也算一个面。
如果一个图无论怎么重画都有边交叉，它就不是平面图。经典的两个非平面图是 和 。本章不证明这两个结论，但要记住它们常作为判断非平面性的入口。
边相交的地方如果不是原图中的顶点，就不能把交点临时当成新顶点来数。平面图要求边只在原本共享的端点相交。
欧拉公式：顶点、边、面之间的平衡
对连通平面图，如果某个没有交叉的画法有 个顶点、 条边、 个面，那么：
这就是欧拉公式。它不是在说每张图都有两个面，也不是说顶点、边、面可以随便数；它说的是连通平面图的三个计数之间有固定平衡。
欧拉公式的计数对象：顶点 V、边 E、面 F，其中外部无界区域也算作一个面。
一个直觉证明
从一棵树开始看最容易。一棵连通树没有回路，所以它只有一个面，也就是外面。树有 ，因此：
如果在平面画法里加一条不交叉的边，并且这条边连接已经存在的两个顶点，它会把某个面切成两个面。于是 增加 ， 也增加 ， 不变。许多连通平面图可以看成从生成树开始逐步加边得到，所以这个值一直保持为 。
交互：观察欧拉公式
下面的工具让你切换几个连通平面图，并观察添加或删除不交叉边时 、、 的变化。特别留意外部区域也算一个面。
用欧拉公式排除非平面图
对简单连通平面图，若 ，每个面至少由三条边围成。数所有面的边界时，每条边最多被数两次，所以可得到常用不等式：
例如 有 、。如果它是平面图，就应有：
这不可能，所以 不是平面图。
对于没有三角形的简单连通平面图，每个面至少由四条边围成，可以得到更强的不等式：
是二分图，没有三角形。它有 、。若它是平面图，就应有 ，矛盾。因此 不是平面图。
练习：一个连通平面图有 个顶点、 条边。它有几个面？
由欧拉公式 ，得到 ，所以 。这 5 个面包括最外面的无界区域。
图着色：把冲突变成相邻不能同色
图着色是给图的每个顶点分配颜色，使得相邻顶点颜色不同。若能用 种颜色完成，就说这个图是 可着色的。最少需要的颜色数叫色数，常记作 。
着色听起来像画图，实质是资源分配。颜色可以代表考试时段、无线频道、寄存器、会议室批次或地图颜色。边表示冲突：两端不能拿同一种资源。
图着色把相互冲突的课程分配到不同颜色或时段中，用于说明排课中的冲突约束。
地图着色
地图着色可以这样建模：每个区域变成一个顶点，如果两个区域共享一段边界，就在对应顶点之间连边。给地图上色，就是给这个冲突图上色。共享一点角落通常不算相邻，因为它不会形成一整段边界冲突。
平面图和地图着色之间有很深的联系。四色定理说明，每张平面地图都可以用不超过四种颜色染色，使相邻区域颜色不同。这个定理的证明很长，本课程只把它当作背景事实，不把它作为证明训练目标。
排课冲突图
排课也可以变成着色问题。把每门考试看成一个顶点。如果两门考试有学生重叠，就连一条边。给顶点染颜色，就是给考试安排时段。相邻顶点不能同色，表示有共同学生的两门考试不能同一时段。
贪心着色的作用和局限
一个简单办法是按某个顺序处理顶点：轮到一个顶点时，给它分配当前可用的最小颜色，避开已经染色的邻居。这个方法叫贪心着色。
贪心着色很快，也常能给出不错方案。但它不保证用最少颜色，因为顶点顺序会影响结果。同一张图，换一个处理顺序，可能使用不同数量的颜色。
“我找到一种用 4 色的方案”只能说明这个图至多需要 4 色，不能说明它至少需要 4 色。要证明“必须用 4 色”，还要说明任何 3 色方案都会失败。
综合建模：从限制到图
遇到现实问题时，先不要急着套定理。更可靠的做法是把对象、关系和目标分开。
明确顶点代表什么。若顶点是人员和任务两类对象，问题可能走向二分图；若顶点是课程、区域或事件，问题可能走向冲突图。
明确边代表什么。边可以表示“可以配对”，也可以表示“不能同时发生”。这两种含义方向相反，建模时不能混用。
明确目标是什么。想让每个人分到任务，是匹配问题；想用尽量少的时段避开冲突，是着色问题；想分析画法和区域，是平面图问题。
最后选择工具。匹配看端点是否重复，Hall 条件看瓶颈集合，平面图看是否存在无交叉画法，着色看相邻顶点是否同色。
模型选择对照
同一个现实问题有时能建出不同的图。关键是让边的含义和目标一致：可行关系通常适合匹配；冲突关系通常适合着色。
自测练习
练习 1：一个三角形图是否是二分图？
不是。三角形是长度为 的奇回路。若沿三条边交替放入左右两部，最后会要求起点同时属于两边，产生矛盾。
练习 2：在一个二分图中，左部有 个顶点，右部有 个顶点。如果某三个左部顶点的邻居合起来只有两个右部顶点，能否存在覆盖左部的匹配？
不能。取这三个左部顶点为 ，有 。这组顶点已经形成 Hall 瓶颈。
练习 3：一个连通平面图有 个顶点、 条边。它有几个面？
由 得到 ，所以 。其中一个面是外部无界区域。
练习 4：若一个简单图有 个顶点和 条边，它能是平面图吗？
不能。简单连通平面图在 时满足 。这里 ，但 ，违反不等式。
练习 5：某考试冲突图中有三门课程两两冲突。至少需要几个考试时段？
至少需要 个时段。三门课程两两相邻，形成三角形；相邻顶点不能同色，所以三者必须使用三种不同颜色。
本章小结
二分图把两类对象之间的可行关系分开，匹配从中选择互不抢端点的边。Hall 条件提醒我们检查瓶颈集合：一组对象的可选对象数不能少于这组对象本身。
平面图关注的是是否存在无交叉画法，而不是当前画法是否交叉。对连通平面图，欧拉公式 把顶点、边、面连在一起，也能给出判断非平面图的简单工具。
图着色把“相邻不能同色”变成资源分配语言。地图着色、考试排课、频道分配和冲突约束都可以用同一套图语言表达。学会选择模型，比记住某个孤立公式更重要。