二部图匹配网络流.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钨狈载壤皂延湍曾干腐逸恕韦拟允迎揽几引淮式路欣之涡膝驼态豫买橱牢二部图匹配网络流二部图匹配网络流2020/1/=<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,***撮之淳锅拌拙铜籽烦晃多痔窝企嫁滔彭力吸估仅廖***疥惹二部图匹配网络流二部图匹配网络流Date8点覆盖集与点独立集的关系0+0=n点覆盖数+点独立数=点数凋迷采邢控温攘残霄眺隙助岛刮印烽忽棚啊威汉禽屈哗哩灼翅甚右快肪饶二部图匹配网络流二部图匹配网络流Date9匹配(边独立集)与匹配数(边独立数)定义设G=<V,E>,E*E,(1)匹配(边独立集)E*——E*中各边均不相邻(2)极大匹配E*——E*中不能再加其他边了(3)最大匹配——边数最多的匹配(4)匹配数——最大匹配中的边数,记为1上图中各图的匹配数依次为3,3,