二分图进阶

在二分图的各种证明中,递归增广的证明思想非常普遍。

最大匹配

边匹配是一个没有共用顶点的边的集合。

Hall定理:二分图的左侧的点能够全部匹配上的充要条件是,对于左侧的点的任意一个子集SS,都至少直接连上了S\left|S\right|个右边的点(Marriage Condition)。

证明

  • 必要性显然。
  • 充分性的证明过程,就是匈牙利算法寻找增广路的过程。不失一般性地,设左边点数小于等于右边点数且左边的点满足MC。考虑左边一个没有被匹配上的点,根据Hall定理,它至少连到了右边的一个点。如果这个点没有匹配上,那就可以匹配上;否则把右边这个点的匹配点加入左边的集合,由MC知至少连到了右边的两个点,任选一个新点,再类似讨论。一旦发现一个没有匹配上的右边的点,就可以沿着增广路增广。MC会使讨论持续进行下去,直到找到未匹配点(成功)或图中没有点(矛盾)。

做题时看到了一个扩展版的Hall定理,不知道在不在原论文里面:

扩展Hall定理:设Γ(S)\Gamma(S)为左边的点的子集SS通过边直接连接到右边的点的集合,则当左边不存在完备匹配时,左边不在最大匹配上的点数等于maxSSΓ(S)\max_{S}\left|S\right|-\left|\Gamma(S)\right|

证明:设F(S)=SΓ(S)F(S)=\left|S\right|-\left|\Gamma(S)\right|

  • 显然未匹配点数大于等于maxSF(S)\max_{S}F(S)。只需证明未匹配点数能取到F(s)F(s)这个下界。
  • 设点集SS取到了这个最大值。不在SSΓ(S)\Gamma(S)中的点一定满足MC,否则可以把不满足MC的子集加进来得到一个差值更大的点集。故我们只在SΓ(S)S\cup\Gamma(S)的诱导子图上讨论。
  • 取一个集合SS'满足F(S)=maxSF(S)F(S')=\max_SF(S)SS'极小(即不存在SS'的子集SS''使得F(S)F(S)F(S'')\geq F(S')),则删除SS'中的任意一个点都会导致F(S)F(S')变化。根据假设,F(S)F(S')只能变小。而S\left|S'\right|减少一,Γ(S)\left|\Gamma(S')\right|又不可能增大,所以只能是Γ(S)\Gamma(S')不变,F(S)F(S')减少一。钦定xx不匹配,在删去xx的子图GG'maxSF(S)=F(S)1\max_SF(S)=F(S')-1。递归讨论得知GG'左边未匹配的点数可以取到F(S)1F(S')-1这个下界,故在当前图中F(S)F(S')这个下界也能取到。

习题:arc076_d,虽然这题不用这个定理也能做。

最大独立集

独立集是两两没有连边的点集,最大独立集和最大团一起是NP-Hard的。但是二分图中的最大独立集数可以通过匹配数来求解。

本来以为上界不太好证,其实是显然:匹配的M\left|M\right|条边中,每条边至少有一个点不在最大独立集中,故最大独立集VM\leq\left|V\right|-\left|M\right|

考虑我们是否能够达到这个上界。把所有不一定在最大匹配上的点都划分在独立集里面,这些点连向的点都不在独立集里面。剩下的点的诱导子图一定是有完美匹配的,任选一边就好。

最小点覆盖

点覆盖是一个顶点集合,每条边都至少有一个端点在该集合中。

König定理:在二分图中,最小点覆盖大小=最大匹配数。

证明:对二分图染色。所有不在最大匹配中的点都不会被选择。所有不被选择的点连向的所有的点都会被选择,所有被选择的点的匹配点都不会被选择。没有被染色的点,就随便选择一个,继续染色。由于最大匹配后不再有增广路,所以染色不会出现矛盾。这样染完色就得到了一个大小为最大匹配数的点覆盖,故最小点覆盖\leq最大匹配。又最大匹配中的每一条边都需要至少一个顶点来覆盖它,而没有一个顶点能够覆盖两条匹配边,故最小点覆盖\geq最大匹配。

其实二分图中最小点覆盖也可以是最大独立集的补集。每条边只能连接最多一个最大独立集中的点,也就是至少连接一个最大独立集的补集的点。

最小边覆盖

//todo

稳定婚姻系统

UOJ41
nnnn女匹配,每个人都有对异性的独特排名。求一个不会有人出轨的匹配方案。两个人会出轨当且仅当他们喜欢对方都胜过喜欢自己的配偶。

这个是GS稳定婚姻系统,GS不仅给出了必定存在稳定婚姻系统的证明,也提供了一个构造稳定婚姻系统的方法。

想起一二年级的时候看到过关于男女匹配、学校匹配的最佳方法,大意是:在每一轮中,每个男生在剩下的女生中选择自己最心仪的女生,然后当前有爱慕者的女生选择出一个自己最喜欢的,两人牵手成功,没有被选中的男生和没有爱慕者的女生(真凄凉)进入下一轮。

这样,对于某一个男生,他每次被拒绝的时候,拒绝他的女生一定是有了一个更好的对象,所以他不可能与那些拒绝过他的女生出轨;他还没有问过的女生,在他心目中的排名没有他当前拥有的对象的排名高,所以那个男生也不可能和她们出轨。这个方法的思路是单方面满足需求的,男生拥有比较大的主动权。

另一种最近学习到的本质相同的做法,也不是很麻烦,但是印象没有上面那个深刻。把所有男生加入队列,处理一个男生的时候,找最喜欢的且没有拒绝过他的女生,如果那个女生没有匹配,或者当前匹配在女生的心目中比他差,那就匹配上了,把原来匹配的那个男生(如果有的话)扔回队列里。这个思想比较像匈牙利。

选与不选相关

最大匹配

给定一张二分图,求每个点是否一定在最大匹配上。

题目大意
先匹配一下。每一个未匹配的点,都不一定在最大匹配上(显然)。不一定在最大匹配上的点,连到的匹配点的匹配点也不一定在最大匹配上(换一个匹配边即可)。

最小点覆盖

EZOJContests/1181/C
给定一张二分图,求每个点是否

  1. 一定在最小点覆盖上
  2. 一定不在最小点覆盖上

算法讨论
先匹配一下。设当前的匹配方案为A。取A中一个未匹配点P1P_1,考虑另一种匹配方案B,有以下讨论:

  • PiP_i在B中没有匹配:那么PiP_i不在B的最小点覆盖集上;
  • PiP_i在B中有匹配,设匹配点为QiQ_iQiQ_i在A中必有匹配边,否则P1Q1...PiQiP_1\rightarrow Q_1\rightarrow...\rightarrow P_i\rightarrow Q_i为A中一条增广路,与A为最大匹配矛盾;设QiQ_i在A中的匹配点为Pi+1P_{i+1},递归讨论得知Pi+1P_{i+1}不在B的最小点覆盖集上,而又存在QiPi+1Q_i\rightarrow P_{i+1}这条边,为了覆盖,QiQ_i必须在B的最小点覆盖集上,因此PiP_i不在B的最小点覆盖集上。

总结起来就是说,现在没有匹配的点,永远别想进入最小点覆盖集。

根据上面的论述可以得到一个染色方法:

  • 不在匹配中的点,也一定不能在最小点覆盖上;
  • 不能在最小点覆盖上的点,连到的所有点都必须在最小点覆盖上;
  • 必须在最小点覆盖上的点,匹配点都不能在最小点覆盖上;
  • 剩余的点都是可以在最小点覆盖上,也可以不在。

无遗漏:未被染色的点的诱导子图有完美匹配,因此这些点可以选也可以不选。

avatar
Kerry Su