二分图匹配

目录

  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)$即最大独立集与最小边覆盖大小相等