匹配
匹配¶
匹配基础概念¶
匹配 \(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\) 每个顶点的完美匹配的充要条件是：
其中 \(N(S)\) 表示 \(S\) 的邻集（图 \(G\) 中所有与 \(S\) 相邻接顶点的集合），\(N(S)\) 一定是 \(Y\) 的子集。
Abstract
\(G=(X,Y)\) 存在饱和 \(X\) 每个顶点的匹配也常说成存在由 \(X\) 到 \(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)\) 表示奇分支数目（有奇数个顶点的分支）
彼得森定理¶
哥尼定理的推论，是完美匹配的充分条件而不是必要条件
没有割边的 3 正则图存在完美匹配
匈牙利算法¶
可以解决问题：
- 在无权偶图中寻找完美匹配
- 在有权偶图中寻找最优匹配
- 在有权偶图中寻找最小匹配（权值和最小）
- 在有权偶图中寻找最大匹配（权值和最大，通过所有权值取反转化为最小匹配问题）。
\(G=(X,Y)\)，匈牙利算法需要满足约束：\(|X|=|Y|\)。
Abstract
基本思想
从任意初始匹配 \(M_0\) 出发，通过寻求一条 \(M_0\) 可扩路 \(P\) ，令 \(M_1=M_0\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\Delta E(P)\)，转（a）
有权图最优匹配¶
可行顶点标号¶
设 \(G=(X,Y)\) ，若对 \(\forall x\in X,\forall y\in Y\)，有：
则称 \(l\) 是赋权完全偶图 \(G\) 的可行顶点标号。
一个简单常用的可行顶点标号：
相等子图¶
设 \(l\) 是赋权完全偶图 \(G=(X,Y)\) 的可行顶点标号，令：
称 \(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）；
- 否则，计算：
修改 \(l\) 如下：
给出新的可行顶点标号，在新标号下重新开始。
（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）
该算法把上面原来的匈牙利算法用于其中，主要是用来判定和求完美匹配。