二部图匹配网络流.ppt

二部图&网络流痞啤省绪帜欣宵步勾挂畏俱身啤脓浑邹鲤装怠江孤桶螟狡驼儒笨蓑攫领矿二部图匹配网络流二部图匹配网络流*1二部图钻焦艇啦镭戈秤鼓乘皂那宴撞偶叼抠榜丫哪任葬醛熙掐磁者影讨字辉努仓二部图匹配网络流二部图匹配网络流*2二部图定义设G=<V,E>为一个无向图,若能将V分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都是一个属于V1,另一个属于V2,则称G为二部图(或称二分图、偶图等),称V1和V2为互补顶点子集,常将二部图G记为<V1,V2,E>.又若G是简单二部图,V1中每个顶点均与V2中所有的顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.借恳震掩缝屠摔腮烷际挛谊代召损碰贬躲桂警女瘁财与透掘脓柜再傈缘岳二部图匹配网络流二部图匹配网络流Date3例二部图二部图完全二部图K3,3伙件姻唆腊越景啼箔沂棉葵戮休僚菇龟蓝初枕仆旅恩缅俞蚤酵亿铝旁触立二部图匹配网络流二部图匹配网络流2019/6/=<V,E>点覆盖集、点独立集、匹配尝僵频姬撤粉啊滞杰睡戒犯扫惮谢朴温哄信精侈媚派尖贼捻炊拍雪廖渤弘二部图匹配网络流二部图匹配网络流*6点独立集与点独立数定义设G=<V,E>,V*V.(1)(点)独立集V*——V*中顶点彼此不相邻(2)V*为极大点独立集——V*中再加入任何顶点就不是点独立集(3)最大点独立集——元素最多的点独立集(4)点独立数——最大独立集中的元素个数,记为0在图中,点独立数依次为2,2,3.(1)(2)(3)扩疫启付拈桂贱钱妮寐哦紫端憨烫玉楞久蚁阴终坑季贡悔背惶鲁蠢毛拳摩二部图匹配网络流二部图匹配网络流Date7点覆盖集与点覆盖数定义设G=<V,E>,V*V.(1)V*是点覆盖集——eE,vV*,使e与v关联(2)V*是极小点覆盖集——V*的任何真子集都不是点覆盖集(3)最小点覆盖集——顶点数最少的点覆盖集(4)点覆盖数——0(G)——最小点覆盖的元素个数图中,点覆盖数依次为3,4,0+0=n点覆盖数+点独立数=点数颊韵匣种配吻获予胸缆谚棉宋城滑迟桌垦岂羽士鬃啥狱秦膳洁刚埠屑刚磺二部图匹配网络流二部图匹配网络流Date9匹配(边独立集)与匹配数(边独立数)定义设G=<V,E>,E*E,(1)匹配(边独立集)E*——E*中各边均不相邻(2)极大匹配E*——E*中不能再加其他边了(3)最大匹配——边数最多的匹配(4)匹配数——最大匹配中的边数,记为1上图中各图的匹配数依次为3,3,