0 前言
好久没看图论了,翻一翻做个笔记。
1 匹配的定义
图G的一个匹配上由一组没有公共端点的的,不是圈的边构成的集合,与匹配M关联的那些顶点是被M-浸润的,而其余点是未被浸润的。图G的一个完美匹配就是浸润了所有顶点的一个匹配。
2 最大匹配
一个匹配是由若干条边构成的集合,故其大小就是边的条数。
2.1 极大匹配
图G中的一个极大匹配是不能通过添加边来使其变大的匹配。一个最大匹配是图G的所有匹配中边数达到最大值的匹配。极大匹配不等于最大匹配。
2.2 M-交错路径与M-增广路径
给定图G的一个匹配M,如果一条路径的边交替出现在M和不出现在M中,则称之为一条M-交错路径。两个端点都没有被M-浸润都M-交错路径称为M-增广路径。
给定一条M-增广路径P,可以用P中不属于M的边替换P中属于M的边,将得到一个新的更大的匹配M’,因此不存在增广路径是最大匹配的特性。Berge定理将归纳这一点,看Berge定理前需要先了解对称差与偶环。
2.3 引理:在两个匹配的对称差中,任何分量或是一条路径,或是一个偶环。
证明:令M和M’上两个匹配且F=MΔM’。由于M和M’均是匹配,因此F的任意顶点至多与M和M’中的每个匹配的一条边关联,于是F的每个顶点至多关联到两条边。由于Δ(F)<=2,F的任意一个分量是一个路径或一个环。而且F的路径或环的边交替出现于M-M’和M’-M,所以每个环有偶数条边,一半来自M-M’,一半来自M’-M。
2.4 Berge定理
定理:图G的一个匹配M是最大匹配当且仅当G中没有M-增广路径
证明:
对于充分性和必要性,我们均证明其倒置命题,即图G有比M更大的匹配当且仅当G中有一条M-增广路径。已知M-增广路径可以用来产生比M更大的匹配。
反过来,令M’是G的比M更大的一个匹配,我们来构造一条M-增广路径,令F=MΔM’,由对称差引理可知,F由一些路径和一些偶环组成,且每个偶环有相同数目的边分别来自M’和M。由于|M’| > |M|, 所以F必有一个分量,其中来自M’的边,多于来自M的边;这个来自M’的边,必定是以M’中的边开始和结束的一条路径。所以它必是G中的一条增广路径。
3 Hall匹配条件
考虑一个X,Y-二部图(即将二部分为X,Y的二部图),并在其中找出浸润X的一个匹配。
如果一个匹配M浸润X,则对任意S⊆X,至少存在S集合的大小个也就是|S|个顶点,在S中有相邻顶点。用N(S)来表示与S中顶点相邻的顶点构成的集合,则|N(S)|≥|S|是上述问题的一个必要条件。
条件“对任意S⊆X,|N(S)| ≥ |S|”即是Hall条件。这个必要条件也是充分的。
3.1 Hall定理
定理: X,Y-二部图中有一个浸润X的匹配,当且仅当对任意S⊆X,|N(S)| ≥ |S|。
证明:
必要性 与S匹配的|S|个顶点必在N(S)中。
充分性 为证明Hall定理也是充分的,我们证明其倒置命题。设M是G的一个最大匹配但M没有浸润X,由此我们要找出一个集合S⊆X满足|N(S)| < |S|,令u∈X是未被M浸润的一个顶点。在从u出发通过G的M-交错路径可以到达的那些顶点中,令位于X中的顶点构成S,而位于Y中的顶点构成T。u∈S。
断言M匹配T和S-{u}。从u开始的M-交错路径沿着不属于M的边抵达Y,并沿着M中的边回到X。因此,S-{u}的每个顶点,从T的一个顶点通过M的一条边到达。由于没有M-增广路径,故T的任意顶点是被浸润的;于是每一条抵达y∈T的M-交错路径通过M扩展到S的一个顶点,所以M中相应的边产生了一个从T到S-{u}的双射,故有|T|=|S-{u}|。
由T和S-{u}之间的匹配,可以得出T⊆N(S),其实T=N(S),假设y∈Y-T有个相邻顶点u∈S,因为u是未被浸润的,而S中其余顶点通过M与T匹配,所以边uy∉M。将边uy添加到抵达u的一条M-交错路径上后,得到一条抵达y的M-交错路径。这同y∉T矛盾,因此uy不存在。
由T=N(S),我们证明了|N(S)| = |T| = |S -1| <|S|,完成了对倒置命题的证明。
References
Introduction to Graph Theory, Sencond Edition, Douglas B. West