二部图匹配网络流.ppt

二部图&网络流
6/10/2018
1
二部图
6/10/2018
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|.
6/10/2018
3
例二部图
二部图
完全二部图
K3,3
6/10/2018
4
图的矩阵表示
二部图的判别法
定理无向图G=<V,E>是二部图当且仅当G中无奇圈.
6/10/2018
5
无向简单图的点覆盖集、点独立集、匹配
6/10/2018
6
点独立集与点独立数
定义设G=<V,E>,V*V.
(1) (点)独立集V*——V*中顶点彼此不相邻
(2) V*为极大点独立集——V*中再加入任何顶点就不是点独立集
(3) 最大点独立集——元素最多的点独立集
(4) 点独立数——最大独立集中的元素个数,记为0
在图中,点独立数依次为2, 2, 3.
(1) (2) (3)
6/10/2018
7
点覆盖集与点覆盖数
定义设G=<V,E>, V*V.
(1) V*是点覆盖集——eE,vV*,使e与v关联
(2) V*是极小点覆盖集——V*的任何真子集都不是点覆盖集
(3) 最小点覆盖集——顶点数最少的点覆盖集
(4) 点覆盖数——0(G)——最小点覆盖的元素个数
图中,点覆盖数依次为3,4,7.
6/10/2018
8
点覆盖集与点独立集的关系
0+0=n点覆盖数+点独立数=点数
6/10/2018
9
匹配(边独立集)与匹配数(边独立数)
定义设G=<V,E>, E*E,
(1) 匹配(边独立集)E*——E*中各边均不相邻
(2) 极大匹配E*——E*中不能再加其他边了
(3) 最大匹配——边数最多的匹配
(4) 匹配数——最大匹配中的边数,记为1
上图中各图的匹配数依次为3, 3, 4.
6/10/2018
10