0 前言
好久没看图论了,翻一翻做个笔记(似曾相识的前言)。
1 顶点覆盖定义
如果图G没有完美匹配,通过证明G没有M-增广路径就可以说明M是最大匹配。然而通过检查所有M-交错路径排除增广路径成本太高。我们只需要找出G中的某种结构以表明不可能有比M更大的匹配。
定义:图G的一个顶点覆盖是由一些顶点构成的集合Q⊆V(G),Q包含每条边上的至少一个端点,Q的所有顶点覆盖边集合E(G)
任意一个顶点不能覆盖匹配中的两条边,所以每个顶点覆盖的大小均不小于任何一个匹配的大小,因此找到相同大小的一个匹配和一个顶点覆盖即证明两者都是最优的,这一结果对二部图成立,对一般图不成立。
下图中的奇环,匹配与顶点覆盖两者最优值相差为1,事实上两者相差可以任意大。
2 柯尼希定理(König-Egeváry Theorem, min-max theorem, König[1931],Egeváry[1931])
描述:如果G是二部图,则G中最大匹配的大小等于G的最小顶点覆盖的大小
证明:G是一个X,Y-二部图,设Q是G的任意顶点覆盖,M是G的任意匹配,由于必须用不同的顶点来覆盖匹配中各条边,所以|Q|≥ |M|。
给定G的一个最小顶点覆盖Q,我们构造一个大小为|Q|的匹配证明上述不等式中等号总可以取到。
将Q划分为R=Q⋂X,T=Q⋂Y,令H和H’分别是由R⋃(Y-T)和T⋃(X-R)有诱导的子图,借助Hall定理,证明H有一个匹配将R浸润到Y-T中,而H‘有一个浸润T的匹配,由于H和H’不相交,因此这两个匹配可以合成G的一个大小为|Q|的匹配。
由于R⋃T是一个顶点覆盖,G没有从Y-T到X-R的边,对任何S⊆R,考虑NH(S),它存在于Y-T之中。如果|NH(S)|<|S|,则中Q中用NH(S)来替换S即可以得到一个更小的顶点覆盖,因为NH(S)覆盖到了所以关联S但未被T覆盖的边。
Q的最小性使得H中Hall条件成立,故H有一个浸润R的匹配,对H‘进行统一的论证可以得到一个浸润T的匹配。
注记 一个最小-最大关系是一个定理说明了某个最小化问题的答案和某个最大化问题之间等同,柯尼希定理定理说明了二部图中顶点覆盖和匹配间的这种关系。
References
Introduction to Graph Theory, Sencond Edition, Douglas B. West