匹配

匹配

匹配基础概念

匹配 $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$ 每个顶点的完美匹配的充要条件是：

$$\mathrm{\forall }S\subseteq X,|N(S)|\ge |S|$$

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

Abstract

$G=(X,Y)$ 存在饱和 $X$ 每个顶点的匹配也常说成存在由 $X$ 到 $Y$ 的匹配 。

推论：若 $G$ 是 $k(k>0)$ 正则偶图，则 $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\mathrm{\Delta }{𝑀}_2\ne \varnothing$, 容易知道：$𝑇[{𝑀}_1\mathrm{\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)\le |S|$$

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

彼得森定理

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

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

匈牙利算法

可以解决问题：

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

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

Abstract

基本思想

从任意初始匹配 $M_0$ 出发，通过寻求一条 $M_0$ 可扩路 $P$ ，令 $M_1=M_0\mathrm{\Delta }E(P)$ ，得到比 $M_0$ 更大的匹配 $M_1$。

1965 年，Edmonds 首先提出：用扎根于 $M$ 非饱和点 $u$ 的 $M$ 交错树的生长来求 $M$ 可扩路。

无权偶图完美匹配

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\mathrm{\Delta }E(P)$，转（a）

有权图最优匹配

可行顶点标号

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

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

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

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

$$\{\begin{array}{ll}l(x)=\underset{y\in Y}{max}w(xy),& x\in X\\ l(y)=0,& y\in Y\end{array}$$

相等子图

设 $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\text{sub}{N}_{G_l}(S)$，转（3）；
• 否则，计算：

$${\alpha }_l=\underset{x\in S,y\notin T}{min}\{l(x)+l(y)-w(xy)\}$$

修改 $l$ 如下：

$$l=\{\begin{array}{ll}l(v)-{\alpha }_l,& v\in S\\ l(v)+{\alpha }_l,& v\in T\\ l(v),& \text{others}\end{array}$$

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

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

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

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