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

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

ID:5334429

大小:255.58 KB

页数:16页

时间:2017-12-08

图论讲义第3章-匹配问题_第1页
图论讲义第3章-匹配问题_第2页
图论讲义第3章-匹配问题_第3页
图论讲义第3章-匹配问题_第4页
图论讲义第3章-匹配问题_第5页
资源描述:

《图论讲义第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的每个连通分支都是完全图(记为命题A,另证)。***由(*)式,O(GU)≤U,即G−U的奇分支个数最多是U。但这样一来,G就有一个完美匹配:**GU的各奇分支中的一个顶点和U的一个顶点配对;U中余下的顶点

23、以及GU的各分支中余下的顶点在本分支内配对(由于各分支及U都是完全图)。**GU的奇分支GU的偶分支………U2*这与G无完美匹配矛盾。证毕.**命题A的证明:在上述充分性证明的条件下,当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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。