第18章+支配集+覆盖集独立集配与着色

《第18章+支配集+覆盖集独立集配与着色》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学DiscreteMathematics7/23/20211DiscreteMath.,ChenChen第十八章支配集、覆盖集、独立集、匹配与着色主要内容支配集、点覆盖集与点独立集边覆盖与匹配二部图中的匹配点着色地图着色与平面图的点着色边着色7/23/20212DiscreteMath.,ChenChen18.1支配集、点覆盖集与点独立集支配集与支配数定义18.1设G=，V*V.(1)V*为支配集——viVV*,vjV*，使得(vi,vj)E(2)V*为极小支配集——V*的真子集不是支配集(3)最小支

2、配集——元素最少的支配集(4)支配数0(G)——最小支配集中的元素个数7/23/20213DiscreteMath.,ChenChen极小与最小支配集之间的关系最小支配集为极小支配集，但反之不真.另外，极小支配集与最小支配集都可能不惟一.又易知完全图、轮图、星形图的支配数均是1.图中，(1),(2),(3)(彼得松图)的支配数分别为1，2，3.请各找出一个最小支配集.(1)(2)(3)7/23/20214DiscreteMath.,ChenChen点独立集与点独立数定义18.2设G=，V*V.(1)点独立集V*——V*中

3、顶点彼此不相邻(2)V*为极大点独立集——V*中再加入任何顶点就不是点独立集(3)最大点独立集——元素最多的点独立集(4)点独立数——最大点独立集中的元素个数，记为0在图中，点独立数依次为2,2,3.(1)(2)(3)7/23/20215DiscreteMath.,ChenChen极大独立集与极小支配集定理18.1设G=中无孤立点，则G的极大点独立集都是极小支配集.证明线索：(1)设V*为G的极大点独立集，证明它也是支配集.vVV*，必vV*，使(v,v)E，否则v0VV*不与V*中任何顶点相邻，则V

4、*{v0}仍为点独立集，这与V*是极大点独立集矛盾.(2)证V*是极小支配集.只需证V*的真子集不是支配集.特别注意，定理18.1其逆不真.7/23/20216DiscreteMath.,ChenChen点覆盖集与点覆盖数定义18.3设G=,V*V.(1)V*是点覆盖集——eE，vV*，使e与v关联(2)V*是极小点覆盖集——V*的任何真子集都不是点覆盖集(3)最小点覆盖集(或最小点覆盖)——顶点数最少的点覆盖集(4)点覆盖数——0(G)——最小点覆盖的元素个数图中，点覆盖数依次为3，4，7.7/23/2021

5、7DiscreteMath.,ChenChen点覆盖集与点独立集的关系定理18.2设G=无孤立点，V*V，则V*是点覆盖当且仅当为点独立集证必要性.若vi,vj相邻，即(vi,vj)E，则V*中顶点不能覆盖(vi,vj)，这是矛盾的.充分性.由于是点独立集，因而eE，e的两个端点至少一个在V*中.推论设G为n阶无孤立顶点图，则V*是极小(最小)点覆盖当且仅当是极大（最大）点独立集，从而有0+0=n7/23/20218DiscreteMath.,ChenChen18.2边覆盖集与匹配边覆盖集与边覆盖数定义18.

6、4设G=，E*E，(1)E*为边覆盖集——vV，eE，使得v与e关联(2)E*为极小边覆盖——E*的真子集不是边覆盖(3)最小边覆盖——边数最少的边覆盖(4)边覆盖数1——最小边覆盖中元素个数图中各图的边覆盖数依次为3,4,5.请各找出一个最小边覆盖.7/23/20219DiscreteMath.,ChenChen匹配(边独立集)与匹配数(边独立数)定义18.5设G=,E*E，(1)匹配(边独立集)E*——E*中各边均不相邻(2)极大匹配E*——E*中不能再加其他边了(3)最大匹配——边数最多的匹配(

7、4)匹配数——最大匹配中的边数，记为1上图中各图的匹配数依次为3,3,4.7/23/202110DiscreteMath.,ChenChen关于匹配中的其他概念定义18.6设M为G中一个匹配.(1)vi与vj被M匹配——(vi,vj)M(2)v为M饱和点——有M中边与v关联(3)v为M非饱和点——无M中边与v关联(4)M为完美匹配——G中无M非饱和点(5)M的交错路径——从M与EM中交替取边构成的G中路径(6)M的可增广交错路径——起、终点都是M非饱和点的交错路径(7)M的交错圈——由M与EM中的边交替出现构成的G中圈上图中，

8、只有第一个图存在完美匹配7/23/202111DiscreteMath.,ChenChen可增广路径及交错圈设红色边在匹配M中，绿色边不在M中，则图(1)中的两条路径均为可增广的交错路径；(2)中的全不是可增广的交错路径