Skip to content

11 Finding A Good Match. Coloring andMatching

Introduction

一个移动网络运营商提供4种不同频率的服务。现在要去扩展业务，在选定的十个地方建立基站。两个频率相同的基站距离必须大于50公里。给定这些信息，存在一种合适的分配方式吗？
现在需要转化成数学问题。基站的位置是顶点，两点之间右边意味着这两点之间的距离不大于50公里。
但是频率这个信息如何表示呢？染色。可以分配不同的颜色给各个顶点。比如频率1是红色，频率2是绿色等等。
下面这个命题是这个问题的数学表述。

Proposition 11.1. 令是十个塔的集合，是如上描述的图。能够安排四种不同的频率的方式等价于使用四种颜色对染色且没有相邻点是同色的。

Definition 11.2. 一个图的色数(chromatic number)表示最小的整数，满足如下条件：图能够被种颜色染色且相邻顶点一定是不同颜色。

图的顶点的着色，其中相邻的顶点具有不同的颜色，称为适当顶点着色(proper vertex coloring)，或适当着色(proper coloring)。
如果一个图的顶点能够被种颜色着色且没有相同颜色的邻接点，称为可着色(k-colorable)。

Example 11.3. 五边形的色数是3，两种是不行的。如下图所示。

Bipartite Graphs

着色问题的最重要的特例是。这个无处不在的特例有一个属于自己的名字。

Definition 11.4. 可2着色的图称为二分图(bipartite)。存在互不相连的两个部分，的每一条边都是连接的一点和的一点。

下图是典型的二分图，注意，在同色的类内部是没有边的。

所有的树是二分图，从根开始，比如染成红色，邻接点染成绿色，再接着的邻接点染成红色，依次下去。正方形、六边形、八边形等也是二分图。
显然，三角形不是二分图，一个点染成红色，一个点染成绿色，第三个点必然和其中一个颜色相同。进而，如果一个图包含三角形，那么肯定不是二分图。
不包含三角形就是二分图了吗？五边形是一个很好地反例。进而，有长度是奇数的环的图，都不是二分图。
下面的定理是上述的概括。

Theorem 11.5. 图是二分图，当且仅当不包含长度是奇数的环。
Proof. 图是二分图，那么不包含长度是奇数的环，这个容易证明。反证法。假设有环。用红色和蓝色染色。不失一般性地用红色染第一点，那个必须是蓝色，是红色，依次，是红色，但是是一条边，两个顶点必须是不同颜色。
现在证明另外一个方向。图不包含长度是奇数的环，那么是二分图。从某一个点开始，染色成蓝色，对于其他某点，如果到的最短路径是奇数，染成红色，如果是偶数，染成蓝色，这样是符合题意的染色方式。假定和是同色的，同时有一条边相连。令分别是两点到的最短路径，由于这两点同色，那么和的长度同为奇数或者同为偶数，加上边，构成了长度为的环，由于同奇偶，那么环的长度是奇数，与前提假设矛盾，所以不存在这样的点，所以是二分图。

个顶点的简单图是二分图，能有多少条边呢？这里想要求的是上限。树有条边，那么答案线性于，或者是，或者是 的若干分之一？下面的定理给出了答案，边数更接近图的边的最大值。
Theorem 11.6. 图是个顶点的简单二分图。如果是偶数，那么最多有条边；是奇数，最多有条边。
Proof 令是两种颜色的点数，那么边数最大值是，那么这个问题转换成了求解二次函数的最大值问题。

在上述证明中，构造了一个非常重要的二分图种类，完全二分图(complete bipartite graphs)。如果完全二分图的两种点数分别是，记作。
令是一个个顶点的简单图，如果有条边，那么可能是一个二分图，因为它可能是。如果有条边，那么根据Theorem 11.6它不是二分图，且有一个长度是奇数的环。下面的引理是一个更强的命题。

Lemma 11.7. 令是个顶点的简单图，并且至少有条边，那么包含三角形。
Proof. 对进行递归来证明。如果，那么是的有至少五条边的子图，根据上面的定理，必然有一个长度是奇数的环，又因为只有4个点，所以环的长度是3。
是图两个相连的点。如果两者的度之和大于，那么有公共顶点，那么组成了一个三角形。如果度之和最大是，删除这两点之后，度最多会减少（之间度算了两次）。删除后，得到一个顶点数是的图，至少有条边，由递归可知这个删除了两个点的图包含三角。

下面要给出一个更强的定理。
Theorem 11.8. 令是个顶点的简单图，并且至少有条边，那么包含个三角形。
如果有条边，可以是完全二分图，一个环都没有，但是只要再加上一条边，就会出现个三角形！树不是这样的，个顶点的树有条边，再加一条边会形成一个长度不定的环（取决于树和新加的边）。
Proof. 假定只有条边。
时，去掉一条边，很显然，有两个三角形。
假设对所有小于的情况都成立。现在考虑就好。Lemma 11.7是说有一个三角形了，还要找到剩下的个三角形。
基于除之外的点连接到三角形的点的边数分成三类讨论。先证明如果边数是条边，那么有个三角形。如果外部顶点(outside vertex)和任意两个顶点相连，就会形成一个三角形。有个外部顶点，根据鸽巢原理，则有个三角形。
后续证明主要思路是如果很多边和相连，那么会产生会多三角形，另一方面，如果边很少的话，那么这些点之间会有很多三角形。
(1) ，那么就找到了个三角形。
(2) ，那么和外部点的边最多是。由于包含三条边，那么其他个顶点组成的子图至少有条边。再去掉一个度最少的点，形成的个顶点的子图的边大于 有个顶点，至少有条边，根据递归假设，有个三角形，加上的至少一个三角形，找到了剩余的个三角形。
(3) ，也就是和外部顶点的边最多条；最少有一条，否则子图有条边，和任意一点构成的图有条边，个顶点，根据递归假设，个三角形。那么内部的边数最少是，加上连接到的某条边和对应顶点构成了个顶点和条边的图，这个图有个三角形。

Matchings in Bipartite Graphs

二分图在生活中有很多应用。考虑个开放的职位和个候选人。定义一个个顶点的图，前个顶点表示职位，后个顶点表示候选人。当且仅当一个候选人申请了某个职位且符合要求(qualified)，那么有一条边连接这两个顶点。显然是一个二分图，因为所有的边都是连接前个顶点和后个顶点，而每个集合内部没有边。如下图所示。

整个招聘过程就是双方匹配的过程。如果职位招聘了候选人，将边加粗，等等。随着招聘的进行，有越来越多的边被加粗，但是在整个过程中，加粗的边都是不相交顶点的边(vertex-disjoint edges)组成，因为没有一个能能被两个职位录取，反过来，一个职位也不能招聘两个人。
如果招聘过程结束，个职位都被填满了，那么会有条粗体的边。如果少于个职位招聘到了合适的候选人，说明找不到合格的候选人，那么没有条粗体的边，不过它们都是不相交顶点的边。

Proposition 11.9. 令是这个招聘问题，个开放职位和个候选人。能够填充满个职位等价于能在上述的图中找到条顶点不相交的边。

下图展示了某种可能的最后结果。

Definition 11.10. 令是任意一个图，令是的边的集合，且没有两条边有共同顶点。是图的匹配(matching)。如果图的每个顶点都被的边覆盖，那么称为完美匹配(perfect matching)。
匹配也被称为边的独立集(independent set of edges)。上述定义不要求是二分图。不过后续讨论都是基于二分图的。

Definition 11.11. 令是一个二分图。当是的匹配且覆盖的所有点时，是到的完美匹配。
如果不关心只关心到的完美匹配，称有一个到的匹配，或能被匹配到。

Bipartite Graphs with Perfect Matchings

是一个二分图。有两个问题，有到的完美匹配吗（对应前面的例子就是职位都填满了）？如何找到最大匹配？
先考虑第一个问题。是一个必要条件。如果中的两个点的度都是1，但是都和相连，那么显然不存在完美匹配。
泛化上述的条件。如果是的点的子集，令是的所有邻接点。是的元素，当且仅当存在某个点，是一条边。邻接点集合与匹配有关，因为如果只想将匹配到，那么可以将注意力集中在二分图上。
如果上下文有歧义，使用符号来表示。

Proposition 11.12. 令是一个二分图。能被完美匹配到，那么对于所有的都满足。
Proof. 反证法。假定有一个不满足，那么。显然不能匹配到，那么任意包含的集合都不能匹配到，进而不能匹配到。

下面的定理是说上述命题的逆命题也是成立的。被称之为菲利普霍尔定理(Philip Hall's theorem)。
Theorem 11.13 (Philip Hall's theorem). 令是一个二分图。 ，当且仅当对于所有的都满足。
Proof. 只需证明半个定理即可，因为Proposition 11.12已经完成了一部分。下面的证明是1950年Halmos和Vaughn给出的。
对做递归来进行证明。易证初始状态。假设对于小于的非负整数都成立，现在考虑。根据题意，对于所有，有。下面分两种情况讨论。
(1) 假定对于每一个，都有严格的小于关系。假定是邻接点并且。令，是任意的非空集合，那么，进而有。根据递归假设，在图中，能够完美匹配到，那么增加一条边，得到想求的结论。
(2) 假定对于某个，有。将分成两个部分，是组成的子图，是剩余点组成的子图。
在中，选任意集合，那么，又因为的所有邻接点都在，所以，进而有，那么满足递归假设。
在中，选择任意自己，那么。由于两者是不相交集合，那么，所以也满足递归假设。
综上，可以匹配到，能够匹配到，所以可以匹配到。

Exercise 9是一个和这个定理相关的应用，虽然第一眼看上去无关。
Theorem 11.13很有用，但是它没有告诉在存在一个完美匹配的前提下如何找到一个，在没有的前提下找到最大匹配(maximum matching)。
最大(maximum)和最大化(maximal)是不同的。最大化是说在某个匹配上在增加一条边，就破坏了匹配的属性；最大是说没有其他匹配比这个匹配的边数更多了。
显然，最大匹配是最大化的匹配，但反之不一定成立。如下图所示。

Definition 11.14. 令是一个图，是其的一个匹配。路径是交替路径(alternating path)如果属于但不属于。

的起点和终点不是的边的邻接点的话，那么不是最大匹配。因为，丢掉替换上会得到更大匹配。这里描述的路径称为增广路径(augmenting path)。
Definition 11.15. 如果交替路径的起点和终点都是中没有用到的点，那么这条路径称为增广路径。

下图的左边粗体是，虚线是，右边粗体是由增广路径替换后得到的更大的匹配。

需要注意的是，这里的定义对任意简单图都成立，不一定非要是二分图。

Theorem 11.16. 令是简单图，是其的匹配。是最大匹配，当且仅当没有关联的增广路径。
Proof. 上图已经证明如果有增广路径，那么不是最大匹配，逆否命题就是最大匹配没有增广路径。
现在证明如果没有增广路径说明是最大匹配。反证法。假定没有增广路径且有最大匹配。考虑，即两者的交集减去两者的并集。由于都是匹配，那么的连通分量要么是偶数循环（那么和贡献了相同的边数），要么是交替路径。又由于是最大匹配，没有增广路径，那么交替路径的长度也必须是偶数。所以。

Stable Matchings in Bipartite Graphs

假定在一个小城市，有个候选人，同时有个空缺职位。每一个候选人有一个长度为的名单表示自己对这个职位的偏好，同时每一个空缺职位的招聘经理也有一个长度为的名单表示对个候选人的偏好。问题不是如果找到一个完美匹配，而是找到一个稳定(stable)完美匹配。首先来定义稳定匹配(stable matchings)。

Definition 11.17. 令是有完美匹配的的二分图。的每个点都有对的每个点的一个偏好列表，反之亦然。如果以下两个条件不都成立，则是稳定的：
(a) ，但是更偏好
(b) ，但是更偏好

换句话说，一个匹配是稳定的前提是不能在两个集合中各找到一个点，都放弃当前匹配。
有一个相当简单的方式能够构造稳定的完美匹配。首先，每个候选人申请自己最偏好的职位，招聘经理临时告诉在偏好名单里最靠前的人被录用了，同时拒绝其他人。重复该步骤。没有工作的候选人继续申请偏好名单的第二个职位，第三个职位等等。如果候选人申请了临时招聘了的职位，如果这个职位的招聘经理更偏好，那么录用而拒绝。直到所有候选人都找到了工作，同时招聘经理也找到了他们想要的人。这个过程总是成立的。假设有候选人还没有工作，那么存在一个职位还没有被填充，这就意味着还没有申请，那么说明这个过程还没有结束。
上述过程不仅找到了完美匹配，而且命题更强，因为是稳定的。
令是二分图，表示候选人，表示空缺职位。假定我们找到的完美匹配不是稳定的。这就说明存在是如下关系：，但是更偏好，同时也更偏好。这两个点会同时放弃当前的匹配。

More Than Two Colors

Theorem 11.6告诉我们二分图的边不能太多。对于个点的二分图，为了让边尽可能的多，那么要尽可能的平分两种颜色的点的数量。
下面考虑染色图。尽可能平分的思想还是有效的。
令，也就是将个顶点分成个子集，个集合有个点，其余集合有个点。也就是尽可能的平分。那么染色完全图的边数是 下面的定理是说没有染色图的边数能够超过。

Theorem 11.18. 令是个顶点且有条边的简单图。那么包含一个子图，也就是说不是染色图。
Proof. 令是个顶点且不包含子图。我们要证明其边数最多是。
对进行递归证明。时，显然成立。假设小于等于都成立。命题隐含了增加任意一条边，会创建一个子图，那么包含一个子图，。那么的边只可能在 * 内部 * 边的一个顶点在，另一个顶点 * 内部

内部有 条边；里面的点最多和中的个点相连，有条边；有点，那么有条边。所以 如果边数大于的话，一定会出现子图。

Theorem 11.18是一个相当强的命题说明什么图不是染色图：一个图有太多边导致有子图，那么不是染色图。另一方面，一个图不包含子图也至少需要种颜色来染色。比如一个奇数长度的环，不包含，但是需要三种颜色。事实上，奇数长度的循环和完全图分别对染色数有要求。
Theorem 11.19. 令是不包含奇数长度循环的非完全图的连通图。令正整数，的每个点的度最大是，那么。

一个图的染色数高，那么度也高。

Matchings in Graphs That Are Not Bipartite

现实中有很多问题是在非二分图中寻找匹配。比如在一个大公司找到一种匹配，每一对的两个人都互相认识；又或者是周末进行足球比赛，每组比赛的两个队在过去两年没有比赛；显然这两个例子都不能用二分图来表示，但我们仍旧想从中得到定点不相邻的边的集合。
幸运的是，对于是否存在完美匹配，有一个充要条件。如果是一个图，是顶点集合的子集，令是图删除点集和所有相邻的边得到的子图，表示中奇数顶点的连通分量的个数。

Theorem 11.20 (Tutte's theorem). 一个图有完美匹配等价于对于的所有顶点的子集，不等式都成立。
从左往右这个方向的证明很简单，令是某个完美匹配，那么奇数个顶点的连通分量至少要包含一个的点，那么。
如果一个图没有完美匹配，但是添加任意新边就有完美匹配，那么我们称图是saturated non-factorizable graph。
Lemma 11.21. 如果图是saturated non-factorizable graph，又如果中的每个点都与其他点相连，那么的连通分量是完全图。
Proof 反证法。令是的边，假设不相连。肯定存在使得不相连，否则。
由于是saturated non-factorizable graph，那么有完美匹配，又因为没有完美匹配，那么。类似地，有完美匹配，且。的对称差是一个环，令分别是包含的环。下面分两种情况讨论。
1） 假设。令。，那么，另一方面，和的边一样多，是一个匹配，所以是的完美匹配，和命题中的条件矛盾。
2）假设。沿着环从到再到之一，比如，令到的路径是，又因为，那么对于而言是交替路径（实际是环）。令，和1）类似，和一样的边数，且不包含因为，那么是图的完美匹配，矛盾。
综上，是的边，那么也是，所以是完全图。

Theorem 11.22. 图是saturated non-factorizable graph等价于它有以下结构： * 有奇数个点且是完全图，或者 * 有偶数个点并且有顶点不相交的完全子图组成，每个有奇数个点，并且每个顶点都和的每个顶点相连。

Proof. 图有奇数个点，那么没有完美匹配。也只有完全图满足saturated non-factorizable因为没法再增加边（saturated non-factorizable要求能增加一条边使之有完美匹配。）。
令，其中是Lemma 11.21.中的定义的。是的连通分量，根据Lemma 11.21.，是完全图，并且的每个点和的每个点都是连通的。
没有完美匹配，那么的个数必然大于，否则的一个点（奇数个，所以会多一个点不能在内部配对）可以和的点配对然后组成完美匹配。
有偶数个点，那么至少就要有个奇数点的分量。
其实也不能多于，因为我们可以添加一条连接其中的两个分量，得到的，而，没有完美匹配。加一条边但是没有完美匹配，不是saturated non-factorizable graph。
因此有个奇数个点的分量。
最后，不会有偶数个点的分量，因为添加一条边连接它和其他分量，不会组成有完美匹配的图。

现在来证明Tutte's theorem。

Proof. 反证法。假设满足所有条件但是没有完美匹配。那么增加一些边可以得到有完美匹配的图，在这个过程的前一步，是saturated non-factorizable graph。
如果有奇数个点，那么选，进而，与条件矛盾。
那么有偶数个点。令是中和其他点都相连的点集。根据Theorem 11.22.， 那么有个分量。移除最开始加的边（），这个过程会导致连通分量分裂，但是奇数点数的分量至少还是会有一个奇数点数的分量。那么，与条件矛盾。
所以最开始的假设不成立。

Exercises

(6) 对于任意正整数，存在不包含三角形的图，它的染色数是。
Solution. 递归法。，单独的一条边满足条件；时，五边形满足题意。假设时成立，有一个图的染色数是，对于所有顶点，新增顶点，其邻接点和的邻接点一样，再新增点，和所有的相连，那么新的图没有三角形，且染色数是。其实从到也是由这种方法构造的。

(7) 证明个顶点的循环用种颜色染色，染色方法数是 $$(x-1)[(x-1)^{n-1}+1]\text{ if is even}(x-1)[(x-1)^{n-1}-1]\text{ if is odd}$$ Solution. 先证明是偶数的情况。递归法。的时候，两个点一条边，显然成立。假设时成立，考虑的情况。有种颜色，有种颜色，有种颜色，以此类推到。对于，大部分情况有种颜色，因为不能和同色，总数有。但是如果是同色的话，那么有种可能性，比多一种，那么前面的总数就少算了一些情况。少算了多少呢？恰好是同色的数量，也就是的染色数，根据递归是种，那么边形的染色数是 对于是奇数，基础情况是，三角形的染色数是，就是题目的公式。递归过程和偶数的情况类似。

(9) 是方块矩阵，每个元素都是非负整数，且每行每列之和都是正整数，那么是双随机矩阵(doubly stochastic matrix)或幻方(magic square)。求证是置换矩阵(permutation matrices)的和。
Solution. 基于递归。，那么就是置换矩阵。考虑。是每行每列之和为的幻方，如果存在一个置换矩阵，元素都是非负整数（情况），那么递归证明就完成了。
令是二分图，左边是点代表的行号，右边的点代表的列号，如果对应元素是整数，那么有一条边相连。如果存在完美匹配，对应的矩阵也就是要找的，去掉，一些元素从正数减一到非负数，满足前面的描述。所以问题转化成有没有完美匹配。
利用Hall's theorem，需要证明任意个元素的集合至少有个邻接点。对应于矩阵，就是任意行，有至少列有非零元素。假定只有列有非零元素。那么这行的和是，同时也是行和列的交集部分之和，因为其他列都是零，但是这列的总和才是，小于其部分和，矛盾。

(10) 是每行和为2的的三维幻方，各个元素都是非负整数。总是成立吗？其中是每行和为1的三维幻方。
Solution. 反例。三层分别是 第二层右下角的的矩阵无法分解了。
假设的第二层右下角是 那么第一层的右下角只能是全零，否则垂直地看（第一层、第二层、第三层）对角线上的元素之和要大于一了。那么进而第二行和第三行左边第一个元素都必须是一，那么导致第一列之和是二。
假设的第二层右下角是 那么和第三层组合的时候会出现类似的问题。