二部图匹配网络流.ppt

二部图&网络流二部图 2017-2-21 3 of 220 二部图定义设G =< V,E>为一个无向图,若能将 V分成 V 1和V 2 (V 1?V 2=V,V 1?V 2=?),使得 G 中的每条边的两个端点都是一个属于 V 1,另一个属于 V 2,则称 G 为二部图( 或称二分图、偶图等),称 V 1和V 2为互补顶点子集,常将二部图 G 记为<V 1,V 2,E >. ?又若 G是简单二部图, V 1中每个顶点均与 V 2中所有的顶点相邻,则称 G为完全二部图,记为 K r,s,其中 r =|V 1|,s =|V 2 |. 2017-2-21 图的矩阵表示 4 of 220 例二部图二部图 6v 4v 5v 1v 2v 3v完全二部图 K 3,3 2017-2-21 5 of 220 二部图的判别法?定理无向图 G =< V,E>是二部图当且仅当 G中无奇圈. 无向简单图的点覆盖集、点独立集、匹配 2017-2-21 7 of 220 点独立集与点独立数定义设G =< V,E>,V*?V. (1) (点)独立集 V*—— V*中顶点彼此不相邻(2) V*为极大点独立集—— V*中再加入任何顶点就不是点独立集(3) 最大点独立集——元素最多的点独立集(4) 点独立数——最大独立集中的元素个数,记为? 0 在图中,点独立数依次为 2, 2, 3. (1) (2) (3) 2017-2-21 8 of 220 点覆盖集与点覆盖数定义设G =< V,E >, V*?V. (1) V*是点覆盖集——?e?E,?v?V*,使 e与v关联(2) V*是极小点覆盖集—— V*的任何真子集都不是点覆盖集(3) 最小点覆盖集——顶点数最少的点覆盖集(4) 点覆盖数——? 0(G)——最小点覆盖的元素个数图中,点覆盖数依次为 3,4,7. 2017-2-21 9 of 220 点覆盖集与点独立集的关系? 0+? 0=n 点覆盖数+点独立数=点数 2017-2-21 10 of 220 匹配(边独立集)与匹配数(边独立数) 定义设G =< V,E >, E*?E, (1) 匹配(边独立集)E*—— E*中各边均不相邻(2) 极大匹配 E*—— E*中不能再加其他边了(3) 最大匹配——边数最多的匹配(4) 匹配数——最大匹配中的边数,记为? 1 上图中各图的匹配数依次为 3, 3, 4.