图论讲义第5章-支配集

《图论讲义第5章-支配集》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第五章支配集、独立集、覆盖集和Ramsey数本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的图均为简单图。§5.1支配集、点独立集、点覆盖集一、支配集(Dominationset)定义5.1.1设D⊆V(G)，若对∀u∈V(G)，要么u∈D，要么u与D中的某些顶点相邻，则称D为图G的一个支配集。如果一个支配集的任何真子集都不是支配集，则称它为极小支配集。图G的含顶点最少的支配集称为最小支配集。最小支配集的顶点个数称为G的支配数，记为γ()G或γ。例如，在下图中，D={v}，D={v,v,v}，D={v,v,v,v}都是G的支配集，00

2、114721356前两个是极小支配集，D是最小支配集。γ(G)=1。0v1v2vv8v03v7v4v6v5G注：（1）最小支配集必是一个极小支配集，反之不然。（2）任一支配集必含有一个极小支配集。（3）极小支配集不唯一，最小支配集一般也不唯一。（4）对二部图G=(X,Y)，X和Y都是支配集。**（5）若图G有完美匹配M，则从M中每边取一个端点构成的顶点集是一个支配集。定理5.1.1设图G中无孤立顶点，则存在支配集D，使得DVGD=()−也是一个支配集。证明：无妨设G是连通图。于是G有生成树T。任取v∈V(G)。令0D={v

3、v∈V(G)且d(v,v)＝偶数}，T

4、0则DVGDvvVG=−()=∈{

5、()且d(v,v)＝奇数}，且D和D都是支配集。证毕。T0定理5.1.2设图G无孤立顶点，D是一个极小支配集，则DVGD=()−也是一个支配集。111证明（反证法）：若不然，存在v∈D，它与D中所有顶点都无边相连，但它又不是孤立顶011点，故必与D中顶点连边，因此D−v仍是支配集。这与D是极小支配集矛盾。证毕。1101推论5.1.1设图G中无孤立顶点。对G的任一个极小支配集D，必存在另一个极小支配集D，12使得D∩D=φ。12证明：由定理5.1.2，DVGD=−()也是一个支配集，且D∩D=φ。D中必含有一个极1111小支配集

6、D。显然D∩D=φ。证毕。2121定理5.1.3图G的支配集D是一个极小支配集当且仅当D中每个顶点v满足下列条件之一：（1）存在uVGD∈−()使得Nu()∩D={}v；（2）Nv()∩D=φ。证明：充分性：设D是G的一个支配集。对D中任一个顶点v，因v满足上述条件之一，故要么与v相邻的某个顶点不能被Dv−{}支配，要么v自己不能被Dv−{}支配，可见，Dv−{}不再是支配集。这表明D是极小支配集。必要性：设D是G的一个极小支配集，则对D中任一个顶点v，Dv−{}不再是支配集。因此在Dv−{}之外存在顶点u，它不与Dv−{}中任何点相邻。如果uv=，则说明v不与

7、D中任何点相邻，即Nv()∩D=φ；如果uv≠，则因D是支配集，故u必与v相邻，但不与D中其它点相邻，即Nu()∩D={}v。证毕。定理5.1.4设G是无孤立顶点的图，则G必有最小支配集D满足：对∀vD∈，∃∈−uGD使得Nu()∩D={}v。证明：用反证法。在G的全部最小支配集中，设D为使得导出子图G[D]含边数最多的一个。假定定理结论不真，即∃vD∈，使得对∀uGD∈−都有Nu()∩D≠{}v。由定理5.1.3，Nv()∩D=φ，即D中所有其它点都不与v相邻。而上式表明，GD−中每个点要么不与v相邻，要么既与v相邻也与D中另外某些点相邻。因G无孤立点，故v在

8、GD−中必有某个邻点w，令DDvw=−({}){∪}，则D也是G的一个最小支配集，但其导出子11图G[D1]含的边数比G[D]中多。这与D的取法矛盾。证毕。以下是关于支配数的几个估计式。υ定理5.1.5如果图G无孤立顶点，则γ(G)≤。2证明：设D是G的一个极小支配集，则由定理5.1.2，V(G)−D也是G的支配集。因此，υγ(G)≤−min{

9、D

10、,

11、V(G)D

12、}≤。2证毕。1ln(1)++δ定理5.1.6(Arnautov1974,Payan1975)设G是一个最小度为δ图，则γ(G)≤υ。1+δ证明：对G的任一非空顶点子集SV⊆(G)，用U表示未被S中顶

13、点支配的所有顶点之集。∗∗对∀∈vVG()，用Nv()表示顶点v及其所有邻点组成的集合，即NvNvv()=(){}∪。由∗于U中每个顶点至少有k个邻点，故∑

14、()Nv

15、

16、

17、≥+U(1δ)。从而在VGS()−中至少有一vU∈

18、

19、(1Uδ+)个顶点x，它在求和过程中至少被重复计算次。(否则，若VGS()−中每个点被υ

20、

21、(1Uδ+)∗

22、

23、U重复计算都少于次，则∑

24、()Nv

25、(

26、<υδδ−⋅S

27、)(1+<)

28、

29、U(1+)，与前υvU∈υ

30、

31、(1Uδ+)式矛盾)。这意味着在VGS()−中存在某个顶点x，它支配U中至少各顶点。υ2现在我们通过迭代来生成G的一个支配集，用S

32、表示在迭代过程中形成的支