第五章匹配与因子分解

5.1 概念

匹配：如果\(M\)是图\(G\)的边子集(不含环），且\(M\)中的任意两条边没有共同顶点，则称\(M\)是\(G\)的一个匹配或对集或边独立集
饱和点：如果\(G\)中顶点\(v\)是\(G\)的匹配\(M\)中某条边的端点，称它为\(M\)饱和点，否则为\(M\)非饱和点
最大匹配：如果\(M\)是图\(G\)的包含边数最多的匹配，称\(M\)是\(G\)的一个最大匹配
完美匹配：若最大匹配饱和了\(G\)的所有顶点，称它为\(G\)的一个完美匹配
\(M\)交错路：如果\(M\)是图\(G\)的匹配，\(G\)中一条由\(M\)中的边和非\(M\)中的边交错形成的路，称为\(G\)中的一条\(M\)交错路
\(M\)可扩路：若\(M\)交错路的起点与终点是\(M\)非饱和点，称这种\(M\)交错路为\(M\)可扩路

Hall定理：

设\(G=(X, Y)\)是偶图，则\(G\)存在饱和\(X\)每个顶点的匹配的充要条件是对\(\forall S\subseteq X\)，有\(|N(S)|\geq |S|\)
Hall定理也可表述为：设\(G=(X,Y)\)是偶图，如果存在\(X\)的一个子集\(S\),使得\(|N(S)|<|S|\)，那么\(G\)中不存在由\(X\)到\(Y\)的匹配

\(k\)正则偶图：

定理以及结论：

从任意匹配\(M\)开始，

步骤1 若\(M\)饱和\(X\)的每个顶点，则停止。否则，任取一个\(X\)中的\(M\)非饱和顶点\(u\)，令\(S=\{u\}\)，\(T=\varnothing\)
步骤2 若\(N(S)\neq T\)，任取一顶点\(y\in N(S)-T\)；若\(N(S)=T\)，则不存在完美匹配（根据Hall定理）
步骤3 若\(y\)是\(M\)饱和的。设\(yz\in M\)，\(S=S\cup \{z\}\)，\(T=T\cup \{y\}\)，然后转到步骤2；若\(y\)是\(M\)非饱和的，则\(P=(u，y)\)路是\(M\)可扩的，\(M=M\bigtriangleup E(P)\)，然后转到步骤1

注意理解匈牙利算法与库恩算法的相似与不同！

可行顶点标号：设\(G=(X,Y)\)，若对任意的\(x\in X,y\in Y\)，有\(l(x)+l(y)\geq w(xy)\)，则称\(l\)是赋权完全偶图\(G\)的可行顶点标号。
- 事实上，设： \[\begin{cases} l(x)=\underset{y\in Y}{max} \ w(xy),若x\in X,\\ l(y)=0,若y\in Y. \end{cases}\] 则\(l\)是\(G\)的一个可行顶点标号。
相等子图：设\(l\)是赋权完全偶图\(G=(X, Y)\)的可行顶点标号，令\(E_l=\{ xy\in E(G)|l(x)+l(y)=w(xy)\}\)，则称\(G_l=G[E_l]\)为\(G\)的对应于\(l\)的相等子图。
库恩算法（Kuhn-Munkres）: 给一初始顶点标号\(l\),在\(G_l\)中任选一个匹配\(M\)，
- 步骤1 若\(X\)是\(M\)饱和的，则\(M\)是最优匹配。否则，令\(u\)是一个\(M\)非饱和点，置\(S=\{ u\},T=\varnothing\)
- 步骤2 若\(T\subset N_{G_l}\)，转到步骤3。否则，计算： \[\alpha _l=\underset{x\in S,y\notin T}{min}\{ l(x)+l(y)-w(xy)\}\] \[\hat{l}=\begin{cases} l(v)-\alpha _l,v\in S\\ l(v)+\alpha _l,v\in T\\ l(v),\small 其它 \end{cases}\] 得到新的可行顶点标号，重新开始
- 步骤3 若\(y\)是\(M\)饱和的。设\(yz\in M\)，\(S=S\cup \{z\}\)，\(T=T\cup \{y\}\)，然后转到步骤2；若\(y\)是\(M\)非饱和的，则\(P=(u，y)\)路是\(M\)可扩的，\(M=M\bigtriangleup E(P)\)，然后转到步骤1