资源描述：
《图论偶图与匹配》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、偶图与匹配在实际应用中,有些如对策、二人对弈、工作分配等问题,例如有A,B,C,D四个人,有a,b,c,d,e五种工作,如果某人可以做某种工作,则它们之间连一直线.ADBDCDDD定义:令G=是无向图,如果可以将V划分成两个子集V,V,aDbDcDdDeD12V∩V=使得任何边(vφ,v)∈E,v∈V,v∈V,12iji1j2则称G是二部图,也称二分图或偶图.并称V,V是G的互补的12结点子集.偶图的特点每一条边都跨接在两个互补结点子集上，而结点子集内部任意两个结点都不邻接。完全偶图:令G=是以V,V为互补的结点子集的12偶图,如果V中的每个结点都与V中每个结点相邻接,
2、则12称G是完全偶图.如果
3、V
4、=m,
5、V
6、=n则G记作Km×n12m,n条边1DD21DD3aDDfaDDcDebDDe4DD34DD2KcDDdbDdDDf2,2K3,3而下面两个图不是偶图.1DD21DD21DD3D34DD35DD44DDD52K2,3V={1,3}V={2,4}?,V={1,3,4}?V={2,5}1212定理G=是偶图当且仅当它的所有回路的长度都是偶数.证明:必要性:假设G是个以V,V为互补的结点子集的二12部图,设任意长度为n的回路:vvv,…,vv,i0i1i2in-1i0假设vvv,…,v∈V,vvv,…,v∈V,i0i2i4in-21i1i3i
7、5in-12可见n-1是奇数,所以n是偶数.充分性:设G的每个回路长度均为偶数,a)设G是连通的.定义结点集合:V={v
8、v和某个固定结点v之间的距离为偶数}1iiV=V-V={v
9、v和某个固定结点v之间的距离为奇数}21ii下面证明E中任何边,其端点分别属于V和V.12(用反证法)假设有一条边(v,v)∈E,使得v∈V,iji1v∈Vj1由V的定义可知:结点v到v有最短路长为m(是偶数),v到1iv有最短路长为n(是偶数),所以再加上边(v,v),就得到jij一条长度为(m+n+1)的回路,可是此回路长为奇数,与已知条件矛盾.所以v和v不能属于同一个结点子集.ij类似地,假设有一条边(v
10、,v)∈E,ijvDDvij使得v∈V,v∈V,由V的定义可i2j22mn知:结点v到vi有最短路长为m(是D奇数),v到v有最短路长为n(是奇数),vj所以再加上边(v,v),就得到一条ij长度为(m+n+1)的回路,可是此回路长为奇数,与已条件矛盾.所以v和v不能属于同一个结点子集.ijG是个以V,V为互补的结点子集的二部图,12b)如果G不是连通图时,可以对G的每个分图,重复上述证明,得到同样结论.最后得G必是二部图.¾匹配在无向图G＝(V，E)中，对边集E的任一子集M，如果M中的任意两条边都不相邻，则称M为图G的一个匹配(或对集)。所谓两条边不相邻即两条边无公共端点。¾G中属于M的
11、边称为匹配边，匹配边的两个端点互为匹配点，匹配边的所有结点称为关于M饱和点,否则称为非饱和点。匹配M的基数(即M中边的数目)记作
12、M
13、.¾设M是G的一个匹配，若不存在另一匹配M’，满足
14、M’
15、＞
16、M
17、,则称M是G的最大基数匹配。若G的每个结点都是M饱和点，则称M是G的完美匹配。显然，完美匹配一定是最大基数匹配。¾设M是图G的一个匹配，若G中存在一条基本路径P，路径的边是由属于M的匹配边和不属于M的非匹配边交替出现组成，则称P为交替路。苦P的两个端点都是M的非饱和点，则称这条交替路为可增广路。¾设M={(v2,v3)(v5,v6)(v7,v8)}(a)p1=v1v2v3v5为交替路(b)p2
18、=v4v5v6v7v8v1为可增广路v2v2v3v3v1v1v1v5v5v4v4v8v8v6v6v7v7(a)(b)¾如果将可增广路P上的匹配边改为非匹配边，2非匹配边改为匹配边，不在P上的匹配边保持2不变，则匹配变为M'，可以看出M'的边数比M的边数增加1，即M'=M+1¾由M变为M’的变换，实际是对M和E(P2)进行环和的结果，即M'=M⊕E(P2)定理5.2(Berge,1957)图G的匹配M是最大基数匹配当且仅当G不含M可增广路。证：=>如果G含有M可增广路P，可构造一个新的匹配,M'=M⊕E(P2),,因而M就不是最大基数匹配。M'>M<=如果M不是最大基数匹配，往明G必含有M可
19、增广路。令M'是G的最大基数匹配，设G'=(V,M⊕M')则G’是G的生成子图，G’的边集是M和M’中不相同的边的并集而且可以得到(1)G'的边集中含M'的边的数目比含M的边的数目多(2)G’的任一结点最多关联M'的一条边或最多关联M的一条边。由(2)可知G’的任一结点的次数或者是0，不然就是1或2，因此G’的每个连通分支或者是由M’和M的边交替出现构成的回路，或者是由M’和M的边交替出现构成的交替路，由于G’中M’的边
