二部图匹配网络流.ppt

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