思路:先通过交错路和增广路的概念建立起处理最大匹配的工具,证明匹配最大的充要条件是图中没有增广路。然后证明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)$,即最大独立集与最小边覆盖大小相等。