29-匹配070101.ppt

《29-匹配070101.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、匹配信号处理中的数学方法第2-10讲上一讲内容的回顾图的平面嵌入平面图和非平面图平面图的必要条件：欧拉公式适用于简单图的欧拉公式推论平面图的充分必要条件-Kuratowski定理平面图着色与四色定理匹配支配集点覆盖集与独立集边覆盖集匹配最大匹配和完美匹配二部图中的匹配Hull定理支配集与支配数点支配点u受u支配的顶点集合支配数0=2u支配数0=1极小支配集最小支配集点独立集与独立数(点)独立集:点与点不相邻独立数0=3独立数0=2最大独立集极大独立集独立集与支配集的关系设G是无孤立点的简单无向图，则G的极大独立集都是极小支配集。证明：设V*是任意的极大独立集(i)V*

2、必是支配集。假设不是，则v0VG-V*,v0与V*中任何元素均不相邻，则V*⋃{v0}仍是独立集，矛盾。(ii)V*是极小的。设v‘是V*中任一元素，因为V*是独立集，V*-{v’}中任何元素都不能支配v',V*-{v'}不是支配集。注意：极小支配集未必是最大独立集(甚至未必是独立集)极小支配集不是独立集点覆盖与点覆盖数点覆盖边点覆盖数0=4点覆盖数0=3最小点覆盖极小点覆盖点覆盖与点独立集的关系设G是无孤立点的简单无向图，VG的真子集V*是点覆盖当且仅当V-V*是点独立集。证明：令V’=V-V*假设V'不是独立集，则存在u,vV',满足uvEG,注意：V‘=

3、VG-V*,即u,vV*,uv边不可能被V*所覆盖，矛盾。eEG,假设e=uv,因为V‘是点独立集，u,v中至少有一个不在V'中，不妨设uV',则uV*,V*是点覆盖。边覆盖与边覆盖数边覆盖点边覆盖数1=3极小边覆盖最小边覆盖匹配边独立集–匹配:边与边不相邻匹配数1=3匹配数1=4极大匹配最大匹配完美匹配M-饱和点M-饱和点最小边覆盖与最大匹配的关系(无孤立点的简单无向图中，最大匹配总是某个最小边覆盖的子集。)若M是图G中的最大匹配,对G中每个M-非饱和点，取一条与之相关联的边，构成边集NW=MN是G中的最小边覆盖若W1是图G中的最小边覆盖，若N1是为

4、了消除W1中的相邻边所需移去的最小的边集M1=W1-N1是G中的最大匹配最小边覆盖与最大匹配的关系证明W是最小边覆盖，M1是最大匹配．W显然是边覆盖，所以

5、W

6、1。注意：

7、M

8、=1,又因为M是最大匹配，N中不可能有一条边的两个端点都是M-非饱和点，

9、N

10、=n-21，

11、W

12、=

13、M

14、+

15、N

16、=n-1。而M1=W1-N1显然是匹配,

17、M1

18、1。因为W1是最小边覆盖，构造M1时，每移去一条边，恰好产生一个M1-非饱和点。注意：

19、W1

20、=1,M1-非饱和点数为n-2

21、M1

22、，

23、N1

24、=

25、W1

26、-

27、M1

28、=n-2

29、M1

30、,即1=n-

31、M1

32、。综上所述可得：1=n

33、-

34、M1

35、n-1=

36、W

37、1,于是：

38、W

39、=1且

40、M1

41、=1，即W是G中的最小边覆盖，且M1是G中的最大匹配。推论：1+1=n。由匹配决定的交错路定义：设M是G中一个匹配。若G中路径P中M与EG-M中的边交替出现，则称P为M-交错路(也可以是回路)；若P的起点与终点都是M-非饱和点，则称P是可增广交错路。可增广交错路最大匹配的特征M是G中最大匹配当且仅当G中不含M-可增广交错路。证明：设M是最大匹配。若G中含可增广路P，显然，MEP仍是匹配，且边数比M多1，矛盾。设G中不含可增广路，假设M'是G的一个最大匹配。设H是MM'边诱导子图。若H=,M=M',

42、即M是最大匹配。否则，因为M和M'均为匹配，H中不可能有3次或3次以上的顶点，H的每个连通分支只能是交错回路或交错路，在两种情况下，H中取自M和M'的边总是一样多(否则，M和M'中有一个含可增广路)，M是最大匹配。二部图中的完备匹配定义：设G是二部图，二部划分为，若G中的匹配M饱和V1中所有顶点，则称M为完备匹配。注意：完备匹配一定是最大匹配，但仅当

43、V1

44、=

45、V2

46、才是完美匹配。此图无完备匹配存在完备匹配的充分必要条件Hull定理：二部图G=(V1,V2,E),

47、V1

48、

49、V2

50、,存在完备匹配当且仅当V1中任意k个顶点至少与V2中的k个顶点相邻，其中k=1,

51、2,…

52、V1

53、。证明(必要性显然，只需证明充分性)：假设M是最大，但非完备匹配，则存在v0V1,是M-非饱和点。v0不可能是孤立点。考虑从v0出发的所有尽可能长的交错路，因为M是最大匹配，所有这样的交错路终点必在V1中(否则是可增广路)。令S为这些路上在V1中的点的集合，T是这些路上在V2中的点的集合，则S中的点只和T中的顶点相邻，但

54、S

55、=

56、T

57、+1,矛盾。V1V2v0完备匹配的一个充分条件二部图G=(V1,V2,E),若V1中每个顶点至少关联t条边，而若V2中每个顶点至多关联t条边，则G中存在