二部图匹配网络流ppt课件.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,32020/9/=<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,