第四章匹配与覆盖¶

4.1 图的匹配与覆盖问题¶

图的匹配相关概念¶

匹配（matching）：设 \(M\) 是图 \(G\) 的一个不含环的边子集，若 \(M\) 中任意两条边没有公共端点，则称 \(M\) 为 \(G\) 的一个匹配，也称为对集或边独立集。
- \(M\) 饱和点：与匹配 \(M\) 中某条边关联的顶点；
- \(M\) 非饱和点：不与匹配 \(M\) 中任何边关联的顶点。
最大匹配（maximum matching）：图 \(G\) 中包含边数最多的匹配。
- 完美匹配（perfect matching）：饱和图 \(G\) 所有顶点的匹配，即 \(M\) 中的边的端点覆盖了 \(G\) 的所有顶点。
  - 完美匹配一定是最大匹配，最大匹配不一定是完美匹配；
  - 若 \(G\) 有完美匹配 \(M\)，则 \(|V(G)|\) 为偶数，且
    
    \[ |M|=\frac{|V(G)|}{2} \]
\(M\) 交错路（\(M\)-alternating path）：设 \(M\) 是图 \(G\) 的一个匹配，\(M\) 交错路是指由 \(M\) 中的边与非 \(M\) 中的边交替组成的路。
- \(M\) 可扩路/增广路（\(M\)-augmenting path）：两个端点都是 \(M\) 非饱和点的 \(M\) 交错路。
  - 可扩路的第一条边与最后一条边均不属于 \(M\)；
  - 可扩路的长度为奇数，其中非 \(M\) 中的边比 \(M\) 中的边多一条。
对称差（symmetric difference）：集合 \(A\) 与 \(B\) 的对称差定义为

\[ A\triangle B=(A\setminus B)\cup(B\setminus A) \]
- 若 \(P\) 是一条 \(M\) 可扩路，则将 \(P\) 上属于 \(M\) 的边删去，并加入 \(P\) 上不属于 \(M\) 的边，可得到新的匹配
  
  \[ M'=M\triangle E(P),\quad |M'|=|M|+1 \]
贝尔热定理（Berge 定理）：图 \(G\) 的匹配 \(M\) 是最大匹配，当且仅当 \(G\) 不包含 \(M\) 可扩路。
- 该定理是通过不断寻找可扩路求最大匹配的理论依据。

偶图的匹配与 Hall 定理¶

设 \(G=(X,Y;E)\) 是偶图（二部图）。

由 \(X\) 到 \(Y\) 的匹配：饱和 \(X\) 中每个顶点的匹配，也称为完全匹配。
- 存在由 \(X\) 到 \(Y\) 的匹配，必有 \(|X|\leq|Y|\)；
- 当 \(|X|=|Y|\) 时，由 \(X\) 到 \(Y\) 的匹配就是完美匹配。
邻集：对于 \(S\subseteq X\)，与 \(S\) 中至少一个顶点相邻的所有顶点构成的集合称为 \(S\) 的邻集，记为

\[ N(S)=\{y\in Y:\exists x\in S,\ xy\in E(G)\} \]
Hall 定理（婚姻定理）：偶图 \(G=(X,Y;E)\) 存在饱和 \(X\) 中每个顶点的匹配，当且仅当

\[ |N(S)|\geq|S|,\quad\forall S\subseteq X \]
- 必要性：\(S\) 中的顶点必须与 \(N(S)\) 中互不相同的顶点配对，因此 \(|N(S)|\geq|S|\)。
- 充分性：若最大匹配 \(M^*\) 不饱和 \(X\) 中某点 \(u\)，则从 \(u\) 出发沿交错路搜索，记可达的两侧顶点集为 \(S\subseteq X\) 与 \(T\subseteq Y\)，则有
  
  \[ N(S)=T,\quad |N(S)|=|T|=|S|-1 < |S| \]
  
  与 Hall 条件矛盾。
- Hall 定理也可以表述为：偶图 \(G=(X,Y;E)\) 若存在一个 \(X\) 的子集 \(S\)，使得 \(|N(S)|<|S|\)，则不存在由 \(X\) 到 \(Y\) 的匹配。
推论：
- \(k\)-正则偶图的完美匹配：若 \(G=(X,Y;E)\) 是 \(k\)-正则偶图（\(k>0\)），则 \(G\) 存在完美匹配。
  - 由两侧顶点的度数之和相等，得
    
    \[ k|X|=k|Y|\implies|X|=|Y| \]
  - 对于任意 \(S\subseteq X\)，从 \(S\) 发出的边均与 \(N(S)\) 关联，因此
    
    \[ k|S|\leq k|N(S)|\implies|S|\leq|N(S)| \]
    
    由 Hall 定理可知存在 \(X\) 到 \(Y\) 的匹配。又 \(|X|=|Y|\)，因此该匹配是完美匹配。
- 完全图的完美匹配数目：\(K_{2n}\) 中不同的完美匹配个数为 \((2n-1)!!\)
  - 固定一个顶点，它有 \(2n-1\) 种配对方式，剩余顶点继续配对，可递推得到上述公式。
- 完全二部图的完美匹配数目：\(K_{n,n}\) 中不同的完美匹配个数为 \(n!\)
  - 将 \(X\) 中的顶点与 \(Y\) 中的顶点一一配对，\(X\) 中第一个顶点有 \(n\) 种选择，第二个顶点有 \(n-1\) 种选择，依次类推。
- 树的完美匹配：一棵树至多存在一个完美匹配。
  - 树叶只能与其唯一的邻接点配对；删去这两个顶点后，对剩余森林反复进行相同操作。若完美匹配存在，每一步的配对都是唯一确定的。

点覆盖与哥尼定理¶

点覆盖（vertex cover）：若顶点子集 \(K\subseteq V(G)\) 满足 \(G\) 中每条边都至少有一个端点属于 \(K\)，则称 \(K\) 为 \(G\) 的一个点覆盖。
- 最小点覆盖（minimum vertex cover）：包含顶点数最少的点覆盖。
- 覆盖数：最小点覆盖所包含的顶点数，记为 \(\alpha(G)\)。
匹配与点覆盖的关系：设 \(M\) 是 \(G\) 的任意匹配，\(K\) 是 \(G\) 的任意点覆盖，则

\[ |M|\leq|K| \]
- 匹配中的边没有公共端点，每条匹配边都至少需要点覆盖中的一个不同顶点来覆盖。
定理：若匹配 \(M\) 与点覆盖 \(K\) 满足 \(|M|=|K|\)，则 \(M\) 是最大匹配，\(K\) 是最小点覆盖。
哥尼定理（König 定理）：在偶图中，最大匹配 \(M^*\) 的边数等于最小点覆盖 \(K^*\) 的顶点数，即

\[ |M^*|=\alpha(G) \]
由最大匹配构造最小点覆盖：设 \(M^*\) 是偶图 \(G=(X,Y;E)\) 的最大匹配。
1. 令 \(U\) 为 \(X\) 中所有 \(M^*\) 非饱和点的集合；
2. 从 \(U\) 出发，在 \(X\) 到 \(Y\) 的方向沿非匹配边、在 \(Y\) 到 \(X\) 的方向沿匹配边搜索，令到达的顶点集为 \(Z\)（包含 \(U\)）；
3. 令 \(S=Z\cap X\)，\(T=Z\cap Y\)，则 \(N(S)=T\)，且 \(S\setminus U\) 与 \(T\) 中的顶点在 \(M^*\) 下配对；
4. 取
  
  \[ K^*=(X\setminus S)\cup T \]
  
  则 \(K^*\) 是点覆盖，且
  
  \[ |K^*|=|X\setminus S|+|T| =|X\setminus U|=|M^*| \]
  
  因此 \(K^*\) 是最小点覆盖。

4.2 图的因子分解¶

因子与因子分解的概念¶

因子：图 \(G\) 的一个至少包含一条边的生成子图，记为 \(G_i\)，即 \(V(G_i)=V(G)\)。
- \(k\) 正则因子：若 \(G_i\) 是 \(k\)-正则图，则称 \(G_i\) 为 \(G\) 的一个 \(k\) 正则因子，或简称为 \(k\) 因子。
因子分解：将图 \(G\) 分解为若干个边不重的因子之并，即

\[ G=G_1\cup G_2\cup\cdots\cup G_t \]

其中 \(V(G_i)=V(G)\)，\(E(G_i)\cap E(G_j)=\varnothing\)（\(i\neq j\)），且 \(\cup_{i=1}^t E(G_i)=E(G)\)。
- \(k\) 因子分解：若图 \(G\) 能分解为若干个 \(k\) 因子之并，则称 \(G\) 可作 \(k\) 因子分解。
  - 若 \(G\) 分解为 \(t\) 个 \(k\) 因子，则 \(G\) 是 \(tk\)-正则图。

图的一因子分解¶

一因子：图 \(G\) 的 \(1\)-正则生成子图，同时也是一个完美匹配的边导出子图。
- 一因子存在性：图存在一因子，当且仅当图存在完美匹配。
完全图一因子分解：
- 一因子分解：完全图 \(K_{2n}\) 可以进行一因子分解，且每次分解得到 \(2n-1\) 个边不重的一因子。
  - 构造思路：固定一个顶点，其余 \(2n-1\) 个顶点按循环次序轮转；每轮按照固定位置配对，得到一个一因子。轮转 \(2n-1\) 次，使每对顶点恰好配对一次。
- 一因子数目：完全图 \(K_{2n}\) 的不同一因子数目等于其完美匹配数目，即
  
  \[ (2n-1)!!=\frac{(2n)!}{2^n n!} \]
定理：每个 \(k\)-正则偶图（\(k>0\)）都可作一因子分解，分解为 \(k\) 个一因子。
- 由 Hall 定理，\(G\) 存在完美匹配；删去相应一因子的边后，得到 \((k-1)\)-正则偶图，依次类推，直到分解为 \(k\) 个一因子。

图的二因子分解¶

二因子：图 \(G\) 的 \(2\)-正则生成子图。
- 在简单图中，二因子由若干个顶点不相交的圈组成，并覆盖图的所有顶点。
- 一个包含所有顶点的圈是二因子，但二因子不一定连通。
定理1：完全图 \(K_{2n+1}\) 可作二因子分解，分解为 \(n\) 个二因子。
- 可将 \(K_{2n+1}\) 分解为 \(n\) 个边不重的生成圈。
- 构造方法：设顶点集为 \(\{v_1,v_2,\ldots,v_{2n+1}\}\)，在前 \(2n\) 个顶点上作路
  
  \[ P_i=v_i v_{i-1}v_{i+1}v_{i-2}v_{i+2}\cdots v_{i-(n-1)}v_{i+(n-1)}v_{i-n},\quad i=1,2,\ldots,n \]
  
  其中下标按模 \(2n\) 计算，取值为 \(1,2,\ldots,2n\)。将 \(v_{2n+1}\) 与每条路的两个端点相连，即得到所需的 \(n\) 个生成圈。
定理2：完全图 \(K_{2n}\) 可分解为一个一因子和 \(n-1\) 个二因子。
- 构造方法：设顶点集为 \(\{v_1,v_2,\ldots,v_{2n}\}\)，在前 \(2n-1\) 个顶点上作路
  
  \[ P_i=v_i v_{i-1}v_{i+1}v_{i-2}v_{i+2}\cdots v_{i-(n-1)}v_{i+(n-1)},\quad i=1,2,\ldots,n-1 \]
  
  其中下标按模 \(2n-1\) 计算，取值为 \(1,2,\ldots,2n-1\)。将 \(v_{2n}\) 与每条路的两个端点相连，即得到所需的 \(n-1\) 个二因子；每个顶点原来的度为 \(2n-1\)，删去这些圈的边后，每个顶点的度均为 \(1\)，余下的边构成一因子。
定理3：一个至少含一条边的连通图可作二因子分解，当且仅当它是正偶数度的正则图。
- 必要性：若分解为 \(k\) 个二因子，则每个顶点的度均为 \(2k\)。
- 充分性：由彼得森（Petersen）的结论，每个正偶数度的正则图都存在二因子；每次删去一个二因子的边，剩余图仍为偶数度正则图，依次类推，直到分解为若干个二因子。

图的森林因子分解¶

以下讨论不含环的图的森林因子分解。

森林因子：图 \(G\) 的一个为森林的因子。
- 森林因子保留原图的全部顶点，可以含有孤立点。
森林因子分解：将图 \(G\) 分解为若干个边不重的森林因子之并。
荫度（arboricity）：图 \(G\) 的森林因子分解所需因子的最少数目，记为 \(\sigma(G)\)。
纳什–威廉斯荫度计算公式（Nash-Williams 公式）：设 \(G\) 有 \(n\geq2\) 个顶点，则

\[ \sigma(G)=\max_{2\leq s\leq n} \left\lceil\frac{m_s}{s-1}\right\rceil \]

其中

\[ m_s=\max\{|E(H)|:H\subseteq G,\ |V(H)|=s\} \]

即 \(m_s\) 为 \(G\) 中所有 \(s\) 阶子图的最大边数，\(\lceil x\rceil\) 表示向上取整。
- 一个 \(s\) 阶森林至多有 \(s-1\) 条边，因此覆盖一个有 \(m_s\) 条边的 \(s\) 阶子图，至少需要 \(\lceil m_s/(s-1)\rceil\) 个森林因子。
完全图的荫度：对于 \(n\geq2\)，有

\[ \sigma(K_n)=\left\lceil\frac{n}{2}\right\rceil \]
- \(K_{2n}\) 可分解为 \(n\) 条边不重的生成路：设顶点集为 \(\{v_1,v_2,\ldots,v_{2n}\}\)，则 \(n\) 条生成路为
  
  \[ P_i=v_i v_{i-1}v_{i+1}v_{i-2}v_{i+2}\cdots v_{i-(n-1)}v_{i+(n-1)}v_{i-n},\quad i=1,2,\ldots,n \]
  
  其中下标按模 \(2n\) 计算，共得到 \(n\) 个森林因子。
- \(K_{2n+1}\) 可以通过如下方式构造：先将前 \(2n\) 个顶点构成的完全图分解为 \(n\) 条生成路，并在每个因子中保留 \(v_{2n+1}\) 为孤立点；剩余与 \(v_{2n+1}\) 关联的边构成一个星图，共得到 \(n+1\) 个森林因子。
完全二部图的荫度：对于 \(r,s\geq1\)，有

\[ \sigma(K_{r,s})=\left\lceil\frac{rs}{r+s-1}\right\rceil \]

4.3 匈牙利算法与最优匹配算法¶

交错树与可扩路的寻找¶

\(M\) 交错树：设 \(M\) 是偶图 \(G=(X,Y;E)\) 的匹配，\(u\in X\) 是 \(M\) 非饱和点。若树 \(H\subseteq G\) 包含 \(u\)，且从 \(u\) 到 \(H\) 中任意顶点的路都是 \(M\) 交错路，则称 \(H\) 为扎根于 \(u\) 的 \(M\) 交错树。
交错树的生长：令 \(S=V(H)\cap X\)，\(T=V(H)\cap Y\)，从 \(S=\{u\}\)、\(T=\varnothing\) 开始。
1. 若 \(N(S)=T\)，则搜索不能继续；由于 \(S\setminus\{u\}\) 与 \(T\) 中顶点配对，有
  
  \[ |N(S)|=|T|=|S|-1<|S| \]
  
  由 Hall 定理，不存在饱和 \(X\) 的匹配。
2. 若 \(N(S)\setminus T\neq\varnothing\)，取 \(y\in N(S)\setminus T\)，并取与 \(y\) 相邻的 \(x\in S\)：
  - 若 \(y\) 是 \(M\) 饱和点，设 \(yz\in M\)，则将边 \(xy\)、\(yz\) 及顶点 \(y\)、\(z\) 加入交错树；
  - 若 \(y\) 是 \(M\) 非饱和点，则树中从 \(u\) 到 \(x\) 的路加上边 \(xy\)，构成一条 \(M\) 可扩路。

匈牙利算法¶

算法思想：从任意初始匹配出发，利用交错树寻找可扩路；每找到一条可扩路，就通过对称差将匹配的边数增加 \(1\)。

求偶图饱和一侧顶点的匹配¶

算法目标：在偶图 \(G=(X,Y;E)\) 中寻找饱和 \(X\) 的匹配；当 \(|X|=|Y|\) 时，即为寻找完美匹配。
算法流程：
1. 取任意初始匹配 \(M\)，可取 \(M=\varnothing\)；
2. 判断 \(M\) 是否饱和 \(X\) 的所有顶点：
  - 若是，则停止，\(M\) 为所求的饱和 \(X\) 的匹配；
  - 若否，则取 \(X\) 中一个 \(M\) 非饱和点 \(u\)，置 \(S=\{u\}\)，\(T=\varnothing\)；
3. 判断是否 \(N(S)=T\)：
  - 若是，则停止，由 Hall 定理，\(G\) 中不存在饱和 \(X\) 的匹配；
  - 若否，则取 \(y\in N(S)\setminus T\)；
4. 判断 \(y\) 是否为 \(M\) 饱和点：
  - 若是，设 \(yz\in M\)，置 \(S=S\cup\{z\}\)，\(T=T\cup\{y\}\)，返回步骤 3；
  - 若否，得到从 \(u\) 到 \(y\) 的 \(M\) 可扩路 \(P\)，置 \(M=M\triangle E(P)\)，返回步骤 2。

求偶图最大匹配¶

算法流程：
1. 取任意初始匹配 \(M\)，可取 \(M=\varnothing\)；
2. 判断 \(M\) 是否饱和 \(X\) 的所有顶点：
  - 若是，则停止，\(M\) 为最大匹配；
  - 若否，则令 \(U\) 为 \(X\) 中所有 \(M\) 非饱和点的集合，置 \(S=U\)，\(T=\varnothing\)；
3. 判断是否 \(N(S)=T\)：
  - 若是，则停止，\(M\) 为最大匹配；
  - 若否，则取 \(y\in N(S)\setminus T\)；
4. 判断 \(y\) 是否为 \(M\) 饱和点：
  - 若是，设 \(yz\in M\)，置 \(S=S\cup\{z\}\)，\(T=T\cup\{y\}\)，返回步骤 3；
  - 若否，得到从某个 \(u\in U\) 到 \(y\) 的 \(M\) 可扩路 \(P\)，置 \(M=M\triangle E(P)\)，返回步骤 2。
正确性：当 \(N(S)=T\) 时，令 \(K=(X\setminus S)\cup T\)，则 \(K\) 是点覆盖，且

\[ |K|=|X\setminus S|+|T| =|X\setminus S|+|S\setminus U| =|X\setminus U|=|M| \]

因此，\(M\) 为最大匹配，\(K\) 为最小点覆盖。
推论：
- 若最大匹配算法因 \(N(S)=T\) 停止，则 \(K^*=(X\setminus S)\cup T\) 是最小点覆盖；
- 若算法因 \(M\) 饱和 \(X\) 而停止，则 \(X\) 本身就是最小点覆盖。

最优匹配算法¶

最优匹配问题¶

最优分配问题：在赋权偶图 \(G=(X,Y;E)\) 中，\(|X|=|Y|\) 且存在完美匹配，求一个完美匹配 \(M^*\)，使得权值之和最大。
最优匹配：在所有完美匹配 \(M\) 中，权值之和最大的匹配 \(M^*\)，即

\[ w(M^*)=\max_{M}\sum_{e\in M}w(e) \]

Kuhn-Munkres 算法（KM 算法）¶

可行顶点标号与相等子图¶

可行顶点标号：给每个顶点 \(v\) 指定实数 \(L(v)\)，使得对每条边 \(xy\in E\) 都有

\[ L(x)+L(y)\geq w(xy) \]
- 一种初始标号方法为
  
  \[ \begin{cases} L(x)=\max\{w(xy):xy\in E\},&x\in X,\\ L(y)=0,&y\in Y. \end{cases} \]
相等子图（equality subgraph）：由满足标号之和恰好等于边权的边构成的非赋权生成子图，记为

\[ G_L=(X,Y;E_L),\quad E_L=\{xy\in E:L(x)+L(y)=w(xy)\} \]
定理：若相等子图 \(G_L\) 中存在完美匹配 \(M^*\)，则 \(M^*\) 是原赋权偶图 \(G\) 的最优匹配。
- 对于 \(G\) 中任意完美匹配 \(M\)，有
  
  \[ w(M)=\sum_{xy\in M}w(xy) \leq\sum_{xy\in M}\bigl(L(x)+L(y)\bigr) =\sum_{v\in X\cup Y}L(v) \]
- 当 \(M^*\subseteq E_L\) 时，上式取等号，因此 \(M^*\) 的总权值最大。

标号调整¶

在相等子图 \(G_L\) 中，从一个非饱和点生长交错树。若搜索停止于 \(N_{G_L}(S)=T\)，则需调整标号，使 \(S\) 到 \(Y\setminus T\) 之间出现新的相等边。
调整量：取这些边的最小松弛量

\[ d=\min_{\substack{x\in S,\ y\in Y\setminus T\\xy\in E}} \bigl(L(x)+L(y)-w(xy)\bigr) \]

此时这些边尚不属于相等子图，因此 \(d>0\)。
标号调整公式：

\[ L'(v)= \begin{cases} L(v)-d,&v\in S,\\ L(v)+d,&v\in T,\\ L(v),&v\notin S\cup T. \end{cases} \]
调整的性质：
- 新标号仍满足 \(L'(x)+L'(y)\geq w(xy)\)，因此仍是可行标号；
- 当前匹配边与交错树中的边仍属于新的相等子图；
- 至少有一条从 \(S\) 到 \(Y\setminus T\) 的边成为新的相等边，使交错树可以继续生长。

KM 算法流程¶

算法思想：通过顶点标号把赋权偶图的最优匹配问题转化为相等子图中的完美匹配问题，再利用匈牙利算法求解。
算法流程：
1. 初始化可行标号 \(L\)，构造相等子图 \(G_L\)，取 \(M=\varnothing\)；
2. 判断 \(M\) 是否为图 \(G_L\) 完美匹配：
  - 若是，则停止，\(M\) 即为原图的最优匹配；
  - 若否，则取 \(X\) 中一个 \(M\) 非饱和点 \(u\)，置 \(S=\{u\}\)，\(T=\varnothing\)；
3. 判断是否 \(N_{G_L}(S)=T\)：
  - 若是，则停止，由 Hall 定理，图 \(G_L\) 没有完美匹配，因此进行标号调整，计算调整量 \(d\)，更新标号与相等子图，保留当前匹配和交错树，返回步骤 3；
  - 若否，则取 \(y\in N(S)\setminus T\)；
4. 判断 \(y\) 是否为 \(M\) 饱和点：
  - 若是，设 \(yz\in M\)，置 \(S=S\cup\{z\}\)，\(T=T\cup\{y\}\)，返回步骤 3；
  - 若否，得到从 \(u\) 到 \(y\) 的 \(M\) 可扩路 \(P\)，置 \(M=M\triangle E(P)\)，返回步骤 2。

第四章 匹配与覆盖¶

4.1 图的匹配与覆盖问题¶

图的匹配相关概念¶

偶图的匹配与 Hall 定理¶

点覆盖与哥尼定理¶

4.2 图的因子分解¶

因子与因子分解的概念¶

图的一因子分解¶

图的二因子分解¶

图的森林因子分解¶

4.3 匈牙利算法与最优匹配算法¶

交错树与可扩路的寻找¶

匈牙利算法¶

求偶图饱和一侧顶点的匹配¶

求偶图最大匹配¶

最优匹配算法¶

最优匹配问题¶

Kuhn-Munkres 算法（KM 算法）¶

可行顶点标号与相等子图¶

标号调整¶

KM 算法流程¶

第四章匹配与覆盖¶