最后更新: 2025-01-22 10:12 ● 参与者查看: 10 次纠错分享参与项目词条搜索

二分图的匹配

我们将在本章节介绍无向图中特殊的关系—匹配，然后将匹配和二分图两者结合起
来，介绍二分图的最大匹配和最佳匹配的有效算法
匹配的基本概念
我们来看一个实例：飞行大队有若干个来自各国的飞行员，专门驾驶一种型号的飞机，这种飞机每架要有两个飞行员驾驶。由于种种原因，例如语言不通或训练上的问题，有些飞行员不能在同一架飞机上飞行，问如何搭配飞行员，才能使出航的飞机最多。为简单起见，假设有 10 个飞行员，图 11.4 中的 $v_1, v_2, \cdots, v_{10}$ 就代表这 10 个飞行员。

如果两个人可以同机飞行，就在代表他们两个之间连一条线；两个人不能同机飞行就不连。例如 $v_1$ 和 $v_2$ 可以同机飞行，而 $v_1$ 和 $v_3$ 就不行。画了这个图后，就可以研究搭配飞行员的问题了。上图中画的三条粗线 $\left(v_2, v_3\right), ~\left(v_5, v_7\right)$ 和 $\left(v_6, ~ v_{10}\right)$ 就代表了一种搭配方案。由于一个飞行员不能同时派往两架飞机，因此任何两条粗线不能有公共的端点，我们把一个图中没有公共端点的一组边叫做一个＂匹配＂。这样，上面问题就成为：如何找一个包含最多条粗线的匹配？这个问题叫做图的最大匹配问题。请大家试试看，能不能从上图中找出一个包含四条边的匹配，再试试能不能找到包含五条边的匹配。

定义 11.11 （匹配）设图 $G(V, E), M \subseteq E$ ，如果 $M$ 中的任意两条边都没有公共点，则称 $M$ 是 $G$ 的一个匹配。

例如图 11.5 （a）（b）中的粗线组成的边集合 $M_1$ 与 $M_2$ 分别是图 $G_1$ 与 $G_2$ 的匹配。
 ![图片](/uploads/2025-01/addba2.jpg)
 
 上述的飞行员匹配问题的数学模型是从给定的图 $G$ 的所有匹配中，找出包含边数最多的匹配。这种匹配即所谓的最大匹配问题。

根据图的类型不同，匹配问题可分为两种：任意图的最大匹配和二分图的最大匹配。
在上述的飞行员匹配问题中，如果把飞行员划分成两个部分：正驾驶员和副驾驶员。这样问题转换为如何搭配正副驾驶员才能使出航飞机最多的问题，这一问题也可以归结为一个二分图上的最大匹配问题。

判别二分图
二分图的邻接矩阵一般可以具有如下形式

$$
A={ }_Y^X\left(\begin{array}{c:c}
0 & A_{12} \\
\hdashline A_{21} & A_Y \\
X
\end{array}\right)
$$

对于较简单的图，可以直观地判断其是否为二分图。然而，对于一个较复杂的图来说，根据定义或用图示方法，相邻矩阵判定其是否为二分图，既不方便亦不可靠，因此有必要制定一个行之有效的判定规则。

定理11．8 图 $G$ 是一个二分图当且仅当 $G$ 的每一个回路的长度均为偶数（如果 $G$ 无回路，相当于任一回路的长度为 0,0 视为偶数）。

证明：必要性，设 $G$ 是二分图，并设 $G$ 中任意一个长度为 $m$ 的回路 $C=v_{i_0}, v_{i_i}, v_{i_2} \cdots, v_{i_{m-1}}, v_{i_0}$ 。因为 $G$ 是二分图，因此可将 $V$ 分为两个互补顶点子集 $V_1$ 和 $V_2$ 。因 $V_{i_0}$ 和 $V_{i_1}$ 是邻接的，设 $v_{i_0} \in V_1, v_{i_1} \in V_2$ ，必有同理可得

$$
v_{i_2}, v_{i_4}, \cdots, v_{i_{m-2}} \in V_1, \quad v_{i_3}, v_{i_5}, \cdots, v_{i_{m-1}} \in V_2
$$

从顶点的下标可以看出，下标为偶数的顶点属于 $V_1$ ，而下标为奇数的顶点属于 $V_2$ ，今 $v_{i_{m-1}}$ 属于 $V_2$ ，故 $m-1$ 为奇数，即 $m$ 为偶数。所以 $G$ 的每一个回路的长度均为偶数。

充分性：设 $G$ 的任一回路的长度为偶数。分两种情况进行讨论。
（1）$G$ 是连通图。
将图的顶点集合 $V$ 按下列定义分为两个子集：

$$
V_1=\left\{v_i \mid v_i \text { 与某一指定结点 } v_0 \text { 的距离为偶数 }\right\} \quad V_2=V-V_1
$$

下面证明 $V_1$ 和 $V_2$ 是 $V$ 的两个互补顶点子集。
任取图 $G$ 的一条边 $e=\left(v_i, v_j\right)$ ，如果 $e$ 的两个端点 $v_i$ 和 $v_j$ 都在 $V_1$ 中，如下图所示的那样得到一个回路 $C=v_i, \cdots, v_0, \cdots, v_j, v_i$ 。

因 $v_i, v_j \in V_1$ ，按定义 $v_i$ 和 $v_j$ 到 $v_0$ 的距离都是偶数，再加上边 $e$ ，故回路 C 的长度为奇数，与题设矛盾，说明 $v_i$ 和 $v_j$ 不可能都处于 $V_1$ 中。

如果任意边 $e$ 的两个端点 $v_i$ 和 $v_j$ 都在 $V_2$ 中，则由定义 $v_i$ 和 $v_j$ 到 $v_0$ 的距离都是奇数，再加上边 $e$ ，故回路 $C$ 的长度仍为奇数，也与题设矛盾，说明 $v_i$ 和 $v_j$ 也不可能都处于 $V_2$ 中。因此只有唯一一种可能，即 $e$ 的两个端点，一个在 $V_1$ 中而另一个在 $V_2$ 中，由于 $e$ 是任意一条边，根据二分图的定义，$G$ 是二分图。
（2）$G$ 是非连通图。
此时可分片讨论，对 $G$ 的每个连通分量应用上面的证明，然后合并起来，即可得证。
二分图的最大匹配
如果已知某图是二分图，那么如何计算边数最多的匹配方案，即这个二分图的最大匹配呢？

最简单的方法是系统地列举出二分图的所有匹配，然后从中选出边数最多者。由于这种方法所需要的时间高达 $2^{|E|}$ ，因此不得不摒弃。下面我们介绍一种利用增广路径求二分图最大匹配的有效算法。

定义 11.12 设 $M$ 是二分图 $G$ 的一个匹配，我们将 $M$ 中的边所关联的顶点称为盖点，其余顶点称为未盖点。若一条路上属于 $M$ 的边和不属于 $M$ 的边交替出现，则称该路为关于 $M$的交错路。若路 $p$ 是一条起始点和结束点都是未盖点的交错路，则称 $p$ 为关于 $M$ 的增广路。

例如，从图 11.7 （a）中可找到一条增广路 $p=t_5 c_1 t_2 c_5$ ，其中实线边表示匹配M中的边。由增广路 p 的定义可知。

性质（1）一条关于 $M$ 的增广路的长度必为奇数，且路上的第一条边和最后一条边都不属
于M。例如图 11.7（a）的增广路p=t5c1t2c5的长度为 3，且(t5，c1)和(t2，c5)非匹配边。
 ![图片](/uploads/2025-01/67f746.jpg)
 性质（2）对于一条关于 $M$ 的增广路 $p$ ，将 $M$ 中属于 $p$ 的边删去，将 $p$ 中不属于 $M$ 的边添加到 $M$ 中，所得到的边集合记为 $M \oplus P$ ，则 $M \oplus P$ 比 $M$ 增加一条匹配边。例如，对图 11.7 （a）的增广路径 $p$ 进行匹配边与非匹配边的对换，得到图 11.7 （b），原 $p$ 路径上的一条匹配边 $\left(c_1\right.$ ， $t_2$ ）变为 $\left(t_5, c_1\right)$ 和 $\left(t_2, c_5\right)$ 两条匹配边，$P$ 路径外的匹配边不变，因此 $|M|$ 由原来的 4 条增加为 5条。

性质（3）$M$ 为 $G$ 的一个最大匹配当且仅当 $G$ 中不存在关于 $M$ 的增广路。例如图 11.7 （b）不存在关于 $M$ 的增广路径，$|M|=5$ ，是一个完全匹配。

性质（1）和（2）是显而易见的。对于性质（3），当存在一条关于 $M$ 的增广路时，由性质（2）可知，$M$ 不是最大匹配。反之，若不存在关于 $M$ 的增广路时，则 $M$ 是最大匹配。我们可以用反证法证明：如果 $M$ 不是最大匹配，则一定存在一个匹配 $M_1,\left|M_1\right|>|M|$ 。作 $M_2=M_1 \oplus M_。$
（1）$M_2$ 的各连通分支必定是关于 $M$ 和 $M_1$ 的交错路。因为 $M_2$ 是由 $M$ 和 $M_1$ 中非共同部分组成的，而 $M$ 和 $M_1$ 都是匹配边，各自边之间没有共同顶点，所以任何连通的道路都必然是交替出现 $M$ 和 $M_1$ 的边。
（2）由于 $\left|M_1\right|>|M|$ ，所以在所有的交错轨中必有这样一条交错路：属于 $M_1$ 的边多于 $M$ 的边，这条路必然是以 $M_1$ 的边开始，且以 $M$ 的边结束的交错路，即为关于 $M$ 的增广路，这与 $M$是最大匹配的假设相矛盾。由此证明了 $M$ 是最大匹配的充分条件是不存在关于 $M$ 的增广路。

性质（3）的证明过程为我们提供了找最大匹配的基本思想。
初始时，置 $M$ 为空集。然后反复在二分图中找一条关于 $M$ 的增广路 $P$ ，并用 $M \oplus P$代替 $M$ ，直至二分图中不存在关于 $M$ 的增广路，最后得到的匹配 $M$ 就是 $G$ 的一个最大匹配。

上一篇：最大流最小割定理

下一篇： Hall定理

本文对您是否有用？有用 (0) 无用 (0)