# 匹配

# 匹配基础概念

匹配 $M$ —— 如果 $M$ 是图 $G$ 的边子集 (不含环)，且 $M$ 中的任意两条边没有共同顶点，则称 $M$ 是 $G$ 的一个匹配，或对集，或边独立集。

如果 $G$ 中顶点是 $G$ 的匹配 $M$ 中某条边的端点，称它为 $M$ 饱和点，否则为 $M$ 非饱和点。

最大匹配 $M$ (无向图定义) —— 如果 $M$ 是图 $G$ 的包含边数最多的匹配，称 $M$ 是 $G$ 的一个最大匹配。

特别是，若最大匹配饱和了 $G$ 的所有顶点，称它为 $G$ 的一个完美匹配。

$M$ 交错路 —— 如果 $M$ 是图 $G$ 的匹配， $G$ 中一条由 $M$ 中的边和非 $M$ 中的边交错形成的路，称为 $G$ 中的一条 $M$ 交错路。

特别地，若 $M$ 交错路的起点与终点都是 $M$ 非饱和点，称这种 $M$ 交错路为 $M$ 可扩路。

# 贝尔热定理

Berge

$G$ 的匹配 $M$ 是最大匹配，当且仅当 $G$ 不包含 $M$ 可扩路。

# HALL 定理

完美匹配的充要条件，将 $X$ 视为需求，$Y$ 视为供给，可以理解为供给必须满足需求。

$G=(X,Y)$ 是偶图，则 $G$ 存在饱和 $X$ 每个顶点的完美匹配的充要条件是：

$$\forall S\subseteq X,\ \ |N(S)|\geq|S|$$

其中 $N(S)$ 表示 $S$ 的邻集（图 $G$ 中所有与 $S$ 相邻接顶点的集合），$N(S)$ 一定是 $Y$ 的子集。

⭐️推论：若 $G$ 是 $k(k\gt0)$ 正则偶图，则 $G$ 存在完美匹配。

# 典例

# 例 1

证明每个 $k$ 方体都是 $k$ 正则偶图。

事实上，由 $k$ 方体的构造： $k$ 方体有 $2k$ 个顶点，每个顶点可以用长度为 $k$ 的二进制码来表示，两个顶点连线当且仅当代表两个顶点的二进制码只有一位坐标不同。

如果我们划分 $k$ 方体的 $2k$ 个顶点，把坐标之和为偶数的顶点归入 $X$，否则归入 $Y$ 。显然，$X$ 中顶点互不邻接，$Y$ 中顶点也如此。所以 $k$ 方体是偶图。

又不难知道 $k$ 方体的每个顶点度数为 $k$ , 所以 $k$ 方体是 $k$ 正则偶图。

由推论： $k$ 方体存在完美匹配。

直接在 k 方体中找出完美匹配。

设 $k$ 方体顶点二进制码为 $x_1,x_2,\cdots,x_k$ , 我们取 $x_1,x_2,\cdots,x_{k-1},0$ , 和

$(x-1,x_2,\cdots,x_{k-1},1)$ 之间的全体边所成之集为 $M$。

显然，$M$ 中的边均不相邻接，所以作成 $k$ 方体的匹配，又容易知道：$|M|=2^{k-1}$，所以 $M$ 是完美匹配。

# 例 2

求 $𝐾_{2𝑛}$ 和 $𝐾_{𝑛,𝑛}$ 中不同的完美匹配的个数

$𝐾_{2𝑛}$ 的任意一个顶点有 $2𝑛-1$ 种不同的方法被匹配。所以 $𝐾_{2𝑛}$ 的不同完美匹配个数等于 $(2𝑛-1)𝐾_{2𝑛-2}$ , 如此推下去，可以归纳出 $𝐾_{2𝑛}$ 的不同完美匹配个数为：$(2𝑛-1)!!$。

同样的推导方法可归纳出 $𝐾_{𝑛,𝑛}$ 的不同完美匹配个数为：$𝑛!$。

# 例 3

证明树至多存在一个完美匹配。

证明：若不然，设 $𝑀_1$ 与 $𝑀_2$ 是树 $T$ 的两个不同的完美匹配，那么 $𝑀_1\Delta𝑀_2≠\varnothing$, 容易知道：$𝑇[𝑀_1\Delta 𝑀_2]$ 每个非空部分顶点度数为 2 ，即它存在圈，于是推出 $T$ 中有圈，矛盾。

# 图的点覆盖

$G$ 的一个顶点子集 $K$ 称为 $G$ 的一个点覆盖，如果 $G$ 的每条边都至少有一个端点在 $K$ 中。$G$ 的一个包含点数最少的点覆盖称为 $G$ 的最小点覆盖，其包含的点数称为 $G$ 的覆盖数，记为 $\alpha(G)$。

⭐️设 $M$ 是 $G$ 的匹配，$K$ 是 $G$ 的覆盖，若 $|M|=|K|$ , 则 $M$ 是最大匹配，而 $K$ 是最小覆盖。

# 哥尼定理

偶图的点覆盖与偶图匹配间的关系

在偶图中，最大匹配的边数等于最小覆盖的顶点数。

# 托特定理

图 $G$ 有完美匹配当且仅当对 $V$ 的任意非空真子集 $S$ , 有：

$$o(G-S)\leq|S|$$

$o(G-S)$ 表示奇分支数目（有奇数个顶点的分支）

# 彼得森定理

哥尼定理的推论，是完美匹配的充分条件而不是必要条件⚠️

没有割边的 3 正则图存在完美匹配

# 匈牙利算法

可以解决问题：

• 在无权偶图中寻找完美匹配
• 在有权偶图中寻找最优匹配
  • 在有权偶图中寻找最小匹配（权值和最小）
  • 在有权偶图中寻找最大匹配（权值和最大，通过所有权值取反转化为最小匹配问题）。

$G=(X,Y)$，匈牙利算法需要满足约束：$|X|=|Y|$。

# 无权偶图完美匹配

# M 交错树

定义 设 $G=(X,Y)$，$M$ 是 $G$ 的匹配，$u$ 是 $M$ 非饱和点。称树 $H$ 是 $G$ 的扎根于点 $u$ 的 $M$ 交错树，如果：

• $u\in V(H)$；
• 对任意 $v\in V(H)$，$(u,v)$ 路是 $M$ 交错路；

扎根于 $M$ 非饱和点 $u$ 的 $M$ 交错树 $H$ 有两种情形：

• 情形 1: 除点 $u$ 外，$H$ 中所有点为 $M$ 饱和点，且在 $M$ 上配对；
• 情形 2: $H$ 包含除 $u$ 外的 $M$ 非饱和点。

# 匈牙利算法

设 $M$ 是初始匹配。$H$ 是扎根于 $M$ 非饱和点 $u$ 的交错树。令：$S=V(H)\cap X$， $T=V(H)\cap Y$。

• （a）
  • 若 $M$ 饱和 $X$ 所有顶点，停止；
  • 否则，设 $u$ 为 $X$ 中 $M$ 非饱和顶点，置 $S=\{u\}$ ，$T=\varnothing$；
• （b）
  • 若 $N(S)=T$，则 $G$ 中不存在完美匹配；
  • 否则设 $y\in N(S)-T$；
• （c）
  • 若 $y$ 为 $M$ 饱和点，且 $yz\in M$，置 $S=S\cup\{z\}$，$T=T\cup \{y\}$，转（b）；
  • 否则，设 $P$ 为 $M$ 可扩路，置 $M=M\Delta E(P)$，转（a）

# 有权图最优匹配

# 可行顶点标号

设 $G=(X,Y)$ ，若对 $\forall x\in X,\forall y\in Y$，有：

$$l(x)+l(y)\geq w(xy)$$

则称 $l$ 是赋权完全偶图 $G$ 的可行顶点标号。

一个简单常用的可行顶点标号：

$$\begin{cases} l(x)=\max_{y\in Y}w(xy),&x\in X\\ l(y)=0,&y\in Y \end{cases}$$

# 相等子图

设 $l$ 是赋权完全偶图 $G=(X,Y)$ 的可行顶点标号，令：

$$E_l=\{xy\in E(G)|l(x)+l(y)=w(xy)\}$$

称 $G_l=G[E_l]$ 为 $G$ 的对应于 $l$ 的相等子图。

# Kuhn 算法

Kuhn 采用顶点标号修改策略，找到了求最优匹配好算法如下

⚠️ 求的是权值和最大的匹配⚠️

给一初始顶点标号 $l$ ，在相等子图 $G_l$ 中任选一个匹配 $M$。

（1）

• 若 $X$ 是 $M$ 饱和的，则 $M$ 是最优匹配；
• 否则，令 $u$ 是一个 $M$ 非饱和点，置 $S=\{u\}$，$T=\varnothing$；

（2）

• 若 $T\sub N_{G_l}(S)$，转（3）；
• 否则，计算：

$$\alpha_l=\min_{x\in S,y\notin T}\{l(x)+l(y)-w(xy)\}$$

修改 $l$ 如下：

$$l=\begin{cases} l(v)-\alpha_l,&v\in S\\ l(v)+\alpha_l,&v\in T\\ l(v),&\text{others}\\ \end{cases}$$

给出新的可行顶点标号，在新标号下重新开始。

（3）在 $N_{G_l}(S)\backslash T$ 中选择点 $y$：

• 若 $y$ 是 $M$ 饱和的，$yz\in M$，则置 $S=S\cup\{z\}$， $T=T\cup\{y\}$，转（2）；
• 否则，设 $P$ 是 $G_l$ 中 $M$ 可扩路，置 $M=M\Delta E(P)$，转（1）

该算法把上面原来的匈牙利算法用于其中，主要是用来判定和求完美匹配。