二分图匹配

目录

  1. 1. 交错路与增广路
  2. 2. Hall定理
  3. 3. 最大匹配与最小点覆盖
  4. 4. 最大独立集与最小边覆盖

思路: 先通过交错路和增广路的概念建立起处理最大匹配的工具, 证明匹配最大的充要条件是图中没有增广路。然后证明Hall定理, 顺便证明了婚配定理, 并利用之证明最大匹配与最小点覆盖的对偶性。最后证明最小边覆盖与最大独立集的对偶性, 以及这四者之间的关系。

交错路与增广路

对给定的一个匹配$M$, 交错路是指由未被浸润的顶点出发, 交错经过$\overline M$$M$中的边的路径, 增广路是指起点与终点均未被浸润的交错路。若对一个图$G$与其上的匹配$M$, 存在一条增广路$P$, 那么$M$与增广路$P$的对称差构成一个边数更大的匹配。

定理: 对一个图$G$与其上的匹配$M$, $M$最大当且仅当没有增广路。

必要性显然, 现证充分性, 即证明没有增广路时$M$一定最大。假设没有增广路且存在更大的匹配$M'$, 尝试寻找增广路, 从而得到矛盾。

作两匹配的对称差, 每个点的度数至多为2 (两个匹配各贡献1个) , 那么对称差的诱导子图的每个分量要么是偶环 (二分图没有奇环) , 要么是链。偶环中属于$M'$的边和属于$M$的边应一样多, 因为沿着偶环走, 一定是交替经过两匹配中的边 (否则同一匹配中有两条边浸润同一顶点) 。又由于$|M'|>|M|$, 一定有一个分量中属于$M'$的边多于属于$M$的边, 这个分量一定是一个交替经过$M'$$M$的链, 从而一定是增广路。得到矛盾。

Hall定理

定理: 对一个$X,Y$二部图, 存在匹配浸润$X$当且仅当$\forall S\subset X,|N(S)|\ge|S|$, 其中$N(S)$是从$S$中的点经过一条边可达的点的集合。

因为$N(S)$一定包含匹配中$S$对应的边, 那么显然$|N(S)|\ge|S|$, 必要性成立。

下证充分性。假设一个最大匹配$M$没有浸润$X$, 即不存在匹配浸润$X$, 尝试证明$\exists S\subset X,|N(S)|<|S|$。设$u\in X$没有被浸润, 考虑由$u$经交错路可达的点集, 记其与$X$的交集为$S$, 与$Y$的交集为$T$。若$S=\{u\}$, 那么$N(S)=\emptyset,|N(S)|<|S|$, 定理成立。现在$S-\{u\}$非空, 我们知道$T\subset N(S)$。实际上$T=N(S)$, 因为若从$v\in S$出发可达$v'\not\in T$, 由于从$u$$v$的路是交错路, 且最后一条边是$M$中的边, 那么$vv'$就是$M$之外的边 (否则$M$中有两条边浸润$v$) , 从而$u\rightarrow v\rightarrow v'$构成一个交错路, 即$v\in T$, 矛盾。所以由$S$中的点经一条边可达的点都在$T$中, 即$N(S)\subset T$, 故$N(S)=T$。由于$T$$S-\{u\}$$M$定义了一个双射, 故$|N(S)|=|T|=|S|-1<|S|$, 于是我们找到了使得$|N(S)|<|S|$$S\subset X$, 充分性得证。

Hall定理得证后, 可以轻松地证明婚配定理:

定理: $k$-正则的$X,Y$二部图必有完美匹配 ($k>0$) 。

证: 首先, 分别根据$X$中的点和$Y$中的点对边进行计数, 得$k|X|=k|Y|$, 故$|X|=|Y|$, 从而浸润$X$得匹配也浸润$Y$, 也就是完美匹配。

现证明这样的二部图满足Hall条件, 即$\forall S\subset X,|N(S)|\geq|S|$$\forall S\subset X$, 有$m=k|S|$条边与之关联。由于这些边都属于$N(S)$覆盖的边集, 所以$m\leq k|N(S)|$, 从而$k|S|\leq k|N(S)|$, 由$k>0$$|S|\leq|N(S)|$, Hall条件得到满足。然后由Hall定理即得婚配定理。

最大匹配与最小点覆盖

书上为引入最小点覆盖给出的理由是: 对一个匹配, 要判定它是否最大需要遍历交错路, 很麻烦, 需要一个更好找的结构来判定匹配的最大性。这个结构就是最小点覆盖。

定理: 最大匹配数$M$与最小点覆盖的顶点数$C$相等。

证明: 首先, 对一个最大匹配, 一个点覆盖必须覆盖这个匹配中的所有边, 也就是最小点覆盖的顶点数不少于最大匹配数, $M\leq C$。然后对于任意给定的最小点覆盖, 我们尝试寻找一个匹配使得匹配数与最小点覆盖点数相同, 从而证明等号必然可以取到。

$X,Y$二部图上的某个最小点覆盖$V$, 我们记$R=V\cap X,T=V\cap Y$。首先$X-R$$Y-T$中的点不会连边, 否则这条边没有被$V$覆盖。然后考察$R$$Y-T$之间的连边, 它们都被$R$覆盖。尝试应用Hall定理证明存在浸润$R$的匹配。对$\forall S\subset R$, 如果$|N(S)|<|S|$, 那么我们在$V$中将$S$换成$N(S)$, 它仍然是点覆盖 (因为$S$这些点的作用仅仅是覆盖与$S$相连的边们, 而现在$N(S)$可以用更少的点做到这件事) , 这与$V$的最小性矛盾。所以$R$$Y-T$的生成子图存在浸润$R$的匹配。同理, $T$$X-R$的生成子图存在浸润$T$的匹配, 并且这两个匹配不相交。于是可以将它们合并为一个原图中的匹配。

现在对于每个最小点覆盖, 都可以找到一个匹配使得匹配数与之相等, 也就是$M\leq C$中的等号一定可以取到, 所以$M=C$

要解释开头的那个 “结构” , 就可以理解为: 对一个匹配, 如果我能在这个匹配上 (在每条边上恰选一个点) 找到一个点覆盖, 那么这个匹配一定最大。这个估计只对肉眼有用吧…

最大独立集与最小边覆盖

感觉这个东西和上节标题听起来就很对偶。

定义: 记最大独立集的点数为$\alpha(G)$, 最大匹配边数为$\alpha'(G)$, 最小点覆盖的点数为$\beta(G)$, 最小边覆盖的边数为$\beta'(G)$

引理: 一个点集为独立集, 当且仅当其补为点覆盖, 故$\alpha(G)+\beta(G)=n(G)$

证明: 若点集为独立集, 那么其补必覆盖所有边, 否则有边联结独立集中的两点, 矛盾。必要性得证。对一个点覆盖, 其补集任两点间均无边相连, 故其补集为独立集。充分性得证。于是对最小独立集, 其补为最大覆盖 (否则有更大的覆盖, 其补为更小的独立集) , 从而$\alpha(G)+\beta(G)=n(G)$

定理: 若$G$没有孤立顶点, 那么$G$有边覆盖, 且$\alpha'(G)+\beta'(G)=n(G)$

证明: 对一个最小边覆盖, 尝试构造边数为$n(G)-\beta'(G)$的匹配。若对于最小边覆盖中的某条边, 其两个端点都已被其他边覆盖, 那么这条边可以去掉, 所以不存在这种情况。也就是说, 最小边覆盖的诱导子图不含有3-链, 它的每个分量都是一个菊花图。记诱导子图的分量数为$k$, 那么最小边覆盖中共有$n(G)-k$条边。在每个分量中选取一条边即可得到一个大小为$k$的匹配。这证明了$\alpha'(G)+\beta'(G)\geq n(G)$

对一个最大匹配, 尝试构造一个边数为$n(G)-\alpha'(G)$的边覆盖。只需要对最大匹配没有浸润的每个顶点选择一条边即可, 这样得到的边覆盖大小恰为$n(G)-\alpha'(G)$, 这证明了$\alpha'(G)+\beta'(G)\leq n(G)$

综上, $\alpha'(G)+\beta'(G)=n(G)$

由上节, $\alpha'(G)=\beta(G)$, 又$\alpha(G)+\beta(G)=\alpha'(G)+\beta'(G)=n(G)$, 于是$\alpha(G)=\beta'(G)$, 即最大独立集与最小边覆盖大小相等。