图论讲义第3章-匹配问题

《图论讲义第3章-匹配问题》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第三章匹配理论§3.1匹配与最大匹配定义3.1.1设G是一个图,M⊆E(G)，满足:对∀e,e∈M，e与e在G中不相邻，则ijij称M是G的一个匹配。对匹配M中每条边e=uv，其两端点u和v称为被匹配M所匹配，而u和v都称为是M饱和的(saturatedvertex)。注:每个顶点要么未被M饱和,要么仅被M中一条边饱和。定义3.1.2设M是G的一个匹配,若G中无匹配M′,使得

2、M′

3、>

4、M

5、,则称M是G的一个最大匹配；如果G中每个点都是M饱和的,则称M是G的完美匹配(Perfectmatching).显然,

6、完美匹配必是最大匹配。例如，在下图G1中，边集{e1}、{e1,e2}、{e1,e2,e3}都构成匹配，{e1,e2,e3}是G1的一个最大匹配。在G2中，边集{e1,e2,e3,e4}是一个完美匹配，也是一个最大匹配。e1e3e2e1e2e3e4G1G2定义3.1.3设M是G的一个匹配,G的M交错路是指其边M和E(G)M中交替出现的路。如果G的一条M交错路(alternatingpath)的起点和终点都是M非饱和的，则称其为一条M可扩展路或M增广路(augmentingpath)。定理3.1.1(Ber

7、ge,1957)图G的匹配M是最大匹配的充要条件是G中不存在M可扩展路。证明:必要性:设M是G的一个最大匹配。如果G中存在一个M可扩展路P,则将P上所有不属于M的边构成集合M′。显然M′也是G的一个匹配且比M多一条边。这与M是最大匹配相矛盾。充分性:设G中不存在M可扩展路。若匹配M不是最大匹配，则存在另一匹配M′,使

8、M′

9、>

10、M

11、.令H=G[M⊕M′]，(M⊕M′=M∪M′−M∩M′称为对称差)。则H中每个顶点的度非1即2(这是因为一个顶点最多只与M的一条边及M′的一条边相关联)。故H的每个连通分支要么是

12、M的边与M′的边交替出现的一个偶长度圈，要么是M的边与M′的边交替出现的一条路。由于

13、M′

14、>

15、M

16、，H的边中M′的边多于M的边，故必有H的某个连通分支是一条路，且始于M′的边又终止于M′的边。这条路是一条M可扩展路。这与条件矛盾。证毕。1§3.2完美匹配定义3.2.1图G的奇分支：G的含有奇数个顶点的连通分支。用O(G)表示G的奇分支的个数。定理3.2.1(Tutte,1947)图G有完美匹配的充分必要条件是对∀S⊂V(G)，O(GS)≤

17、S

18、。证明（Lovász,1973）必要性：设图G有完美匹配M。

19、对∀S⊂V(G)，若GS无奇分支，则O(GS)=0；否则，设G,G,",G是GS的所有奇分支。注意每个G中至少有一个顶12ki点u在M下与S中的某个顶点v配对（i=1,2,",k），（因G是奇分支，M是完美匹配）。iii故O(GS)=k=

20、{v,v,",v}

21、≤S。12k奇分支偶分支u1u2…uk…G1G2Gkv2…vk…v1S充分性（反证法）：设G满足：对∀S⊂V(G)，O(GS)≤S，但G没有完美匹配。首先，取S=φ，知O(G)=0，故V(G)是偶数。现在，给G添加边以获得一个没有完美匹配而有

22、尽***可能多的边的图G。因G是G的生成子图，故对∀S⊂V(G)，GS是GS的生成子图，从而*O(GS)≤O(GS)≤S.（*）*令U={uu∈V(G),d*(u)=ν−1}.G***若U=V(G)，则G是偶数阶完全图，有完美匹配。这与G的性质矛盾。因此，**U≠V(G)，可以证明，此时GU的每个连通分支都是完全图（记为命题Ａ，另证）。***由（*）式，O(GU)≤U，即G−U的奇分支个数最多是U。但这样一来，G就有一个完美匹配：**GU的各奇分支中的一个顶点和U的一个顶点配对；U中余下的顶点

23、以及GU的各分支中余下的顶点在本分支内配对（由于各分支及U都是完全图）。**GU的奇分支GU的偶分支………U2*这与G无完美匹配矛盾。证毕.**命题Ａ的证明：在上述充分性证明的条件下，当U≠V(G)时，GU的每个连通分支都是完全图。*用反证法证明：若不然，设GU中某个连通分支G不是完全图，则V(G)≥3。必存在iix,y,z∈V(G)，使得xy,yz∈E(G)，且xz∉E(G)。由于y∉U，故必有与y不相邻的顶iii**点，即必存在w∈V(GU),使得yw∉E(G)。ywzx…GiU***由于G

24、是不含完美匹配的极大图，所以G+xz和G+yw都含有完美匹配，分别设为M和1*M。用H表示G∪{xz,yw}中由M⊕M导出的子图。由于对∀u∈V(H)，d(u)=2或212H0（由M和M都是完美匹配知），故H的每个非平凡连通分支都是其边在M和M中交替出1212现的偶长度圈。下分两种情形：(1)xz和yw分别在H的不同分支中。设yw在H的某个圈C上，则M在C上的边连同1**M不在C上的边构成G的一个完美匹配。这与G