1
第五章 支配集、独立集、覆盖集和Ramsey数
本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的图均为简单图。
§5.1 支配集、点独立集、点覆盖集
一、支配集 (Domination set)
定义 5.1.1 设 )(GVD?,若对 )(GVu∈?,要么 Du∈,要么 u 与 D 中的某些顶点相邻，
则称 D 为图 G 的一个 支配集 。如果一个支配集的任何真子集都不是支配集，则称它为 极小支配集 。图 G 的含顶点最少的支配集称为 最小支配集 。最小支配集的顶点个数称为 G 的 支配数,
记为 ()Gγ 或 γ 。
例如，在下图中,}{
00
vD =,},,{
7411
vvvD =,},,,{
65312
vvvvD = 都是 G 的支配集，
前两个是极小支配集，
0
D 是最小支配集。 1)( =Gγ 。
G
注,（ 1）最小支配集必是一个极小支配集，反之不然。
（ 2）任一支配集必含有一个极小支配集。
（ 3）极小支配集不唯一，最小支配集一般也不唯一。
（ 4）对二部图 ),( YXG =,X 和 Y 都是支配集。
（ 5）若图 G 有完美匹配 M
*
，则从 M
*
中每边取一个端点构成的顶点集是一个支配集。
定理 5.1.1 设图 G 中无孤立顶点，则存在支配集 D，使得 ()DVG D=? 也是一个支配集。
证明：无妨设 G 是连通图。于是 G 有生成树 T。任取 )(
0
GVv ∈ 。令
)(|{ GVvvD ∈= 且 ),(
0
vvd
T
＝偶数 },
则 () {| ()DVG D vvVG=?=∈且 ),(
0
vvd
T
＝奇数 }，且 D 和 D 都是支配集。证毕。
定理 5.1.2 设图 G 无孤立顶点，
1
D 是一个极小支配集，则
11
()DVG D=? 也是一个支配集。
证明（反证法）,若不然，存在
10
Dv ∈,它与
1
D 中所有顶点都无边相连，但它又不是孤立顶点，故必与
1
D 中顶点连边，因此
01
vD? 仍是支配集。这与
1
D 是极小支配集矛盾。证毕。
推论 5.1.1 设图 G 中无孤立顶点。 对 G 的任一个极小支配集
1
D,必存在另一个极小支配集
2
D,
使得 φ=
21
DD ∩ 。
证明：由定理 5.1.2，
11
()DVG D=?也是一个支配集，且 φ=DD ∩
1
。
1
D 中必含有一个极小支配集
2
D 。显然 φ=
21
DD ∩ 。证毕。
v
7
v
8
v
2
v
1
v
5
v
6
v
3
v
4
v
0
2
定理 5.1.3 图 G 的支配集 D 是一个极小支配集当且仅当 D 中每个顶点 v 满足下列条件之一,
（ 1）存在 ()uVG D∈?使得 () {}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 不与 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 在 GD?
中必有某个邻点 w，令
1
({}){}DDv w=? ∪,则
1
D 也是 G 的一个最小支配集，但其导出子图 G[D
1
]含的边数比 G[D]中多。这与 D 的取法矛盾。证毕。
以下是关于支配数的几个估计式。
定理 5.1.5 如果图 G 无孤立顶点，则 (G)
2
υ
γ ≤ 。
证明：设 D 是 G 的一个极小支配集，则由定理 5.1.2,V(G) D? 也是 G 的支配集。因此，
(G) min{| D |,| V(G) D |}
2
υ
γ ≤?≤。
证毕。
定理 5.1.6 (Arnautov 1974,Payan 1975) 设 G 是一个最小度为 δ 图,则
1ln( 1)
(G)
1
δ
γ υ
δ
++
≤
+
。
证明：对 G 的任一非空顶点子集 SV(G)?,用 U 表示未被 S 中顶点支配的所有顶点之集。
对 ()vVG?∈,用 ()Nv
表示顶点 v 及其所有邻点组成的集合，即 () () {}Nv Nv v
= ∪ 。由
于 U 中每个顶点至少有 k 个邻点，故 |()|||( 1)
vU
Nv Uδ
∈
≥+
∑
。从而在 ()VG S? 中至少有一个顶点 x，它在求和过程中至少被重复计算
||( 1)U δ
υ
+
次。 (否则，若 ()VG S? 中每个点被重复计算都少于
||( 1)U δ
υ
+
次，则
||
|()|(|S|) ( 1)||( 1)
vU
U
Nv Uυδδ
υ
∈
< +< +
∑
，与前式矛盾 )。这意味着在 ()VG S? 中存在某个顶点 x，它支配 U 中至少
||( 1)U δ
υ
+
各顶点。
3
现在我们通过迭代来生成 G 的一个支配集，用 S 表示在迭代过程中形成的支配集的一部分，初始时可取最大度顶点放入 S。在迭代的每一步选择一个顶点放入 S，所选择的顶点应能够尽可能多地支配当前的 S 尚未支配的顶点。由前一部分的结论，如果当前的 S 尚未支配的顶点有 ||Uk= 个,则在 ()VG S? 中存在某个顶点 x，它支配 U 中至少
(1)k δ
υ
+
个顶点。因此按照我们的选点规则,再选择一个点放入 S 后,剩下未被支配的顶点不超过
1
(1 )k
δ
υ
+
个。
在
ln( 1)
1
δ
υ
δ
+
+
步后，未被支配的顶点个数至多为
ln( 1)
ln( 1)
1
1
(1 )
1
e
δ
υ
δ
δ
δ υ
υυ
υδ
+
+
+
+
<=
+
。
（上式推导中用到不等式 1
p
p e
< ） 。将当前 S 中的点和未被 S 支配的点放在一起，便组成
G 的一个支配集，它含有
ln( 1)
1
δ
υ
δ
+
+
+
1
υ
δ +
=
1ln( 1)
1
δ
υ
δ
+ +
+
个顶点。结论得证。
定理 5.1.7 对任何图 G，有 (G) (G)
1(G)
υ
γυ
≤≤?Δ
+Δ
。
证明,设 D 是 G 的一个最小支配集,则 V(G) D ( )
vD
Nv
∈
∪
,因此 |V(G) D| |D| (G)?≤?Δ 。
而 |V(G) D| |D|υ?=?,|D| (G)γ=,故 (G) (G) (G)υ γγ? ≤Δ,于是 (G)
1(G)
υ
γ
≥
+Δ
。
证毕。
图的支配集是内容相当丰富的一个研究专题，它在许多学科领域有重要的应用，是目前研究的一个热点方向 [1~5]。进一步的了解可参看 Haynes－ Hedetniemi－ Slater 的长达 1200 页的专著 [6]。支配集理论在电力网络中的应用见文献 [7]。支配集在无线通信网络中的应用见文献
[ 8~11]。
[1] B.G.,Xu,Two classes of edge domination in graphs,Discrete Applied Mathematics,154(2006),
1541-1546,
[2] T.W,Haynes,M.A,Henning,and J,Howard,Locating and total dominating sets in trees,Discrete
Applied Mathematics,154(2006),1293-1300,
[3] J.S,Deogun,and D,Kratsch,Dominating pair graphs,SIAM J,Discrete Mathematics,
15:3(2001-2002),353-366,
[4] Chin Lung Lu,Ming-Tat Ko and Chuan Yi Tang,Perfect edge domination and efficient edge
domination in graphs,Discrete Applied Mathematics,119(2002),227-250,
[5] Chin Lung Lu and Chuan Yi Tang,Weighted efficient domination problem on some perfect
graphs,Discrete Applied Mathematics,117(2002),163-182,
[6] T.W,Haynes,S.T,Hedetniemi,and P.J,Slater,Fundamentals of Domination in Graphs,Marcel
Dekker,Inc.,1998,
[7] T.W,Haynes,S.M,Hedetniemi,S.T,Hedetniemi,and M.A,Henning,Domination in graphs
applied to electric power networks,SIAM J,Discrete Mathematics,15:4(2001-2002),519-529,
4
[8] I,Stojmenovic,M,Seddigh,and J,Zunic,Dominating sets and neighbor elimination based
broadcasting algorithms in wireless networks,Proc,IEEE Hawaii Int,Conf,On System Sciences,
Jan,2001,
[9] J,Wu,and H.L.Li,On calculating connected dominating set for efficient routing in ad hoc
wireless networks,Proceedings of the 3
rd
ACM International Workshop on Discrete Algorithms and
Methods for Mobile Computing and Communications,1999,7-14,
[10] S,Guha,and S,Khuller,Approximation algorithms for connected dominating sets,
Algorithmica,20:4(1998),347-387,
[11] B,Das,and V,Bharghavan,Routing in ad hoc networks using minimum connected dominating
sets,ICC’97,Montreal,Canada,June,1997,
二、点独立集 (vertex independent set)
定义 5.1.2 设 ）（ GVI?,若 I 中任二顶点均不相邻，则称 I 为图 G 的一个 点独立集 （简称独立集） ；若对 IGVu \)(∈?,}{uI ∪ 都不再是 G 的独立集，则称独立集 I 为图 G 的一个极大点独立集 。 G 的含点数最多的点独立集称为 最大点独立集,它含点的个数称为 G 的 独立数,记为 )(Gα 或 α 。
例如，在下图中,}{
00
vI =,},,{
7411
vvvI =,},,,{
75312
vvvvI = 都是 G 的独立集，
且都是极大独立集，其中
2
I 是最大独立集,4)( =Gα 。
一些文献中将独立集称为稳定集 (stable set)，相应地将独立数称为稳定数。
z 独立集与支配集的关系
定理 5.1.8 图 G 的极大独立集必是 G 的极小支配集。
证明：设 I 是 G 的一个极大独立集。对 IGVu \)(∈?,u 必与 I 中某顶点相邻（否则与极大性矛盾） 。可见 I 是一个支配集。又对 Iv∈?,v 必与 }{\ vI 中的顶点不相邻，可见 I 是极小支配集。证毕。
注,该定理的逆不真。例如在下图中,},{
21
vv 是极小支配集，但却不是极大独立集。实际上它根本不是独立集。
v
1
v
2
v
3v
4
v
7
v
8
v
2
v
1
v
5
v
6
v
3
v
4
v
0
G
5
但我们有如下结论。
定理 5.1.9 若 I 是独立集，则它是极大独立集当且仅当它是支配集。
证明：必要性由定理 5.1.8 显然。
充分性：设 I 是独立集又是支配集，则对 IGVv \)(∈?,因 I 是支配集,v 必与 I 中某顶点相邻。故 }{vI ∪ 不是独立集。可见 I 是极大独立集。
注,（ 1）由定理 5.1.8 和定理 5.1.9，虽然 G 的一个独立集未必是 G 的支配集，但一个极大独立集必是 G 的极小支配集；反过来,G 的一个支配集要么不是独立集，要么是极大独立集；
（ 2）一个支配集若不是极小支配集，则必不是 G 的独立集。
定理 5.1.10 对任何图 G,(G) (G)α γ≥ 。
证明,设 I 是 G 的一个最大独立集，则它必是一个极大独立集，由定理 5.1.8,I 是 G 的一个
（极小）支配集，因此 (G) | I | (G)γ α≤= 。证毕。
注,定理 5.1.10 中的等号未必总成立，也就是说，虽然 G 的一个最大独立集必是 G 的极小支配集，但它未必是最小支配集。例如完全二部图 K
1,3
，最大独立集含三个点，而最小支配集含一个点。
z 点独立集与连通度
定理 5.1.11 (Bondy,1978) 设 2)( ≥Gν 。若图 G 中任二不相邻顶点 x 与 y 均有
)()()( Gydxd
GG
ν≥+,则 )()( GG κα ≤ 。
证明,首先易知 G 是连通的（若 G 不连通，设 x,y 属于不同的连通分支
21
,GG,则
1||)(
1
≤ Gxd
G
,1||)(
2
≤ Gyd
G
，从而 ν<?+≤+ 2||||)()(
21
GGydxd
GG
） 。
若 G 为完全图
ν
K,则 )(11)(
νν
κνα KK =?≤=,结论成立。下设 G 不是完全图。用反证法证明结论。
假定 1)()( +≥ GG κα 。设 I 和 S 分别是 G 中的最大点独立集和最小点割集。则
2)(|| ≥= GI α,kGS == )(|| κ 。设 SG \ 的连通分支为
l
GGG null,,
21
,)2( ≥l 。由于对
Iyx ∈?,,αν?≤|)()(| yNxN
GG
∪ 。
故 |)()(| yNxN
GG
∩ ＝ |)(||)(| yNxN
GG
+ |)()(| yNxN
GG
∪?
＝ )()( ydxd
GG
+ |)()(| yNxN
GG
∪? 1)( +≥=≥ kαανν 。
这表明 SI \ 含在 SG \ 的同一个连通分支中（因在 SI \ 中任二点 x 与 y 有公共的邻点，故有
I (含 α 个顶点 )
y
x
G-I (含 αν? 个顶点 )
6
路相通） 。无妨设 )(\
1
GVSI?,即 SGVI ∪)(
1
。因 1+≥ kα,故 )(
1
GVIu ∩∈? 。
取 )(
2
GVv∈,则
1|)|(1|)(|)1|)((|2|)()(|
11
==≤ SIGVIGVIvNuN
GG
∩∩∩∪ αννν,
又因 ISvNuN
GG
\)()(?∩,故 |)()(| vNuN
GG
∩ || SIk ∩?≤ 。由此二式可得
() ()|() ()||() ()|
GG G G G G
du dv Nu Nv Nu Nv+ =+∪∩
(||1)(||)I SkISν α≤?+?+?∩∩
1(1)12kkkν αν ν=?+?≤? ++?=?
这与定理条件矛盾。因此 )()( GG κα ≤ 。证毕。
推论 5.1.2 设 G 是 )2( ≥νν 阶简单图。若
2
)(
ν
δ ≥G,则 )()( GG κα ≤ 。
z 独立数与 Hamilton 性,
定理 5.1.12（ Chvátal & Erd?s,1972）设 G 是 )3( ≥νν 阶简单图。若 )()( GG ακ ≥,则 G 是
Hamilton 图。
证明：若 1)( =Gα,则 G 是完全图，从而是 Hamilton 图。下设 2)( ≥Gα 。
由于 2)()( ≥≥ GG ακ,故 G含有圈。 设 C是 G的最长圈。 下面用反证法证明 C是 Hamilton
圈。
若 C 不含 G 的所有顶点，则 )(\)( CVGV 非空。令 H 是 )(CVG? 的任一连通分支，并令 },,,{
21 s
xxx null 是 C 中与 H 相邻的顶点集。因 2)( ≥Gκ,故 2≥s （否则,C 上只有一个顶点 v 与 H 相邻,}{vG? 不连通） 。由 C 的最大性及 H 的连通性知
s
xxx,,,
21
null 在 C 上互不相邻（否则可得更大的圈） 。
因此 sCV >|)(|,且 },,,{
21 s
xxx null 是 G 的点割集（因去掉 },,,{
21 s
xxx null 后 H 与 C 上其余点不连通） 。所以 sG ≤)(κ （由 )(Gκ 的定义） 。
G
1
G
2
I
S
u
v
y
1
x
1
C
H
y
2
x
2
y
s
x
s
…
…
7
给圈 C 定一个方向，得有向圈 C
null
。令 },,2,1),(|{ siCEyxyY
iii
null
null
=∈= 。则由
i
x 在 C
上的不相邻性知,2|| ≥= sY 。下面证明,Y 是 G 的一个独立集。
事实上，若 Y 不是 G 的独立集，则有边 )(GEyy
ji
∈ 。设通过 H 中顶点连接
i
x 和
j
x 的路为
ij
P,则
ijjijjii
PyyyxyxC ++ 是 G 中一条比 C 更长的圈。这与 C 是最长圈矛盾。
于是 Y 是独立集。
由于
i
y 与
i
x 相邻，故
i
y 不与 H 中任何点相邻（否则会得到比 C 更长的圈）,i=1,2,…,s。
任取 )(HVy∈,则 },,,{
1 s
yyyS null= 是 G 的独立集，且 1)(1||)( +≥+=≥ GsSG κα 。这与定理的条件矛盾。因此 C 必是 Hamilton 圈。证毕。
有关独立集和独立数的研究较为活跃。有兴趣的读者可查阅近期文献（如 [12~15]） 。
[12] Anders Sune Pedersen and Preben Dahl Vestergaard,The number of independent sets in
unicyclic graphs,Discrete Applied Mathematics,152(2005),246-256,
[13] Miranca Fischermann,Lutz Volkmann and Dieter Rautenbach,A note on the number of
matchings and independent sets in trees,Discrete Applied Mathematics,145(2005),483-489,
[14] Ralph J,Faudree,Zden k Ryjá ek and Richard H,Schelp,On local and global independence
numbers of a graph,Discrete Applied Mathematics,132(2003),79-84,
[15] Arun Jagota,Giri Narasimhan and ubomír oltés,A Generalization of maximal
independent sets,Discrete Applied Mathematics,117(2002),223-235,
三、点覆盖 (vertex covering set)
定义 5.1.3 设 )(GVF?,若 G 的每条边至少有一个端点属于 F，则称 F 是 G 的一个 点覆盖 。
若对任给的 Fv∈,}{vF? 不再是 G 的点覆盖，则称点覆盖 F 是一个 极小点覆盖 。图 G 的含点数最少的点覆盖称为 最小点覆盖,其点数称为 G 的 点覆盖数,记为 )(Gβ 或 β 。
例如，在下图中,},,,,{
75310
vvvvv 和 },,,,,,,{
87654321
vvvvvvvv 都是 G 的点覆盖，且都是极小点覆盖。前一个点覆盖是最小点覆盖,)(Gβ ＝ 4。
G
注,（ 1）最小点覆盖必为极小点覆盖；
（ 2）点覆盖集与支配集是容易混淆的两个概念，它们的本质区别在于，点覆盖集是用点覆盖边，而支配集使用点支配点。在连通图中，点覆盖集必为支配集。但支配集未必是覆盖集。
比如上例中 }{
0
v 及 },,{
741
vvv 都是 G 的支配集，但不是覆盖集。
（ 3）极小点覆盖集未必是极小支配集。
例如上例中 },,,,{
75310
vvvvv 是 G 的极小点覆盖集，但它不是 G 的极小支配集。
v
7
v
8
v
2
v
1
v
5v6
v
3
v
4
v
0
8
z 点覆盖与点独立集的关系,
定理 5.1.13 顶点子集 F 是图 G 的点覆盖集当且仅当 FGV \)( 是 G 的点独立集。
证明,F 是图 G 的点覆盖集?G 的每条边至少有一端在 F 中?没有两端都在 FGV \)( 中的边? FGV \)( 是点独立集。证毕。
推论 5.1.3 F 是图 G 的极小点覆盖集当且仅当 FGV \)( 是 G 的极大点独立集。
推论 5.1.4 νβα =+ )()( GG,
§5.2 边独立集与边覆盖集
一、边独立集
定义 5.2.1,图 G 的一个匹配 M 称为 G 的一个 边独立集 。 G 的最大匹配所含的边数称为 G 的边独立数 或 匹配数,记为 )(Gα′ 。
边独立集与点覆盖有密切关系。由于任意一个顶点不能覆盖边独立集中的两条边，因此图有大的边独立集，就有大的点覆盖集。另一方面，独立集中不同的边不能用同一个顶点覆盖，因此图 G 中任何点覆盖集的含的点数不会小于任何边独立集含的边数。边独立数与点覆盖的下列关系是显然的。
z )(12)(
22 nn
KnnK βα =?<=′ ；
z )()(
22 nn
CnC βα ==′ ；
z )(2)(
1212 ++
=<=′
nn
KnnK βα ；
z )(1)(
1212 ++
=+<=′
nn
CnnC βα ；
z )(},min{)(
,,nmnm
KnmK βα ==′ 。
一般地，有
定理 5.2.1 对任何无环边的图 G,)()( GG βα ≤′ 。
证明：设 S 是 G 中一个最小点覆盖,M 是 G 中最大匹配。 M 中任一条边 e 的两端点至少有一个属于 S，因而 )()( GG βα ≤′ 。证毕。
定理 5.2.2 (K?nig,Egerváry,1931)
[16],[17]
对于二部图 G，有 )()( GG βα =′,即 G 中最大匹配的边数等于最小覆盖的点数。
[16] D,K?nig,Graphen und Matrizen,Math,Lapok,38(1931),116-119,
[17] E,Egerváry,On combinatorial properties of matrices,Math,Lapok,38(1931),16-28
证明：设 M
*
是 G = ( X,Y )的最大匹配。设 |||| YX ≤ 。
若 M
*
饱和 X，则 ||
*
M=′α 。另一方面,X 显然是一个最小点覆盖（因 M
*
中每条边需要一个点来覆盖） 。故 αβ ′=== ||||)(
*
MXG 。
若 M
*
不饱和 X，设
xXxU |{ ∈= 未被 M
*
所饱和 },vGVvA |)({ ∈= 到 U 有 M
*
交错路 U∪},
XAS ∩=,YAT ∩= 。
9
则 TSN =)( 。 （ *）
令 TSXK ∪)(?=,则 G 的每条边至少有一端在 K 中（否则必存在一条边，其一端在 S 中，
另一端在 TY \ 中，这与 TSN =)( 矛盾） 。因此 K 是 G 的一个点覆盖，且
||||
*
KM = 。 （ **）
结合定理 5.2.1，便有 )()(||||
*
GGMK βα ≤′== 。而 K 是 G 的一个点覆盖，因此又有
)(|| GK β≥ 。从而 )(||||)(
*
GMKG αβ ′=== 。证毕。
附,（ *）式的证明,
首先 )(SNT?,对 Ty∈?,y 到 U 有 M
*
交错路 P，且 y 必是 M
*
饱和的（否则 P 是 M
*
可扩路） 。设
*
Myx∈,则 x 到 U 有 M
*
交错路 P + yx。这表明 Sx∈,故 )(SNy∈ ；
其次 TSN?)(,对 )(SNy∈?,设 y 在 S 中的邻点是 x。因 x 到 U 有交错路 P′，故若
Py ′∈,则 y到 U有交错路； 若 Py ′?,则 xyP +′ 是 y到 U的 M
*
交错路。 总之 Ay∈ 故 Ty∈ 。
证毕。
（ **） 的证明,首先 SX? 是 M
*
饱和的 （因 X 中的非饱和点全在 U 中）,T 也是 M
*
饱和的 （否则有 M
*
可扩路） 。故 K 中每一点都对应有一条 M
*
的边；其次,SX? 与 T 间不会有 M
*
的边
（否则 SX? 中的点到 U 有 M
*
交错路） 。因此每条 M
*
的边仅有 K 中一个点与之相关联。可见 M
*
的边与 K 的点一一对应，因而 ||||
*
KM = 。证毕。
关于边独立数有如下估计式。
定理 5.2.3 设图 G 无孤立点，则 (G)
1(G) 2
υ υ
α
′≤≤
+Δ
。
证明：因为每条匹配边匹配图 G 的两个顶点，故上界是显然的。
为证明下界，对图的边数 ε 作数学归纳法。
1ε = 时结论显然成立。
假设对任何不超过 k 条边的图 G，下界都成立。
设 G 是具有 k+1 条边且无孤立点的图。若 G 中每条边都有至少一个端点是 1 度顶点，则
G 的每个连通分支都是星 (星是一个完全二部图，其中一个分部仅含一个点,如 K
1,s
)。一颗星
K
1,s
的最大匹配只有一条边，且
1,1,
(K ),(K ) 1
ss
ssυΔ= =+,因此
1,
1,
1,
(K )
(K ) 1
1(K)
s
s
s
υ
α′ ==
+Δ
。
设 G 由 r 颗星
12
,,
r
TT Tnull 组成（ 1r ≥ ）,则
U
T=N(S)
X \ S
S
10
1
11
()
() (G)
(G) ( )
1()1+(G)1(G)
r
irr
ii
i
ii
i
T
T
T
T
υ
υ υ
αα
=
==
′′ ≥=
+Δ Δ +Δ
∑
∑∑
。
下设 G 中存在边 e，其两端点都不是 1 度点。设 G e? 有 m 个连通分支
12
G,G,G
m
null
（ 1m ≥ ）,则每个连通分支都不是孤立点，且边数都不超过 k。因此根据归纳假设,
(G )
(G ),( 1,2,)
1(G)
i
i
i
im
υ
α′ ≥=
+Δ
null 。
从而
1
11
(G )
(G ) (G)
(G) (G ) (G )
1(G)1+( )1(G)
m
imm
ii
i
ii
i
e
Ge
υ
υ υ
αα α
=
==
′′ ′≥?= ≥ ≥ ≥
+Δ Δ? +Δ
∑
∑∑
。
归纳完成。证毕。
二、边覆盖
定义 5.2.2 设 )(GEL? 。若 G 的每个顶点都与 L 中至少一条边关联，则称 L 是 G 的 边覆盖 。
若边覆盖 L 的任何真子集都不是 G 的边覆盖，则称 L 是 G 的 极小边覆盖 。 G 的含边数最少的边覆盖称为 G 的 最小边覆盖,其所含边的数目称为 G 的 边覆盖数,记为 )(Gβ′ 或 β′。
例如，在下图中,},,{
6321
eeeL = 和 },,{
7322
eeeL = 都是边覆盖，也是极小边覆盖，还是最小边覆盖； },,,{
75413
eeeeL = 是边覆盖，但不是极小边覆盖。
z 点独立数与边覆盖数的关系
定理 5.2.4 对任何图 G，都有 )()( GG βα ′≤ 。
证明：设 I 是 G 的最大点独立集。因 I 中点彼此不相邻，故至少要用 |I|条边才能覆盖住 I 中的所有顶点，故 )(||)( GIG βα ′≤= 。证毕。
z 边覆盖与边独立数（匹配数）的关系
定理 5.2.5(Gallai,1959) 若 0)( >Gδ,则 νβα =′+′ )()( GG 。
证明：设 M 是 G 的最大匹配。若 M 是 G 的完美匹配，则显然 α
ν
β ′==≤′
2
|| M,从而
ν
νν
βα =+≤′+′
22；若 M 不是 G 的完美匹配,U 是 M 非饱和点之集。则 ][UG 是无边图
（否则在 G[U]中取一边可使 M 扩大） 。由于 0)( >Gδ,所以 U 的每个点在 G 中都至少与一
条边关联。对应于每个点取这样一条边，这些边的集合记为 E′。显然 EM ′∪ 是 G 的边覆盖，
e
1
e
3
e
5
e
7e6
e
2
e
4
11
且 φ=′EM ∩ 。因而（注意 M 中的边数为 α′,E′中的边数为 αν ′? 2 ）
αναναβ ′?=′?+′=′≤′ )2(|| EM ∪,即 νβα ≤′+′ 。
另一方面，设 L 是 G 的最小边覆盖。令 ][LGH =,则 ν== )()( GVHV (因 L 覆盖了 G
的所有顶点 )。设 M 是 H 的最大匹配,U 为 H 中 M 非饱和点集，则 H[U]是无边图，从而
||2|||\||||| MUMLML?=≥=? ν 。 （ *）
其中第一个等号用到 ML? ；不等号是因为 L-M 中每条边要么两端点都 M 饱和，要么只有一端点 M 不饱和。故 L-M 中每条边至多有一个点在 U 中。而且 U 中每个点至少由 L-M 中一条边关联。
由（ *）式,||| |LMυ+≥。又因 H 是 G 的生成子图，故 M 也是 G 的匹配。从而
||||MLα βυ′′+≥ +≥。证毕。
推论 5.2.1 图 G 的边覆盖数等于 G 的边独立数加上最大匹配非饱和点的个数。
证明：由定理 5.2.5,() () () ( 2 ())GGG Gβ υα α υ α′′′ ′=?=+?,注意到 ()Gα′ 是最大匹配的边数，故 2()Gυ α′? 是未被最大匹配饱和的点数。证毕。
该推论将求 G 的最小边覆盖集的问题转化为求 G 的最大匹配问题：求出 G 的一个最大匹配 M
*
，对于在 M
*
下未饱和的每个点，任选其一条关联的边，这些边与 M
*
的边放在一起便形成 G 的一个最小边覆盖。
推论 5.2.2 设 G 是二部图且 0)( >Gδ,则 )()( GG βα ′= 。
证明：由于 βανβα ′+′==+,而由 Konig-Egerváry 定理,βα =′,故 βα ′= 。证毕。
推论 5.2.3 设 0)( >Gδ,则 )()( GG βα ′≤′,等号成立当且仅当 G 有完美匹配；
证明：设 M
*
是 G 的最大匹配。则覆盖 M
*
关联的 2|M
*
|个点至少需要 |M
*
|条边。故
)(||)(
*
GMG βα ′≤=′ 。
等号成立时，由 Gallai 定理 νβα =′+′ )()( GG 知,να =′ )(2 G,故 M
*
是完美匹配。
推论 5.2.4 设 0)( >Gδ,则
（ 1） 对 G 的任一匹配 M 和任一边覆盖 L，有 |||| LM ≤ 。等号成立时 M 为完美匹配且 L 为最小边覆盖；
（ 2） 对 G 的任一匹配 M 和任一点覆盖 F，有 |||| FM ≤ 。等号成立时,M 为最大匹配且 F
为最小点覆盖；
（ 3） 对 G 中任一点独立集 I 和任一边覆盖 L，有 |||| LI ≤ 。等号成立时,I 为最大点独立集且 L 为最小边覆盖。
证明,（ 1）对任一匹配 M 和任一边覆盖 L，由推论 5.2.3，有 ||)()(|| LGGM ≤′≤′≤ βα 。
当 |||| LM = 时，上式成为 ||)()(|| LGGM =′=′= βα 。因而 M 是最大匹配,L 是最小边覆盖，且由推论 5.2.3 知，此时 M 是完美匹配。
12
（ 2）由定理 5.2.1,有 |||| FM ≤≤′≤ βα 。当 |M|=|F|时，上式成为 |||| FM ==′= βα,可见 M 是最大匹配而 F 是最小点覆盖。
（ 3）由定理 5.2.4 得,|||| LI ≤′≤≤ βα 。当 |||| LI = 时，上式成为 |||| LI =′== βα,可见此时 I 是最大点独立集而 L 是最小边覆盖。 证毕。
注,（ 1）对完美匹配 M 和最小边覆盖 L，必定 |||| LM = ；
（ 2）对最大匹配 M 和最小点覆盖 F，未必 |||| FM = 。例如
5
C,最大匹配含 2 边，但最小点覆盖含 3 点；
（ 3）对最大点独立集 I 和最小边覆盖 L，未必 |||| LI = 。同样可取
5
C 检验。
关于点覆盖数的估计，有下述结果。
定理 5.2.6 设图 G 无孤立点，则
(G)
(G)
21(G
υυ
β
Δ
′≤≤
+Δ
。
证明：由定理 5.2.5,() ()GGα βυ′′+=，得 () ()GGβ υα′ ′=? 。再利用定理 5.2.3，
(G)
1(G) 2
υ υ
α
′≤≤
+Δ
，由此立即可得结论。证毕。
最后再给出一个支配数与点（边）独立数、点（边）覆盖数的关系作为本节的结束。
定理 5.2.7 设图 G 无孤立顶点，则 (G) min{ (G),(G),(G),(G)}γ αα ββ′ ′≤ 。
证明,(G) (G)γ α≤ 是定理 5.1.10 的结论。
由于无孤立顶点的图中每个点覆盖都是支配集，因此 (G) (G)γ β≤ 成立。
设 E
1
是 G 的一个最小边覆盖，则 G 的每个顶点是 E
1
中至少一条边的端点。对 E
1
中每条边取其一个端点，所形成的顶点集合记为 D,则 D 是 G 的一个支配集。因此
1
(G) | D | | E | (G)γ β′≤≤= 。
设 M 是 G 的一个最大匹配，对 M 中任一条边 euv=,端 点 u,v 中至少有一个的所有邻点都是 M 饱和点（否则,u,v 都有 M 不饱和邻点，则有 M 增广路，与 M 是最大匹配矛盾） 。无妨设 u 的所有邻点都是 M 饱和的，则称 e 的另一端点 v 称为 e 的可选端点。对 M 中每条边取其一个可选端点，形成一个集合 D，则 D 是 G 的一个支配集（对任一个 M 饱和顶点，与它关联的 M 匹配边必有一个端点在 D 中，故被 D 支配；对每个 M 非饱和顶点 w，其邻点必定是
M 饱和的,按 D 的选法,其邻点必在 D 中,因此 w 也被 D 支配） 。 于是 (G) | D | | M | (G)γ β≤ == 。
证毕。
有关边覆盖的更多内容可参看 [18]。
[18] A,Schrijver,Combinatorial Optimization Polyhedra and Efficiency,New York,NY,
Springer-Verlag,2003,
13
§5.3 支配集、点独立集、点覆盖集的求法
一、应用背景
1,应急增援中心的选址
欲在 n 个地点
n
vvv,,,
21
null 设置若干个应急中心，使得每个地点都与至少一个应急中心相邻（有直达通路） 。同时，为了减少造价，应急中心的数目要尽可能少。问应设多少个？如何设置？
图论模型：以 n 个地点为顶点集，两点之间有直达通路时，连边，得一图 G。问题是：求图
G 的最小支配集。
2,收款台的设置
某商场实行收款台收款制度。为使顾客在任何一个货架通道都能看到至少一个收款台，
问至少应设置多少个收款台？设在什么位置？
类似的问题有：执勤岗哨的设置问题、交通监控器的设置问题等。
图论模型：构作图 G：货架通道为 G 的边，通道交叉点为 G 的顶点。问题是求图 G 最小点覆盖集。
3,通信信号差错控制问题
设某信息传输系统的基本信号集合为 },,,{
521
sssS null= 。由于干扰等原因，使得接收端收到的信号可能发生错乱。比如发送
1
s,可能收到
2
s 。通过统计分析已经知道哪些信号间容易发生错乱。例如，容易发生错乱的情况如下图所示。为了能从收到的输出信号辨识出正确的输入信号，我们不能使用所有 5 个信号来传送信息，而只能从中选出一部分使用。问如何选取尽可能多的可用信号？
图论模型,构作图 G：以
521
,,,sss null 为顶点，若信号
i
s 容易错收为
j
s,则从顶点
i
s 向
j
s 连一条有向边。问题是求有向图 G 中的最大点独立集。
目前还没有有效算法来求任意给定图的极小点覆盖集、极大点独立集和极小支配集。下面介绍的方法用到布尔代数。
二、逻辑运算及其性质
设 G 是一个图，用
i
v 表示事件“包含顶点
i
v,；
ji
vv + 或
ji
vv ∨ 表示事件“要么包含顶点
i
v,要么包含顶点
j
v,；
ji
vv 或
ji
vv ∧ 表示事件“即包含顶点
i
v 又包含顶点
j
v,。则如下逻辑运算律成立,
s
1
s
2
s
3
s
4 s5
发送
s
1
s
2
s
3
s
4 s5
接收
s
1
s
5
s
4
s
3
s
2
14
（ 1）交换律：
ji
vv +
ij
vv +=,
ji
vv
ij
vv= 。
（ 2）结合律：
kji
vvv ++ )()(
kji
vvv ++=,
kji
vvv )()(
kji
vvv=
（ 3）分配律,)(
kji
vvv +
kiji
vvvv +=,
kji
vvv )( +
kjki
vvvv +=
（ 4）吸收律,
iii
vvv =+,
iii
vvv =,
ijii
vvvv =+,
ijii
vvvv =+ )( 。
三、算法
1,极小点覆盖和极大独立集
（ 1） 由定义,V(G)的子集 C 是 G 的极小点覆盖? 对每个 )(GVv
i
∈,要么 Cv
i
∈,
要么 CvN
iG
)( 。
（ 2）由推论 5.1.3,V(G)的子集 C 是 G 的极小点覆盖? V(G)\C 是 G 的极大点独立集。
由此可得求所有极小点覆盖和极大独立集的方法,
将表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏∏
展开成积之和的形式，则每一项表示一个极小点覆盖，而这些极小点覆盖的补集给出了所有极大点独立集。表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏ ∏
通常记为
12
(,,,)vv v
υ
null 。
例 5.3.1 求下图的所有极小点覆盖和极大点独立集。
解,),,,(
721
vvv null? = )(
421
vvv + )(
65312
vvvvv + )(
75423
vvvvv + )(
65314
vvvvv +
)(
74325
vvvvv +? )(
7426
vvvv + )(
6537
vvvv +
＝
6531
vvvv ＋
65432
vvvvv ＋
7542
vvvv ＋
7432
vvvv 。
故极小点覆盖有,
1
C ＝ },,,{
6531
vvvv,},,,,{
654322
vvvvvC =,},,,{
75423
vvvvC =,},,,{
74324
vvvvC = 。
而极大点独立集有,
==
11
CI },,{
742
vvv,
==
22
CI },{
71
vv,==
33
CI },,{
631
vvv,
==
44
CI },,{
651
vvv 。
同时，不难得出最小点覆盖和最大点独立集。
2,极小支配集
由定理 5.1.3，上述方法得出的极大独立集必是 G 的极小支配集。但一般情况下这并未包含 G 的所有极小支配集。求所有极小支配集的方法为,
v
7
v
6
v
5
v
4
v
3
v
2
v
1
15
将表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏∑
展开成积之和的形式，则每一项给出一个极小支配集。表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏∑
通常记为
12
(,,,)vv v
υ
ψ null 。
例 5.3.2 求下图的所有极小支配集。
解：
12
(,,,)vv v
υ
ψ null ＝ )(
4321
vvvv +++ )(
412
vvv ++ )(
413
vvv ++
)(
653214
vvvvvv +++++? )(
645
vvv ++ )(
546
vvv ++
＝
51
vv ＋
61
vv ＋
4
v ＋
532
vvv ＋
632
vvv
故 G 的所有极小支配集为,},{
51
vv,},{
61
vv,}{
4
v,},,{
532
vvv,},,{
632
vvv 。
上述求极小点覆盖集、极大点独立集和极小支配集的算法是指数阶的。例如对于求极小点覆盖集、极大点独立集的算法，我们需要处理 )(
1)(
∏∏
=∈
+
ν
ivNu
i
i
uv 的展开式中 2
υ
个乘积项，因此计算复杂度至少是 O(2 )
υ
。但目前尚没有更好的精确型算法求极小点覆盖集、极大点独立
集和极小支配集的最优解。
设计求极小点覆盖集、极大点独立集和极小支配集的近似算法，或在某些约束条件下寻找它们的精确算法，是目前的一个研究热点。文献 [19]~[21]与点覆盖算法有关,[22]~[24]涉及到点独立集的算法,[25],[26]研究有关支配集的近似算法和分布式算法，文献 [27]~[30]研究无线通信网络中连通支配集的算法。
[19] R,Bar-Yehuda and S,Even,A local-ratio theorem for approximating the weighted vertex cover
problem,Annals of Discrete Mathematics,25(1985) 27-45,
[20] K.L,Clarkson,A modification of the greedy algorithm for vertex cover,Information Processing
Letters,17(1983) 23-25,
[21] D.S,Hochbaum,Approximation algorithms for set covering and vertex cover problems,SIAM
Journal on Computing,11(1982) 555-556,
[22] Thomas Erlebach and Klaus Jansen,Conversion of coloring algorithms into maximum weight
independent set algorithms,Discrete Applied Mathematics,148(2005),107-125,
[23] V,E,Alekseev,Polynomial algorithm for finding the largest independent sets in graphs without
forks,Discrete Applied Mathematics,135(2004),3-16,
[24] Shuichi Sakai,Mitsunori Togasaki and Koichi Yamazaki,A note on greedy algorithms for the
maximum weighted independent set problem,Discrete Applied Mathematics,126(2003),313-322
[25] Toshihiro Fujito and Hiroshi Nagamochi,A 2-approximation algorithm for the minimum weight
edge dominating set problem,Discrete Applied Mathematics,118(2002),199-207,
[26] Lucia D,Penso and V.C.Valmir C,Barbosa,A distributed algorithm to find k-dominating sets,
Discrete Applied Mathematics,141(2004),243-253,
v
6
v
5
v
4
v
3
v
2
v
1
16
[27] I,Stojmenovic,M,Seddigh,and J,Zunic,Dominating sets and neighbor elimination based
broadcasting algorithms in wireless networks,Proc,IEEE Hawaii Int,Conf,On System Sciences,
Jan,2001,
[28] J,Wu,and H.L.Li,On calculating connected dominating set for efficient routing in ad hoc
wireless networks,Proceedings of the 3
rd
ACM International Workshop on Discrete Algorithms and
Methods for Mobile Computing and Communications,1999,7-14,
[29] S,Guha,and S,Khuller,Approximation algorithms for connected dominating sets,
Algorithmica,20:4(1998),347-387,
[30] B,Das,and V,Bharghavan,Routing in ad hoc networks using minimum connected dominating
sets,ICC’97,Montreal,Canada,June,1997,
§5.4 Ramsey 数
一、团（ clique）
定义 5.4.1 设 )(GVQ?,若导出子图 ][QG 是完全图，则称 Q 是 G 的一个 团 。若给团 Q 添加 QGV \)( 中任何顶点，导出子图都不再是团，则称 Q 是一个 极大团 。图 G 的含顶点数最多的团称为 G 的 最大团,其顶点数称为 G 的 团数,记为 ()Gω 。含 k 个顶点的团称为 k-团 。
例如，在下图中,},,{
210
vvv 和 },,{
320
vvv 都是 G 的团。前者是极大团，而后者不是。
},,,{
4320
vvvv 是 G 的最大团。
注,（ 1）任何非平凡的树，其团数均为 2。
（ 2） Q 是 G 的团当且仅当 Q 是 G 的独立集； Q 是 G 的极大（最大）团当且仅当 Q 是 G 中极大（最大）独立集
关于团有许多研究专题，文献 [31]~[36]分别涉及到最大团问题、最大赋权团问题、最大团覆盖问题、边 -团覆盖、团独立集、团划分等。团也与图的染色有密切关系，这将在下一章讨论。
[31] Patric R,J,?sterg?rd,A fast algorithm for the maximum clique problem,Discrete Applied
Mathematics,120(2002),197-207
[32] S,Busygin,A new trust region technique for the maximum weight clique problem,Discrete
Applied Mathematics,154(2006),2080-2096,
[33] J.M.Keil,and L.Stewart,Approximating the minimum clique cover and other hard problems in
subtree filament,Discrete Applied Mathematics,154(2006),1983-1995,
[34] G.Durán,M.C.Lin,S.Mera and J.L.Sawarcfiter,Algorithms for clique-independent sets on
subclasses of circular-are graphs,Discrete Applied Mathematics,154(2006),1783-1790,
v
7
v
8
v
2
v
1
v
5
v
6
v
3
v
4
v
0
17
[35] T.S,Michael,and T.Quint,Sphericity,cubicity,and edge clique covers of graphs,Discrete
Applied Mathematics,154(2006),1309-1313,
[36] I,Charon,and O,Hudry,Noising methods for a clique partitioning problem,Discrete Applied
Mathematics,154(2006),754-769,
显然，团和点独立集是两个互补的概念。即顶点子集 Q 是图 G 的团当且仅当 Q 是补图 G
的独立集。 直观上判断,一个图如果没有大的团则应该有大的点独立集。 这一问题属于 Ramsey
理论的研究范畴。
二,Ramsey 数
先来看一个例子。
例 5.4.1 任意 6 个人的聚会上，总有 3 人互相认识或互不认识。
证明,用 6 个顶点代表六个人，构造 6 阶完全图 K
6
。如果两人互相认识，则将它们的连边染红色，否则染蓝色。则问题转化为：证明将 K
6
的边进行任意红、蓝染色，一定会出现红色三角形或蓝色三角形。
在完全图 K
6
中任取一顶点记为 v
1
，
由组合学中的鸽笼原理，以 v
1
为端点的 5 条连边中至少有 3 条是同色的。不妨设边 v
1
v
2
,v
1
v
3
,v
1
v
4
都为红色。现考察连接 v
2
,v
3
,v
4
的 3 条边，
若这 3 条边全为蓝色，则△v
2
v
3
v
4
就是一个同色三角形（蓝色） 。否则,3 条边中必有红色边，
无妨设为 v
2
v
3
，则△v
2
v
3
v
4
构成一个同色三角形（红色） 。证毕。
上述问题可描述为：对完全图 K
6
的边任意染红蓝两种颜色后，要么有红色三 角形，要么有蓝色三角形。一般地，有,
用红、蓝两种颜色对完全图的边染色，要求不论怎么染，都能要么出现染红色的 p 阶完全子图 K
p
，要么出现染蓝色的 q 阶完全子图 K
q
，这样的完全图至少应有多少个顶点 (即至少应为多少阶图 )？
如果将红色边形成的子图记为 G，则蓝色边形成的子图是 G 的补图。因此上述问题也可
描述为,
求 min{ |r 每个 r 阶图 G 要么本身含有 p-团，要么其补图 G 含有 q-团 }。
亦即,求 min{ |r 每个 r 阶图 G 要么有 p-团，要么有含 q 个顶点的独立集 }。
这个问题称为 Ramsey 问题,所求的最少顶点数（即完全图应具有的最小阶数）称为
Ramsey 数,记为 (,)rpq。特别地，定义 r (1,q) = r ( p,1) =1。
Ramsey 问题的上述三种表述经常交替使用。例 5.4.1 实际上证明了 r (3,3) ≤ 6。
定理 5.4.1 r (3,3) = 6。
证明：由例 5.4.1,r (3,3) ≤ 6。另一方面，长为 5 的圈 C
5
既无 3-团又无 3 个点的独立集，这表明 r (3,3) ≥ 6。因此 r (3,3) = 6。证毕。
定理 5.4.2 r (3,4) = 9。
证明,先证 r (3,4) ≥ 9。
对具有 9 个顶点的任何图 G，必存在顶点 v
0
，其度
0
() 3dv ≠ 。 （否则,G 的顶点度之和为奇数） 。
18
如果
0
() 4dv ≥,设 v
1
,v
2
,v
3
,v
4
是其 4 个邻点。若 v
1
,v
2
,v
3
,v
4
有一条连边，比如 v
1
v
2
，
则 v
0
,v
1
,v
2
构成 G 的一个 3-团；否则,v
1
,v
2
,v
3
,v
4
间没有连边，形成 G 的一个 4 顶点独立集。
如果
0
() 3dv <,则 G 中至少有 6 个顶点与 v
0
不相邻。由于 r (3,3)=6，故这 6 个顶点在 G
导出的子图要么有 3-团，要么有含 3 个顶点的独立集。如果是前者，则结论已成立；如果是后者，则与 v
0
一起构成含 4 个顶点的独立集。
综上,具有 9 个顶点的任何图 G,要么有 3-团,要么有 4 个顶点的独立集,因此 r(3,4) ≥ 9。
另一方面，如下所示的 8 阶图既无 3-团，又无 4 个顶点的独立集，这说明 r (3,4) ≤ 9。于是 r (3,4) = 9。证毕。
定理 5.4.3 r(4,4) =18。
证明,对具有 18 个顶点的任何图 G，任取其一个顶点 v
0
。
如果
0
() 9dv ≥,取其 9 个邻点,将这 9 个邻点在 G 中的点导出子图记为 G
1
,由定理 5.4.2，
r (3,4) = 9，故 G
1
中要么有 3-团，要么有 4 个顶点的独立集。若是前者，则这个 3-团与 v
0
组成 G 的一个 4-团；若是后者，则这个独立集也是 G 中的 4 个顶点的独立集。
如果
0
() 9dv <,则与 v
0
不相邻的顶点至少有 9 个，即在 G 的补图 G 中 v
0
至少有 9 个邻点。与以上类似可得,G 中要么有 4-团，要么有 4 个顶点的独立集。从而 G 中要么有 4-团，
要么有 4 个顶点的独立集。
以上结果表明 r(4,4) ≤ 18。
下证 r (4,4) > 17。我们只需找出对 K
17
的边的一种红蓝染色，使得不出现同色的 K
4
即可。
在一个圆周上画出 17 个等分点，将其依次编号为 v
0
,v
1
,v
2
,…,v
16
，把整数 1,2,…,16 分为两组,
X={1,2,4,8,9,13,15,16},Y={3,5,6,7,10,11,12,14}。
按下列规则对 K
17
进行红、蓝边染色：对于边,(0,16)
ij
vv i j≤ ≤,
当 ||ijX?∈时，将边
ij
vv 染成红色；当 ||ijY? ∈ 时，将边
ij
vv 染成蓝色。
按此规则，下列边被染成红色
01 02 04 08 09 013 015 016
(,),(,),(,),(,),(,),(,),(,),(,);vv vv vv vv vv vv vv vv
12 13 15 19 116
(,),(,),(,),(,),,(,)vv vv vv vv vvnull ；
… … … … … … … … … …
15 16
(,)vv 。
其余边全染蓝色。可以检验，在这样的颜色下 K
17
中没有同色的 K
4
。这表明 r(4,4) >17。
由以上两方面便得 r(4,4) = 17。证毕。
19
有时用“边染色”的说法进行论证更为直观和简便。比如上一定理的前半部分可以用边染色方法论述如下。
设对 K
18
的边进行了任意的红、蓝染色。考察 K
18
中从任一顶点 v
0
出发的 17 条边。由鸽笼原理知，其中至少有 9 条边是同色的，不妨设为红色。这 9 条边异于 v
0
的 9 个端点构成完全子图 K
9
，由 r (3,4) =9 知，该 K
9
中要么有红色 K
3
，要么有蓝色 K
4
。若是前者，则这个红色
K
3
与 v
0
一起便构成了红色 K
4；若是后者，则本身就是一个蓝色 K
4
。由此便知 r (4,4) ≤ 18。
三,Ramsey 数的性质
定理 5.4.4
（ 1） r ( p,q ) = r ( q,p );
（ 2） r ( 2,q ) = q,r ( p,2 ) = p;
（ 3）当 p,q ≥ 2 时，有 r ( p,q ) ≤ r ( p,q –1 )+ r ( p –1,q )，且当 r ( p,q –1 )和 r ( p –1,q )都是偶数时，不等号严格成立。
证明,(1) 设 r ( p,q ) = k，则对任何 k 阶图 G，其补图 G 也是一个 k 阶图，故 G 中要么有 p-
团，要么有 q 个顶点的独立集，从而 G 中要么有 q-团，要么有 p 个顶点的独立集，由 G 的任意性，知 r ( q,p ) = k。
(2) 对任一个 q 阶图，要么至少有一条边，任何一条边的两个端点即构成 2-团；要么没有边，此时所有 q 个顶点构成一个独立集。故 r ( 2,q ) = q。同理可证 r ( p,2 ) = p。
(3) 我们用“边染色”的方法来该性质，读者可尝试用团和独立集的方式改写这个证明。
令 n = r ( p,q–1 ) + r ( p –1,q )，下面证明，用红蓝两色对 K
n
的边任意染色后，必有红色的 K
p
或蓝色的 K
q
,从而 r ( p,q ) ≤ n,
事实上，任取 K
n
的一个顶点 v,设 v 连出的 n?1 条边中有 n
1
条红色边,n
2
条蓝色边。则
n
1
+ n
2
= n –1 = r ( p,q–1 ) + r ( p –1,q ) –1 。
1）若 n
1
≥ r ( p –1,q)，则 v 通过红边相连的顶点至少有 r ( p –1,q) 个。按照 r ( p –1,q) 的定义，这 r ( p –1,q) 个点构成的完全图 K
r(p?1,q)
中要么含有红色的 K
p?1
，要么含有蓝色的 K
q
。
若是前者，则该红色的 K
p?1
与 v 便构成 K
n
中一个红色的 K
p；若是后者，则自然有蓝色的 K
q
。
2）若 n
1
< r ( p –1,q)，则 n
2
≥ r ( p,q–1 )。与上述过程同样可 证得：红蓝染色后的 K
n
中必有红色的 K
p
或蓝色的 K
q
。
因此，用红蓝两色对 K
n
的边任意染色后，必有红色的 K
p
或蓝色的 K
q
,故
r ( p,q ) ≤ n = r ( p,q –1 )+ r ( p –1,q )。
下面证明当 r ( p,q –1 )和 r ( p –1,q )都是偶数时,不等号严格成立。 设 m= r ( p,q–1 ) + r ( p
–1,q ) –1。因 m 是奇数，故用红蓝两色对完全图 K
m
的边任意染色后，必有某点 v
0
关联的边有偶数条被染红（若每点处都有奇数条红边，则所有红色边导数的子图中顶点度之和为奇数，
这是不可能的） 。因
0
()dv = m?1=r ( p,q–1 ) + r ( p –1,q ) –2。如果与 v
0
关联的 m?1 条边中红色边至少有 r ( p –1,q )条，则与上述（ 1）同样可证,K
m
中必有红色的 K
p
或蓝色的 K
q；如果与 v
0
关联的红色边少于 r ( p –1,q )条，则由 v
0
的取法（与 v
0
关联的红色边有偶数条）,v
0
至多有 r ( p –1,q )?2 条红边，因此至少有 r ( p,q–1 )条蓝边。此时与上述（ 2）同样可知,K
m
中必有红色的 K
p
或蓝色的 K
q
。
20
由以上可见 r ( p,q–1 ) + r ( p –1,q ) –1 个顶点的完全图 K
m
的边任意红蓝染色，必有红色的 K
p
或蓝色的 K
q
，故 r ( p,q ) ≤ r ( p,q –1 )+ r ( p –1,q ) –1< r ( p,q –1 )+ r ( p –1,q )。证毕。
例 5.4.2 证明,r ( 3,5 ) =14。
证,由性质 (3),r ( 3,5 ) ≤ r ( 3,4 )+ r (2,5) = 9 + 5 = 14。
另一方面，按如下方法对完全图 K
13
的边进行红、蓝染色：设 K
13
的顶点为 0,1,2,···,12，
将这些顶点依次放在一个圆周的 13 等分点上。当点 i 与 k 满足
k = i+1,i+5,i+8,i+12,(mod 13),
时，点 i 与 k 之间连红色边；否则，连蓝色边。可以检验，这样构成的对 K
13
的红蓝染色，既无红色的 K
3
，又无蓝色的 K
5
。这表明 r ( 3,5 ) ≥ 14。
由以上两方面即知,r ( 3,5 ) =14。证毕。
四,Ramsey 数的上下界
定理 5.4.5 设,2pq≥,则
2
(,)
1
pq
rpq
p
+?
≤
，其中
2
1
pq
p
+?
表示从 2pq+?个元素中取 1p? 个元素的组合数。
证明,对 p q+ 用归纳法。
由性质，
22
(2,)
21
q
rq q
+?
==
，
22
(,2)
1
p
rp p
p
+?
==
,可见当 1p = 或 1q = 时，
结论成立。假定对满足 4 p qst≤+<+的所有正整数对 (,)p q,结论都成立。则
332
(,) ( 1,) (,1)
21 1
st st st
rst rs t rst
sss
+?+?+?
≤?+?≤ + =
。
这里用到了组合恒等式
11
1
nn n
mm m
+=
。证毕。
定理 5.4.6 当 3q ≥ 时，
2
3
(3,)
2
q
rq
+
≤ 。
证明：对 q 进行归纳。当 3q = 时,(3,3) 6r =,且
2
3
6
2
q +
=,结论不等式成立。
当 4q = 时,(3,4) 9r =,且 (3,1) 6rq? =,而
2
319
22
q +
=,结论不等式严格成立。
假设 1qk≤?时结论成立。则 qk= 时,
22
(1)3 4
(3,) (2,) (3,1)
22
kk
rk rk rk k
++
≤+?≤+ =。
下证上述不等式严格成立，这样便证明了
2
3
(3,)
2
k
rk
+
≤ 。
事实上，若 k 是奇数，则
2
4k + 是奇数，故此时，
2
4
(3,)
2
k
rk
+
< ；下设 k 是偶数。此
21
时如果
2
(1)3
(3,1)
2
k
rk
+
<,则所证不等式严格成立；如果
2
(1)3
(3,1)
2
k
rk
+
=,
则因 k 是偶数，从而 (2,)rk k= 和
22
(1)3
(3,1) 2
22
kk
rk k
+
==?+都是偶数，由定理
5.4.4，此时 (3,) (2,) (3,1)rk rk rk<+?，故所证不等式严格成立。证毕。
当 p q= 时,Ramsey 数 (,)rpp称为 对角 Ramsey 数,对角 Ramsey 数的一个下界如下。
定理 5.4.7 当 3p ≥ 时，
2
(,) 2
p
rpp≥ 。
证明,对 n 阶完全图 K
n
进行任意红蓝边染色时，由于其每条边都有染 红和染蓝两种可能，而
K
n
共有
(1)
2
nn?
条边，故不同的染色方案共有
(1)
2
2
nn?
种。对于 K
n
中指定的 p 个顶点，它们之间的连边有
(1)
2
pp?
条。在 K
n
的所有染色方案中，使这 p 个顶点形成的完全子图 K
p
全染红边的方案有
n(n 1) ( 1)
22
2
pp
种（除 K
p
的边外，其余
(1)
2
nn?
(1)
2
pp?
条边每条有 2 种染法） 。
因 K
n
中指定 p 个顶点的方式有
n
p
种，故在 K
n
的所有红蓝边染色方案中，出现红色 K
p
的染法有
n
p
n(n 1) ( 1)
22
2
pp
种。它占染色方案总数的比例为
(1) ( 1)
22 (1)
(1)
2
2
(1)
2
2
2
2
!
2
nn pp
pp
pp p
nn
n
np
n
p p
=<
。
假定
2
2
p
n <,则
2
(1) (1)
22 (1)
22 2
(1)
2
2
22 2 2 2 2 2 1
!!123 2
2
nn pp
ppp p
nn
n
p
pp p
< == <。
这表明在 K
n
的所有红蓝边染色方案中，出现红色 K
p
的染法不到染色方案总数的一半。由两种颜色的对等性,出现蓝色 K
p
的染法也不到染色方案总数的一半。 有此可知,只要
2
2
p
n <,
则必有 K
n
的一种红蓝边染色方案，即不出现红色 K
p
也不出现蓝色 K
p
。故
2
(,) 2
p
rpp≥ 。证毕。
由定理 5.4.7 容易得到下列推论（习题） 。
推论 5.4.1 设 min{,}mpq=,则
2
(,) 2
m
rpq≥ 。
下表列出了目前已经确定的所有 Ramsey 数和一些上下界，此表引自 [37]和 [38]。
[37] D.B.West,Introduction to Graph theory (2
nd
edition),2001
[38]《图论及其应用,（张先迪、李正良编）高教出版社,2005。
22
一些 r(p,q)的值和界
q
p
3 4 5 6 7 8 9 10 11 12 13 14 15
3 6 9 14 18 23 28 36 40/43 46/51 51/60 59/69 66/78 73/89
4 18 25 35/41 49/61 55/84 69/115 80/149 96/191 106
/238
118
/291
129
/349
134
/417
5 43/49 58/87 80/143 95/216 121/316?/442
6 102/165 109/298 122/495 153/780?/1171
7 205/540?/1031?/1713?/2826
8?/1870 282/3583?/6096
9?/6625 565/
12715
10?/23854 798/?
表中 a/b 表示 a 为下界,b 为上界。
五,Ramsey 数的一般形式
定义 5.4.2 设 p
1
,p
2
,···,
p
m
是一组给定的大于 1 的正整数，用 m 种颜色 C
1
,C
2
,···,
C
m
对完全图的边染色，要求不论怎么染，都能要么出现 C
1
色的完全子图
1
K
p
,要么出现 C
2
色的完全子图
2
K
p
,···,要么出现 C
m
色的完全子图 K
m
p
,这样的完全图至少应有多少个顶点 (即至少应为多少阶图 )？ 这个问题称为 一般 Ramsey 问 题,所求的最少顶点数 (即完全图的阶数 )称为 一般
Ramsey 数,记为 r ( p
1
,p
2
,···,
p
m
)。
例 5.4.3 有 17 位学者，每人给其他人各写一封信，讨论三个问题中的某一个问题，且两人之间互相通信讨论的是同一问题。证明至少有三位学者，他们之间通信讨论的是同一个问题。
证明,此问题等价于证明用红黄蓝三种颜色对 K
17
的边任意染色后，必出现同色三角形 K
3
。
设 v
0
,v
1
,v
2
,…,v
16
是 K
17
的顶点。对 K
17
的边任意进行红黄蓝三染色后,v
0
与其余 16 点的连边中至少有
16
6
3
=
条同色边，无妨设为 v
0
v
1
,v
0
v
2
,···,v
0
v
6
这六条边被染红色。考虑由
v
1
,v
2
,…,v
6
组成的完全子图 K
6
。如果其中有一条红色边，比如 v
1
v
2
，则 v
0
,v
1
,v
2
三点便组成红色三角形；如果其中没有红色边，则 K
6
的边全为黄蓝两色，归结为 K
6
的边 2 染色问题，由例
5.3.1 知，其中必含有黄色三角形或蓝色三角形。证毕。
关于一般 Ramsey 数，有如下类似于定理 5.4.4 的性质。
（ 1）对正整数 p
1
,p
2
,…,p
m
的任一种排列
12
,,,
m
ii i
p ppnull,有
r ( p
1
,p
2
,···,
p
m
)= r (
12
,,,
m
ii i
p ppnull );
（ 2） r ( 2,p
1
,p
2
,…,p
m
) = r ( p
1
,p
2
,···,
p
m
);
（ 3） r ( p
1
,p
2
,···,
p
m
)≤ r ( p
1
1,p
2
,···,
p
m
)+ r ( p
1
,p
2
1,···,
p
m
)+ ··· + r ( p
1
,p
2
,···,
p
m
1 )?m+2;
（ 4） r ( p
1
+1,p
2
+1,···,
p
m
+1)≤
12
12
()!
!! !
m
m
p pp
pp p
+++null
null
。
23
其中（ 1） ~（ 3）的证明与定理 5.4.4 类似,（ 4）的证明与定理 5.4.5 类似。
Greenwood和 Gleason 已经证明,r (3,3,3)=17。 另有一些一般 Ramsey 数已获得其上下界。
Ramsey 理论是一个十分精彩而又相当难的研究方向。 Ramsey 数有多种推广形式。有关更深入的内容可参看专著 [39],[40]。
[39] T.D,Parsons,Ramsey graph theory,in Selected Topics in Graph Theory (L,W,Beineke,and
R.J,Wilson eds.),Academic Press,London,(1978) 361-384,
[40] R.L,Graham,B.L,Rothschild,and J.E,Spencer,Ramsey Theory,Wiley,New York,1990,
第五章习题
1,证明：图 G 是二部图当且仅当对 G 的每个子图 H 均有 )(
2
1
)( HH να ≥ 。
2,设 G 是一个二部图,证明
1
(G) (G)
2
αν= 当且仅当 G 有一个完美匹配。
3,证明：图 G 是二部图当且仅当对 G 的每个适合 0)( >Hδ 的子图 H 均有 )()( HH βα ′= 。
4,如图 G，求,
（ 1） G 的所有极小支配集及支配数；
（ 2） G 的所有极小点覆盖集及点覆盖数；
（ 3） G 的所有极大点独立集及点独立数；
（ 4） G 的所有极大匹配及匹配数；
（ 5） G 的所有极小边覆盖及边覆盖数。
5,下图是连接 10 个城市的宽带流媒体骨干网络的结构示意图。在这个网络上，用户可以进行通信或获取各种网络信息，也可以召开网络会议、进行远程教学，还可以实时在线点播音乐、电影和电视剧、玩电子游戏或视屏聊天。现在网络设计者想要在部分节点设置一些大型数据库存放网络资源供用户下载，这些数据库完全相同并需要定期更新。为了节省网络带宽和缩短用户下载时延，要求每个城市经过至多一跳（即一条边）便能访问到数据库。
另一方面，出于建设成本和更新维护成本的考虑，设计者又希望设置尽可能少的数据库达到上述要求。请建立这一问题的图论模型，并帮设计者找出一个最优的设置方案，同时要解释你的方案为什么是最优的。
6,利用 Konig 定理证明：任一个二部图 G 有一个至少含
(G)
(G)
ε
Δ
条边的匹配。并由此证明：设
H 是完全二部图 K
n,n
的一个子图，如果 (H) ( 1)knε >?,则 H 中存在至少含有 k 条边的匹配。
7,设 G 是一个非平凡简单图,证明,（ 1） (G)
ε
αυ≤?
Δ；（ 2） 如果 G 是正则图,则 (G)
2
υ
α ≤ 。
a
e
d
c
b
f
v
1
v
4
v
3
v
2
v
5
24
8,设 G 是恰含一个圈的非二部图，证明
1
(G)
2
υ
α
≥
。
9,设 G 是一个无孤立点的图,M 是 G 的一个极大匹配,L 是 G 的一个极小边覆盖。证明,
（ 1） M 是最大匹配当且仅当 M 含于某个最小边覆盖中；
（ 2） L 是最小边覆盖当且仅当 L 包含一个最大匹配。
10,设 G 是一个简单图，其中任意 k 个顶点的度之和小于 nk?,证明图 G 的任意极大独立集的顶点数大于 k,
11,表述支配数为 1 的图的特征。
12,找出支配数和点覆盖数不相等的最小树。
13,
n
C 和
n
P 分别表示有 n 个顶点的圈和路。给出求 ()
n
Cγ 和 ()
n
Pγ 的公式。
14,设 G 是一个简单图，证明,(G)
2
υ
γ ≤ 。 （提示：利用结论：若 S 是极小支配集，则 S也是支配集。 ）
15,设 G 是无孤立点的图，证明,(G) (G)
2
υ
γυβ′≤?≤。
16,设 G 是简单图，证明,（ 1） (G) (G)
1(G)
υ
γυ
≤≤?Δ
+Δ；
（ 2）
1diamG diamG
(G)
32
γυ
+
≤≤?
。
17,证明：若图 G 的直径至少是 3，则 (G) 2γ ≤ 。
18,确定 Petersen 图的支配数。
19,(1) 证明：对 9 个顶点构成的完全图 K
9
，将它的边进行任意红、蓝染色后，一定会出现同色的三角形或同色的 K
4
。
(2) 对完全图 K
8
，找出一种对其边进行红蓝染色的方案，使得既不出现红色的 K
3
又不出现蓝色的 K
4
。
20,设 min{,}mpq=,证明
2
(,) 2
m
rpq≥ 。
21,证明：对任意正整数整数 p
1
,p
2
,…,p
m
，有 r ( p
1
,p
2
,···,
p
m
) ≤ r ( p
1
,r(p
2
,···,
p
m
))。
22,证明,（ 1）对正整数 p
1
,p
2
,…,p
m
的任一种排列
12
,,,
m
ii i
p ppnull,有 r ( p
1
,p
2
,···,
p
m
)= r
(
12
,,,
m
ii i
p ppnull )。 （ 2） r ( 2,p
1
,p
2
,…,p
m
) = r ( p
1
,p
2
,···,
p
m
)。
23,证明,r (3,3,3) ≤ 17。
24,平面上有 6 个点，其中任意三点都能组成一个不等边三角形。证明：在这些点构成的所有三角形中，必有一个三角形的最短边是另一个三角形的最长边。
25,九位科学家在一次国际会议上相遇，发现他们中的任意 3 个人中，至少有 2 个人可以用同一种语言交谈。如果每个科学家最多会说 3 种语言，证明至少有 3 个科学家可以用同一种语言交谈。
第五章 支配集、独立集、覆盖集和Ramsey数
本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的图均为简单图。
§5.1 支配集、点独立集、点覆盖集
一、支配集 (Domination set)
定义 5.1.1 设 )(GVD?,若对 )(GVu∈?,要么 Du∈,要么 u 与 D 中的某些顶点相邻，
则称 D 为图 G 的一个 支配集 。如果一个支配集的任何真子集都不是支配集，则称它为 极小支配集 。图 G 的含顶点最少的支配集称为 最小支配集 。最小支配集的顶点个数称为 G 的 支配数,
记为 ()Gγ 或 γ 。
例如，在下图中,}{
00
vD =,},,{
7411
vvvD =,},,,{
65312
vvvvD = 都是 G 的支配集，
前两个是极小支配集，
0
D 是最小支配集。 1)( =Gγ 。
G
注,（ 1）最小支配集必是一个极小支配集，反之不然。
（ 2）任一支配集必含有一个极小支配集。
（ 3）极小支配集不唯一，最小支配集一般也不唯一。
（ 4）对二部图 ),( YXG =,X 和 Y 都是支配集。
（ 5）若图 G 有完美匹配 M
*
，则从 M
*
中每边取一个端点构成的顶点集是一个支配集。
定理 5.1.1 设图 G 中无孤立顶点，则存在支配集 D，使得 ()DVG D=? 也是一个支配集。
证明：无妨设 G 是连通图。于是 G 有生成树 T。任取 )(
0
GVv ∈ 。令
)(|{ GVvvD ∈= 且 ),(
0
vvd
T
＝偶数 },
则 () {| ()DVG D vvVG=?=∈且 ),(
0
vvd
T
＝奇数 }，且 D 和 D 都是支配集。证毕。
定理 5.1.2 设图 G 无孤立顶点，
1
D 是一个极小支配集，则
11
()DVG D=? 也是一个支配集。
证明（反证法）,若不然，存在
10
Dv ∈,它与
1
D 中所有顶点都无边相连，但它又不是孤立顶点，故必与
1
D 中顶点连边，因此
01
vD? 仍是支配集。这与
1
D 是极小支配集矛盾。证毕。
推论 5.1.1 设图 G 中无孤立顶点。 对 G 的任一个极小支配集
1
D,必存在另一个极小支配集
2
D,
使得 φ=
21
DD ∩ 。
证明：由定理 5.1.2，
11
()DVG D=?也是一个支配集，且 φ=DD ∩
1
。
1
D 中必含有一个极小支配集
2
D 。显然 φ=
21
DD ∩ 。证毕。
v
7
v
8
v
2
v
1
v
5
v
6
v
3
v
4
v
0
2
定理 5.1.3 图 G 的支配集 D 是一个极小支配集当且仅当 D 中每个顶点 v 满足下列条件之一,
（ 1）存在 ()uVG D∈?使得 () {}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 不与 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 在 GD?
中必有某个邻点 w，令
1
({}){}DDv w=? ∪,则
1
D 也是 G 的一个最小支配集，但其导出子图 G[D
1
]含的边数比 G[D]中多。这与 D 的取法矛盾。证毕。
以下是关于支配数的几个估计式。
定理 5.1.5 如果图 G 无孤立顶点，则 (G)
2
υ
γ ≤ 。
证明：设 D 是 G 的一个极小支配集，则由定理 5.1.2,V(G) D? 也是 G 的支配集。因此，
(G) min{| D |,| V(G) D |}
2
υ
γ ≤?≤。
证毕。
定理 5.1.6 (Arnautov 1974,Payan 1975) 设 G 是一个最小度为 δ 图,则
1ln( 1)
(G)
1
δ
γ υ
δ
++
≤
+
。
证明：对 G 的任一非空顶点子集 SV(G)?,用 U 表示未被 S 中顶点支配的所有顶点之集。
对 ()vVG?∈,用 ()Nv
表示顶点 v 及其所有邻点组成的集合，即 () () {}Nv Nv v
= ∪ 。由
于 U 中每个顶点至少有 k 个邻点，故 |()|||( 1)
vU
Nv Uδ
∈
≥+
∑
。从而在 ()VG S? 中至少有一个顶点 x，它在求和过程中至少被重复计算
||( 1)U δ
υ
+
次。 (否则，若 ()VG S? 中每个点被重复计算都少于
||( 1)U δ
υ
+
次，则
||
|()|(|S|) ( 1)||( 1)
vU
U
Nv Uυδδ
υ
∈
< +< +
∑
，与前式矛盾 )。这意味着在 ()VG S? 中存在某个顶点 x，它支配 U 中至少
||( 1)U δ
υ
+
各顶点。
3
现在我们通过迭代来生成 G 的一个支配集，用 S 表示在迭代过程中形成的支配集的一部分，初始时可取最大度顶点放入 S。在迭代的每一步选择一个顶点放入 S，所选择的顶点应能够尽可能多地支配当前的 S 尚未支配的顶点。由前一部分的结论，如果当前的 S 尚未支配的顶点有 ||Uk= 个,则在 ()VG S? 中存在某个顶点 x，它支配 U 中至少
(1)k δ
υ
+
个顶点。因此按照我们的选点规则,再选择一个点放入 S 后,剩下未被支配的顶点不超过
1
(1 )k
δ
υ
+
个。
在
ln( 1)
1
δ
υ
δ
+
+
步后，未被支配的顶点个数至多为
ln( 1)
ln( 1)
1
1
(1 )
1
e
δ
υ
δ
δ
δ υ
υυ
υδ
+
+
+
+
<=
+
。
（上式推导中用到不等式 1
p
p e
< ） 。将当前 S 中的点和未被 S 支配的点放在一起，便组成
G 的一个支配集，它含有
ln( 1)
1
δ
υ
δ
+
+
+
1
υ
δ +
=
1ln( 1)
1
δ
υ
δ
+ +
+
个顶点。结论得证。
定理 5.1.7 对任何图 G，有 (G) (G)
1(G)
υ
γυ
≤≤?Δ
+Δ
。
证明,设 D 是 G 的一个最小支配集,则 V(G) D ( )
vD
Nv
∈
∪
,因此 |V(G) D| |D| (G)?≤?Δ 。
而 |V(G) D| |D|υ?=?,|D| (G)γ=,故 (G) (G) (G)υ γγ? ≤Δ,于是 (G)
1(G)
υ
γ
≥
+Δ
。
证毕。
图的支配集是内容相当丰富的一个研究专题，它在许多学科领域有重要的应用，是目前研究的一个热点方向 [1~5]。进一步的了解可参看 Haynes－ Hedetniemi－ Slater 的长达 1200 页的专著 [6]。支配集理论在电力网络中的应用见文献 [7]。支配集在无线通信网络中的应用见文献
[ 8~11]。
[1] B.G.,Xu,Two classes of edge domination in graphs,Discrete Applied Mathematics,154(2006),
1541-1546,
[2] T.W,Haynes,M.A,Henning,and J,Howard,Locating and total dominating sets in trees,Discrete
Applied Mathematics,154(2006),1293-1300,
[3] J.S,Deogun,and D,Kratsch,Dominating pair graphs,SIAM J,Discrete Mathematics,
15:3(2001-2002),353-366,
[4] Chin Lung Lu,Ming-Tat Ko and Chuan Yi Tang,Perfect edge domination and efficient edge
domination in graphs,Discrete Applied Mathematics,119(2002),227-250,
[5] Chin Lung Lu and Chuan Yi Tang,Weighted efficient domination problem on some perfect
graphs,Discrete Applied Mathematics,117(2002),163-182,
[6] T.W,Haynes,S.T,Hedetniemi,and P.J,Slater,Fundamentals of Domination in Graphs,Marcel
Dekker,Inc.,1998,
[7] T.W,Haynes,S.M,Hedetniemi,S.T,Hedetniemi,and M.A,Henning,Domination in graphs
applied to electric power networks,SIAM J,Discrete Mathematics,15:4(2001-2002),519-529,
4
[8] I,Stojmenovic,M,Seddigh,and J,Zunic,Dominating sets and neighbor elimination based
broadcasting algorithms in wireless networks,Proc,IEEE Hawaii Int,Conf,On System Sciences,
Jan,2001,
[9] J,Wu,and H.L.Li,On calculating connected dominating set for efficient routing in ad hoc
wireless networks,Proceedings of the 3
rd
ACM International Workshop on Discrete Algorithms and
Methods for Mobile Computing and Communications,1999,7-14,
[10] S,Guha,and S,Khuller,Approximation algorithms for connected dominating sets,
Algorithmica,20:4(1998),347-387,
[11] B,Das,and V,Bharghavan,Routing in ad hoc networks using minimum connected dominating
sets,ICC’97,Montreal,Canada,June,1997,
二、点独立集 (vertex independent set)
定义 5.1.2 设 ）（ GVI?,若 I 中任二顶点均不相邻，则称 I 为图 G 的一个 点独立集 （简称独立集） ；若对 IGVu \)(∈?,}{uI ∪ 都不再是 G 的独立集，则称独立集 I 为图 G 的一个极大点独立集 。 G 的含点数最多的点独立集称为 最大点独立集,它含点的个数称为 G 的 独立数,记为 )(Gα 或 α 。
例如，在下图中,}{
00
vI =,},,{
7411
vvvI =,},,,{
75312
vvvvI = 都是 G 的独立集，
且都是极大独立集，其中
2
I 是最大独立集,4)( =Gα 。
一些文献中将独立集称为稳定集 (stable set)，相应地将独立数称为稳定数。
z 独立集与支配集的关系
定理 5.1.8 图 G 的极大独立集必是 G 的极小支配集。
证明：设 I 是 G 的一个极大独立集。对 IGVu \)(∈?,u 必与 I 中某顶点相邻（否则与极大性矛盾） 。可见 I 是一个支配集。又对 Iv∈?,v 必与 }{\ vI 中的顶点不相邻，可见 I 是极小支配集。证毕。
注,该定理的逆不真。例如在下图中,},{
21
vv 是极小支配集，但却不是极大独立集。实际上它根本不是独立集。
v
1
v
2
v
3v
4
v
7
v
8
v
2
v
1
v
5
v
6
v
3
v
4
v
0
G
5
但我们有如下结论。
定理 5.1.9 若 I 是独立集，则它是极大独立集当且仅当它是支配集。
证明：必要性由定理 5.1.8 显然。
充分性：设 I 是独立集又是支配集，则对 IGVv \)(∈?,因 I 是支配集,v 必与 I 中某顶点相邻。故 }{vI ∪ 不是独立集。可见 I 是极大独立集。
注,（ 1）由定理 5.1.8 和定理 5.1.9，虽然 G 的一个独立集未必是 G 的支配集，但一个极大独立集必是 G 的极小支配集；反过来,G 的一个支配集要么不是独立集，要么是极大独立集；
（ 2）一个支配集若不是极小支配集，则必不是 G 的独立集。
定理 5.1.10 对任何图 G,(G) (G)α γ≥ 。
证明,设 I 是 G 的一个最大独立集，则它必是一个极大独立集，由定理 5.1.8,I 是 G 的一个
（极小）支配集，因此 (G) | I | (G)γ α≤= 。证毕。
注,定理 5.1.10 中的等号未必总成立，也就是说，虽然 G 的一个最大独立集必是 G 的极小支配集，但它未必是最小支配集。例如完全二部图 K
1,3
，最大独立集含三个点，而最小支配集含一个点。
z 点独立集与连通度
定理 5.1.11 (Bondy,1978) 设 2)( ≥Gν 。若图 G 中任二不相邻顶点 x 与 y 均有
)()()( Gydxd
GG
ν≥+,则 )()( GG κα ≤ 。
证明,首先易知 G 是连通的（若 G 不连通，设 x,y 属于不同的连通分支
21
,GG,则
1||)(
1
≤ Gxd
G
,1||)(
2
≤ Gyd
G
，从而 ν<?+≤+ 2||||)()(
21
GGydxd
GG
） 。
若 G 为完全图
ν
K,则 )(11)(
νν
κνα KK =?≤=,结论成立。下设 G 不是完全图。用反证法证明结论。
假定 1)()( +≥ GG κα 。设 I 和 S 分别是 G 中的最大点独立集和最小点割集。则
2)(|| ≥= GI α,kGS == )(|| κ 。设 SG \ 的连通分支为
l
GGG null,,
21
,)2( ≥l 。由于对
Iyx ∈?,,αν?≤|)()(| yNxN
GG
∪ 。
故 |)()(| yNxN
GG
∩ ＝ |)(||)(| yNxN
GG
+ |)()(| yNxN
GG
∪?
＝ )()( ydxd
GG
+ |)()(| yNxN
GG
∪? 1)( +≥=≥ kαανν 。
这表明 SI \ 含在 SG \ 的同一个连通分支中（因在 SI \ 中任二点 x 与 y 有公共的邻点，故有
I (含 α 个顶点 )
y
x
G-I (含 αν? 个顶点 )
6
路相通） 。无妨设 )(\
1
GVSI?,即 SGVI ∪)(
1
。因 1+≥ kα,故 )(
1
GVIu ∩∈? 。
取 )(
2
GVv∈,则
1|)|(1|)(|)1|)((|2|)()(|
11
==≤ SIGVIGVIvNuN
GG
∩∩∩∪ αννν,
又因 ISvNuN
GG
\)()(?∩,故 |)()(| vNuN
GG
∩ || SIk ∩?≤ 。由此二式可得
() ()|() ()||() ()|
GG G G G G
du dv Nu Nv Nu Nv+ =+∪∩
(||1)(||)I SkISν α≤?+?+?∩∩
1(1)12kkkν αν ν=?+?≤? ++?=?
这与定理条件矛盾。因此 )()( GG κα ≤ 。证毕。
推论 5.1.2 设 G 是 )2( ≥νν 阶简单图。若
2
)(
ν
δ ≥G,则 )()( GG κα ≤ 。
z 独立数与 Hamilton 性,
定理 5.1.12（ Chvátal & Erd?s,1972）设 G 是 )3( ≥νν 阶简单图。若 )()( GG ακ ≥,则 G 是
Hamilton 图。
证明：若 1)( =Gα,则 G 是完全图，从而是 Hamilton 图。下设 2)( ≥Gα 。
由于 2)()( ≥≥ GG ακ,故 G含有圈。 设 C是 G的最长圈。 下面用反证法证明 C是 Hamilton
圈。
若 C 不含 G 的所有顶点，则 )(\)( CVGV 非空。令 H 是 )(CVG? 的任一连通分支，并令 },,,{
21 s
xxx null 是 C 中与 H 相邻的顶点集。因 2)( ≥Gκ,故 2≥s （否则,C 上只有一个顶点 v 与 H 相邻,}{vG? 不连通） 。由 C 的最大性及 H 的连通性知
s
xxx,,,
21
null 在 C 上互不相邻（否则可得更大的圈） 。
因此 sCV >|)(|,且 },,,{
21 s
xxx null 是 G 的点割集（因去掉 },,,{
21 s
xxx null 后 H 与 C 上其余点不连通） 。所以 sG ≤)(κ （由 )(Gκ 的定义） 。
G
1
G
2
I
S
u
v
y
1
x
1
C
H
y
2
x
2
y
s
x
s
…
…
7
给圈 C 定一个方向，得有向圈 C
null
。令 },,2,1),(|{ siCEyxyY
iii
null
null
=∈= 。则由
i
x 在 C
上的不相邻性知,2|| ≥= sY 。下面证明,Y 是 G 的一个独立集。
事实上，若 Y 不是 G 的独立集，则有边 )(GEyy
ji
∈ 。设通过 H 中顶点连接
i
x 和
j
x 的路为
ij
P,则
ijjijjii
PyyyxyxC ++ 是 G 中一条比 C 更长的圈。这与 C 是最长圈矛盾。
于是 Y 是独立集。
由于
i
y 与
i
x 相邻，故
i
y 不与 H 中任何点相邻（否则会得到比 C 更长的圈）,i=1,2,…,s。
任取 )(HVy∈,则 },,,{
1 s
yyyS null= 是 G 的独立集，且 1)(1||)( +≥+=≥ GsSG κα 。这与定理的条件矛盾。因此 C 必是 Hamilton 圈。证毕。
有关独立集和独立数的研究较为活跃。有兴趣的读者可查阅近期文献（如 [12~15]） 。
[12] Anders Sune Pedersen and Preben Dahl Vestergaard,The number of independent sets in
unicyclic graphs,Discrete Applied Mathematics,152(2005),246-256,
[13] Miranca Fischermann,Lutz Volkmann and Dieter Rautenbach,A note on the number of
matchings and independent sets in trees,Discrete Applied Mathematics,145(2005),483-489,
[14] Ralph J,Faudree,Zden k Ryjá ek and Richard H,Schelp,On local and global independence
numbers of a graph,Discrete Applied Mathematics,132(2003),79-84,
[15] Arun Jagota,Giri Narasimhan and ubomír oltés,A Generalization of maximal
independent sets,Discrete Applied Mathematics,117(2002),223-235,
三、点覆盖 (vertex covering set)
定义 5.1.3 设 )(GVF?,若 G 的每条边至少有一个端点属于 F，则称 F 是 G 的一个 点覆盖 。
若对任给的 Fv∈,}{vF? 不再是 G 的点覆盖，则称点覆盖 F 是一个 极小点覆盖 。图 G 的含点数最少的点覆盖称为 最小点覆盖,其点数称为 G 的 点覆盖数,记为 )(Gβ 或 β 。
例如，在下图中,},,,,{
75310
vvvvv 和 },,,,,,,{
87654321
vvvvvvvv 都是 G 的点覆盖，且都是极小点覆盖。前一个点覆盖是最小点覆盖,)(Gβ ＝ 4。
G
注,（ 1）最小点覆盖必为极小点覆盖；
（ 2）点覆盖集与支配集是容易混淆的两个概念，它们的本质区别在于，点覆盖集是用点覆盖边，而支配集使用点支配点。在连通图中，点覆盖集必为支配集。但支配集未必是覆盖集。
比如上例中 }{
0
v 及 },,{
741
vvv 都是 G 的支配集，但不是覆盖集。
（ 3）极小点覆盖集未必是极小支配集。
例如上例中 },,,,{
75310
vvvvv 是 G 的极小点覆盖集，但它不是 G 的极小支配集。
v
7
v
8
v
2
v
1
v
5v6
v
3
v
4
v
0
8
z 点覆盖与点独立集的关系,
定理 5.1.13 顶点子集 F 是图 G 的点覆盖集当且仅当 FGV \)( 是 G 的点独立集。
证明,F 是图 G 的点覆盖集?G 的每条边至少有一端在 F 中?没有两端都在 FGV \)( 中的边? FGV \)( 是点独立集。证毕。
推论 5.1.3 F 是图 G 的极小点覆盖集当且仅当 FGV \)( 是 G 的极大点独立集。
推论 5.1.4 νβα =+ )()( GG,
§5.2 边独立集与边覆盖集
一、边独立集
定义 5.2.1,图 G 的一个匹配 M 称为 G 的一个 边独立集 。 G 的最大匹配所含的边数称为 G 的边独立数 或 匹配数,记为 )(Gα′ 。
边独立集与点覆盖有密切关系。由于任意一个顶点不能覆盖边独立集中的两条边，因此图有大的边独立集，就有大的点覆盖集。另一方面，独立集中不同的边不能用同一个顶点覆盖，因此图 G 中任何点覆盖集的含的点数不会小于任何边独立集含的边数。边独立数与点覆盖的下列关系是显然的。
z )(12)(
22 nn
KnnK βα =?<=′ ；
z )()(
22 nn
CnC βα ==′ ；
z )(2)(
1212 ++
=<=′
nn
KnnK βα ；
z )(1)(
1212 ++
=+<=′
nn
CnnC βα ；
z )(},min{)(
,,nmnm
KnmK βα ==′ 。
一般地，有
定理 5.2.1 对任何无环边的图 G,)()( GG βα ≤′ 。
证明：设 S 是 G 中一个最小点覆盖,M 是 G 中最大匹配。 M 中任一条边 e 的两端点至少有一个属于 S，因而 )()( GG βα ≤′ 。证毕。
定理 5.2.2 (K?nig,Egerváry,1931)
[16],[17]
对于二部图 G，有 )()( GG βα =′,即 G 中最大匹配的边数等于最小覆盖的点数。
[16] D,K?nig,Graphen und Matrizen,Math,Lapok,38(1931),116-119,
[17] E,Egerváry,On combinatorial properties of matrices,Math,Lapok,38(1931),16-28
证明：设 M
*
是 G = ( X,Y )的最大匹配。设 |||| YX ≤ 。
若 M
*
饱和 X，则 ||
*
M=′α 。另一方面,X 显然是一个最小点覆盖（因 M
*
中每条边需要一个点来覆盖） 。故 αβ ′=== ||||)(
*
MXG 。
若 M
*
不饱和 X，设
xXxU |{ ∈= 未被 M
*
所饱和 },vGVvA |)({ ∈= 到 U 有 M
*
交错路 U∪},
XAS ∩=,YAT ∩= 。
9
则 TSN =)( 。 （ *）
令 TSXK ∪)(?=,则 G 的每条边至少有一端在 K 中（否则必存在一条边，其一端在 S 中，
另一端在 TY \ 中，这与 TSN =)( 矛盾） 。因此 K 是 G 的一个点覆盖，且
||||
*
KM = 。 （ **）
结合定理 5.2.1，便有 )()(||||
*
GGMK βα ≤′== 。而 K 是 G 的一个点覆盖，因此又有
)(|| GK β≥ 。从而 )(||||)(
*
GMKG αβ ′=== 。证毕。
附,（ *）式的证明,
首先 )(SNT?,对 Ty∈?,y 到 U 有 M
*
交错路 P，且 y 必是 M
*
饱和的（否则 P 是 M
*
可扩路） 。设
*
Myx∈,则 x 到 U 有 M
*
交错路 P + yx。这表明 Sx∈,故 )(SNy∈ ；
其次 TSN?)(,对 )(SNy∈?,设 y 在 S 中的邻点是 x。因 x 到 U 有交错路 P′，故若
Py ′∈,则 y到 U有交错路； 若 Py ′?,则 xyP +′ 是 y到 U的 M
*
交错路。 总之 Ay∈ 故 Ty∈ 。
证毕。
（ **） 的证明,首先 SX? 是 M
*
饱和的 （因 X 中的非饱和点全在 U 中）,T 也是 M
*
饱和的 （否则有 M
*
可扩路） 。故 K 中每一点都对应有一条 M
*
的边；其次,SX? 与 T 间不会有 M
*
的边
（否则 SX? 中的点到 U 有 M
*
交错路） 。因此每条 M
*
的边仅有 K 中一个点与之相关联。可见 M
*
的边与 K 的点一一对应，因而 ||||
*
KM = 。证毕。
关于边独立数有如下估计式。
定理 5.2.3 设图 G 无孤立点，则 (G)
1(G) 2
υ υ
α
′≤≤
+Δ
。
证明：因为每条匹配边匹配图 G 的两个顶点，故上界是显然的。
为证明下界，对图的边数 ε 作数学归纳法。
1ε = 时结论显然成立。
假设对任何不超过 k 条边的图 G，下界都成立。
设 G 是具有 k+1 条边且无孤立点的图。若 G 中每条边都有至少一个端点是 1 度顶点，则
G 的每个连通分支都是星 (星是一个完全二部图，其中一个分部仅含一个点,如 K
1,s
)。一颗星
K
1,s
的最大匹配只有一条边，且
1,1,
(K ),(K ) 1
ss
ssυΔ= =+,因此
1,
1,
1,
(K )
(K ) 1
1(K)
s
s
s
υ
α′ ==
+Δ
。
设 G 由 r 颗星
12
,,
r
TT Tnull 组成（ 1r ≥ ）,则
U
T=N(S)
X \ S
S
10
1
11
()
() (G)
(G) ( )
1()1+(G)1(G)
r
irr
ii
i
ii
i
T
T
T
T
υ
υ υ
αα
=
==
′′ ≥=
+Δ Δ +Δ
∑
∑∑
。
下设 G 中存在边 e，其两端点都不是 1 度点。设 G e? 有 m 个连通分支
12
G,G,G
m
null
（ 1m ≥ ）,则每个连通分支都不是孤立点，且边数都不超过 k。因此根据归纳假设,
(G )
(G ),( 1,2,)
1(G)
i
i
i
im
υ
α′ ≥=
+Δ
null 。
从而
1
11
(G )
(G ) (G)
(G) (G ) (G )
1(G)1+( )1(G)
m
imm
ii
i
ii
i
e
Ge
υ
υ υ
αα α
=
==
′′ ′≥?= ≥ ≥ ≥
+Δ Δ? +Δ
∑
∑∑
。
归纳完成。证毕。
二、边覆盖
定义 5.2.2 设 )(GEL? 。若 G 的每个顶点都与 L 中至少一条边关联，则称 L 是 G 的 边覆盖 。
若边覆盖 L 的任何真子集都不是 G 的边覆盖，则称 L 是 G 的 极小边覆盖 。 G 的含边数最少的边覆盖称为 G 的 最小边覆盖,其所含边的数目称为 G 的 边覆盖数,记为 )(Gβ′ 或 β′。
例如，在下图中,},,{
6321
eeeL = 和 },,{
7322
eeeL = 都是边覆盖，也是极小边覆盖，还是最小边覆盖； },,,{
75413
eeeeL = 是边覆盖，但不是极小边覆盖。
z 点独立数与边覆盖数的关系
定理 5.2.4 对任何图 G，都有 )()( GG βα ′≤ 。
证明：设 I 是 G 的最大点独立集。因 I 中点彼此不相邻，故至少要用 |I|条边才能覆盖住 I 中的所有顶点，故 )(||)( GIG βα ′≤= 。证毕。
z 边覆盖与边独立数（匹配数）的关系
定理 5.2.5(Gallai,1959) 若 0)( >Gδ,则 νβα =′+′ )()( GG 。
证明：设 M 是 G 的最大匹配。若 M 是 G 的完美匹配，则显然 α
ν
β ′==≤′
2
|| M,从而
ν
νν
βα =+≤′+′
22；若 M 不是 G 的完美匹配,U 是 M 非饱和点之集。则 ][UG 是无边图
（否则在 G[U]中取一边可使 M 扩大） 。由于 0)( >Gδ,所以 U 的每个点在 G 中都至少与一
条边关联。对应于每个点取这样一条边，这些边的集合记为 E′。显然 EM ′∪ 是 G 的边覆盖，
e
1
e
3
e
5
e
7e6
e
2
e
4
11
且 φ=′EM ∩ 。因而（注意 M 中的边数为 α′,E′中的边数为 αν ′? 2 ）
αναναβ ′?=′?+′=′≤′ )2(|| EM ∪,即 νβα ≤′+′ 。
另一方面，设 L 是 G 的最小边覆盖。令 ][LGH =,则 ν== )()( GVHV (因 L 覆盖了 G
的所有顶点 )。设 M 是 H 的最大匹配,U 为 H 中 M 非饱和点集，则 H[U]是无边图，从而
||2|||\||||| MUMLML?=≥=? ν 。 （ *）
其中第一个等号用到 ML? ；不等号是因为 L-M 中每条边要么两端点都 M 饱和，要么只有一端点 M 不饱和。故 L-M 中每条边至多有一个点在 U 中。而且 U 中每个点至少由 L-M 中一条边关联。
由（ *）式,||| |LMυ+≥。又因 H 是 G 的生成子图，故 M 也是 G 的匹配。从而
||||MLα βυ′′+≥ +≥。证毕。
推论 5.2.1 图 G 的边覆盖数等于 G 的边独立数加上最大匹配非饱和点的个数。
证明：由定理 5.2.5,() () () ( 2 ())GGG Gβ υα α υ α′′′ ′=?=+?,注意到 ()Gα′ 是最大匹配的边数，故 2()Gυ α′? 是未被最大匹配饱和的点数。证毕。
该推论将求 G 的最小边覆盖集的问题转化为求 G 的最大匹配问题：求出 G 的一个最大匹配 M
*
，对于在 M
*
下未饱和的每个点，任选其一条关联的边，这些边与 M
*
的边放在一起便形成 G 的一个最小边覆盖。
推论 5.2.2 设 G 是二部图且 0)( >Gδ,则 )()( GG βα ′= 。
证明：由于 βανβα ′+′==+,而由 Konig-Egerváry 定理,βα =′,故 βα ′= 。证毕。
推论 5.2.3 设 0)( >Gδ,则 )()( GG βα ′≤′,等号成立当且仅当 G 有完美匹配；
证明：设 M
*
是 G 的最大匹配。则覆盖 M
*
关联的 2|M
*
|个点至少需要 |M
*
|条边。故
)(||)(
*
GMG βα ′≤=′ 。
等号成立时，由 Gallai 定理 νβα =′+′ )()( GG 知,να =′ )(2 G,故 M
*
是完美匹配。
推论 5.2.4 设 0)( >Gδ,则
（ 1） 对 G 的任一匹配 M 和任一边覆盖 L，有 |||| LM ≤ 。等号成立时 M 为完美匹配且 L 为最小边覆盖；
（ 2） 对 G 的任一匹配 M 和任一点覆盖 F，有 |||| FM ≤ 。等号成立时,M 为最大匹配且 F
为最小点覆盖；
（ 3） 对 G 中任一点独立集 I 和任一边覆盖 L，有 |||| LI ≤ 。等号成立时,I 为最大点独立集且 L 为最小边覆盖。
证明,（ 1）对任一匹配 M 和任一边覆盖 L，由推论 5.2.3，有 ||)()(|| LGGM ≤′≤′≤ βα 。
当 |||| LM = 时，上式成为 ||)()(|| LGGM =′=′= βα 。因而 M 是最大匹配,L 是最小边覆盖，且由推论 5.2.3 知，此时 M 是完美匹配。
12
（ 2）由定理 5.2.1,有 |||| FM ≤≤′≤ βα 。当 |M|=|F|时，上式成为 |||| FM ==′= βα,可见 M 是最大匹配而 F 是最小点覆盖。
（ 3）由定理 5.2.4 得,|||| LI ≤′≤≤ βα 。当 |||| LI = 时，上式成为 |||| LI =′== βα,可见此时 I 是最大点独立集而 L 是最小边覆盖。 证毕。
注,（ 1）对完美匹配 M 和最小边覆盖 L，必定 |||| LM = ；
（ 2）对最大匹配 M 和最小点覆盖 F，未必 |||| FM = 。例如
5
C,最大匹配含 2 边，但最小点覆盖含 3 点；
（ 3）对最大点独立集 I 和最小边覆盖 L，未必 |||| LI = 。同样可取
5
C 检验。
关于点覆盖数的估计，有下述结果。
定理 5.2.6 设图 G 无孤立点，则
(G)
(G)
21(G
υυ
β
Δ
′≤≤
+Δ
。
证明：由定理 5.2.5,() ()GGα βυ′′+=，得 () ()GGβ υα′ ′=? 。再利用定理 5.2.3，
(G)
1(G) 2
υ υ
α
′≤≤
+Δ
，由此立即可得结论。证毕。
最后再给出一个支配数与点（边）独立数、点（边）覆盖数的关系作为本节的结束。
定理 5.2.7 设图 G 无孤立顶点，则 (G) min{ (G),(G),(G),(G)}γ αα ββ′ ′≤ 。
证明,(G) (G)γ α≤ 是定理 5.1.10 的结论。
由于无孤立顶点的图中每个点覆盖都是支配集，因此 (G) (G)γ β≤ 成立。
设 E
1
是 G 的一个最小边覆盖，则 G 的每个顶点是 E
1
中至少一条边的端点。对 E
1
中每条边取其一个端点，所形成的顶点集合记为 D,则 D 是 G 的一个支配集。因此
1
(G) | D | | E | (G)γ β′≤≤= 。
设 M 是 G 的一个最大匹配，对 M 中任一条边 euv=,端 点 u,v 中至少有一个的所有邻点都是 M 饱和点（否则,u,v 都有 M 不饱和邻点，则有 M 增广路，与 M 是最大匹配矛盾） 。无妨设 u 的所有邻点都是 M 饱和的，则称 e 的另一端点 v 称为 e 的可选端点。对 M 中每条边取其一个可选端点，形成一个集合 D，则 D 是 G 的一个支配集（对任一个 M 饱和顶点，与它关联的 M 匹配边必有一个端点在 D 中，故被 D 支配；对每个 M 非饱和顶点 w，其邻点必定是
M 饱和的,按 D 的选法,其邻点必在 D 中,因此 w 也被 D 支配） 。 于是 (G) | D | | M | (G)γ β≤ == 。
证毕。
有关边覆盖的更多内容可参看 [18]。
[18] A,Schrijver,Combinatorial Optimization Polyhedra and Efficiency,New York,NY,
Springer-Verlag,2003,
13
§5.3 支配集、点独立集、点覆盖集的求法
一、应用背景
1,应急增援中心的选址
欲在 n 个地点
n
vvv,,,
21
null 设置若干个应急中心，使得每个地点都与至少一个应急中心相邻（有直达通路） 。同时，为了减少造价，应急中心的数目要尽可能少。问应设多少个？如何设置？
图论模型：以 n 个地点为顶点集，两点之间有直达通路时，连边，得一图 G。问题是：求图
G 的最小支配集。
2,收款台的设置
某商场实行收款台收款制度。为使顾客在任何一个货架通道都能看到至少一个收款台，
问至少应设置多少个收款台？设在什么位置？
类似的问题有：执勤岗哨的设置问题、交通监控器的设置问题等。
图论模型：构作图 G：货架通道为 G 的边，通道交叉点为 G 的顶点。问题是求图 G 最小点覆盖集。
3,通信信号差错控制问题
设某信息传输系统的基本信号集合为 },,,{
521
sssS null= 。由于干扰等原因，使得接收端收到的信号可能发生错乱。比如发送
1
s,可能收到
2
s 。通过统计分析已经知道哪些信号间容易发生错乱。例如，容易发生错乱的情况如下图所示。为了能从收到的输出信号辨识出正确的输入信号，我们不能使用所有 5 个信号来传送信息，而只能从中选出一部分使用。问如何选取尽可能多的可用信号？
图论模型,构作图 G：以
521
,,,sss null 为顶点，若信号
i
s 容易错收为
j
s,则从顶点
i
s 向
j
s 连一条有向边。问题是求有向图 G 中的最大点独立集。
目前还没有有效算法来求任意给定图的极小点覆盖集、极大点独立集和极小支配集。下面介绍的方法用到布尔代数。
二、逻辑运算及其性质
设 G 是一个图，用
i
v 表示事件“包含顶点
i
v,；
ji
vv + 或
ji
vv ∨ 表示事件“要么包含顶点
i
v,要么包含顶点
j
v,；
ji
vv 或
ji
vv ∧ 表示事件“即包含顶点
i
v 又包含顶点
j
v,。则如下逻辑运算律成立,
s
1
s
2
s
3
s
4 s5
发送
s
1
s
2
s
3
s
4 s5
接收
s
1
s
5
s
4
s
3
s
2
14
（ 1）交换律：
ji
vv +
ij
vv +=,
ji
vv
ij
vv= 。
（ 2）结合律：
kji
vvv ++ )()(
kji
vvv ++=,
kji
vvv )()(
kji
vvv=
（ 3）分配律,)(
kji
vvv +
kiji
vvvv +=,
kji
vvv )( +
kjki
vvvv +=
（ 4）吸收律,
iii
vvv =+,
iii
vvv =,
ijii
vvvv =+,
ijii
vvvv =+ )( 。
三、算法
1,极小点覆盖和极大独立集
（ 1） 由定义,V(G)的子集 C 是 G 的极小点覆盖? 对每个 )(GVv
i
∈,要么 Cv
i
∈,
要么 CvN
iG
)( 。
（ 2）由推论 5.1.3,V(G)的子集 C 是 G 的极小点覆盖? V(G)\C 是 G 的极大点独立集。
由此可得求所有极小点覆盖和极大独立集的方法,
将表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏∏
展开成积之和的形式，则每一项表示一个极小点覆盖，而这些极小点覆盖的补集给出了所有极大点独立集。表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏ ∏
通常记为
12
(,,,)vv v
υ
null 。
例 5.3.1 求下图的所有极小点覆盖和极大点独立集。
解,),,,(
721
vvv null? = )(
421
vvv + )(
65312
vvvvv + )(
75423
vvvvv + )(
65314
vvvvv +
)(
74325
vvvvv +? )(
7426
vvvv + )(
6537
vvvv +
＝
6531
vvvv ＋
65432
vvvvv ＋
7542
vvvv ＋
7432
vvvv 。
故极小点覆盖有,
1
C ＝ },,,{
6531
vvvv,},,,,{
654322
vvvvvC =,},,,{
75423
vvvvC =,},,,{
74324
vvvvC = 。
而极大点独立集有,
==
11
CI },,{
742
vvv,
==
22
CI },{
71
vv,==
33
CI },,{
631
vvv,
==
44
CI },,{
651
vvv 。
同时，不难得出最小点覆盖和最大点独立集。
2,极小支配集
由定理 5.1.3，上述方法得出的极大独立集必是 G 的极小支配集。但一般情况下这并未包含 G 的所有极小支配集。求所有极小支配集的方法为,
v
7
v
6
v
5
v
4
v
3
v
2
v
1
15
将表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏∑
展开成积之和的形式，则每一项给出一个极小支配集。表达式
1()
()
i
i
iuNv
vu
υ
=∈
+
∏∑
通常记为
12
(,,,)vv v
υ
ψ null 。
例 5.3.2 求下图的所有极小支配集。
解：
12
(,,,)vv v
υ
ψ null ＝ )(
4321
vvvv +++ )(
412
vvv ++ )(
413
vvv ++
)(
653214
vvvvvv +++++? )(
645
vvv ++ )(
546
vvv ++
＝
51
vv ＋
61
vv ＋
4
v ＋
532
vvv ＋
632
vvv
故 G 的所有极小支配集为,},{
51
vv,},{
61
vv,}{
4
v,},,{
532
vvv,},,{
632
vvv 。
上述求极小点覆盖集、极大点独立集和极小支配集的算法是指数阶的。例如对于求极小点覆盖集、极大点独立集的算法，我们需要处理 )(
1)(
∏∏
=∈
+
ν
ivNu
i
i
uv 的展开式中 2
υ
个乘积项，因此计算复杂度至少是 O(2 )
υ
。但目前尚没有更好的精确型算法求极小点覆盖集、极大点独立
集和极小支配集的最优解。
设计求极小点覆盖集、极大点独立集和极小支配集的近似算法，或在某些约束条件下寻找它们的精确算法，是目前的一个研究热点。文献 [19]~[21]与点覆盖算法有关,[22]~[24]涉及到点独立集的算法,[25],[26]研究有关支配集的近似算法和分布式算法，文献 [27]~[30]研究无线通信网络中连通支配集的算法。
[19] R,Bar-Yehuda and S,Even,A local-ratio theorem for approximating the weighted vertex cover
problem,Annals of Discrete Mathematics,25(1985) 27-45,
[20] K.L,Clarkson,A modification of the greedy algorithm for vertex cover,Information Processing
Letters,17(1983) 23-25,
[21] D.S,Hochbaum,Approximation algorithms for set covering and vertex cover problems,SIAM
Journal on Computing,11(1982) 555-556,
[22] Thomas Erlebach and Klaus Jansen,Conversion of coloring algorithms into maximum weight
independent set algorithms,Discrete Applied Mathematics,148(2005),107-125,
[23] V,E,Alekseev,Polynomial algorithm for finding the largest independent sets in graphs without
forks,Discrete Applied Mathematics,135(2004),3-16,
[24] Shuichi Sakai,Mitsunori Togasaki and Koichi Yamazaki,A note on greedy algorithms for the
maximum weighted independent set problem,Discrete Applied Mathematics,126(2003),313-322
[25] Toshihiro Fujito and Hiroshi Nagamochi,A 2-approximation algorithm for the minimum weight
edge dominating set problem,Discrete Applied Mathematics,118(2002),199-207,
[26] Lucia D,Penso and V.C.Valmir C,Barbosa,A distributed algorithm to find k-dominating sets,
Discrete Applied Mathematics,141(2004),243-253,
v
6
v
5
v
4
v
3
v
2
v
1
16
[27] I,Stojmenovic,M,Seddigh,and J,Zunic,Dominating sets and neighbor elimination based
broadcasting algorithms in wireless networks,Proc,IEEE Hawaii Int,Conf,On System Sciences,
Jan,2001,
[28] J,Wu,and H.L.Li,On calculating connected dominating set for efficient routing in ad hoc
wireless networks,Proceedings of the 3
rd
ACM International Workshop on Discrete Algorithms and
Methods for Mobile Computing and Communications,1999,7-14,
[29] S,Guha,and S,Khuller,Approximation algorithms for connected dominating sets,
Algorithmica,20:4(1998),347-387,
[30] B,Das,and V,Bharghavan,Routing in ad hoc networks using minimum connected dominating
sets,ICC’97,Montreal,Canada,June,1997,
§5.4 Ramsey 数
一、团（ clique）
定义 5.4.1 设 )(GVQ?,若导出子图 ][QG 是完全图，则称 Q 是 G 的一个 团 。若给团 Q 添加 QGV \)( 中任何顶点，导出子图都不再是团，则称 Q 是一个 极大团 。图 G 的含顶点数最多的团称为 G 的 最大团,其顶点数称为 G 的 团数,记为 ()Gω 。含 k 个顶点的团称为 k-团 。
例如，在下图中,},,{
210
vvv 和 },,{
320
vvv 都是 G 的团。前者是极大团，而后者不是。
},,,{
4320
vvvv 是 G 的最大团。
注,（ 1）任何非平凡的树，其团数均为 2。
（ 2） Q 是 G 的团当且仅当 Q 是 G 的独立集； Q 是 G 的极大（最大）团当且仅当 Q 是 G 中极大（最大）独立集
关于团有许多研究专题，文献 [31]~[36]分别涉及到最大团问题、最大赋权团问题、最大团覆盖问题、边 -团覆盖、团独立集、团划分等。团也与图的染色有密切关系，这将在下一章讨论。
[31] Patric R,J,?sterg?rd,A fast algorithm for the maximum clique problem,Discrete Applied
Mathematics,120(2002),197-207
[32] S,Busygin,A new trust region technique for the maximum weight clique problem,Discrete
Applied Mathematics,154(2006),2080-2096,
[33] J.M.Keil,and L.Stewart,Approximating the minimum clique cover and other hard problems in
subtree filament,Discrete Applied Mathematics,154(2006),1983-1995,
[34] G.Durán,M.C.Lin,S.Mera and J.L.Sawarcfiter,Algorithms for clique-independent sets on
subclasses of circular-are graphs,Discrete Applied Mathematics,154(2006),1783-1790,
v
7
v
8
v
2
v
1
v
5
v
6
v
3
v
4
v
0
17
[35] T.S,Michael,and T.Quint,Sphericity,cubicity,and edge clique covers of graphs,Discrete
Applied Mathematics,154(2006),1309-1313,
[36] I,Charon,and O,Hudry,Noising methods for a clique partitioning problem,Discrete Applied
Mathematics,154(2006),754-769,
显然，团和点独立集是两个互补的概念。即顶点子集 Q 是图 G 的团当且仅当 Q 是补图 G
的独立集。 直观上判断,一个图如果没有大的团则应该有大的点独立集。 这一问题属于 Ramsey
理论的研究范畴。
二,Ramsey 数
先来看一个例子。
例 5.4.1 任意 6 个人的聚会上，总有 3 人互相认识或互不认识。
证明,用 6 个顶点代表六个人，构造 6 阶完全图 K
6
。如果两人互相认识，则将它们的连边染红色，否则染蓝色。则问题转化为：证明将 K
6
的边进行任意红、蓝染色，一定会出现红色三角形或蓝色三角形。
在完全图 K
6
中任取一顶点记为 v
1
，
由组合学中的鸽笼原理，以 v
1
为端点的 5 条连边中至少有 3 条是同色的。不妨设边 v
1
v
2
,v
1
v
3
,v
1
v
4
都为红色。现考察连接 v
2
,v
3
,v
4
的 3 条边，
若这 3 条边全为蓝色，则△v
2
v
3
v
4
就是一个同色三角形（蓝色） 。否则,3 条边中必有红色边，
无妨设为 v
2
v
3
，则△v
2
v
3
v
4
构成一个同色三角形（红色） 。证毕。
上述问题可描述为：对完全图 K
6
的边任意染红蓝两种颜色后，要么有红色三 角形，要么有蓝色三角形。一般地，有,
用红、蓝两种颜色对完全图的边染色，要求不论怎么染，都能要么出现染红色的 p 阶完全子图 K
p
，要么出现染蓝色的 q 阶完全子图 K
q
，这样的完全图至少应有多少个顶点 (即至少应为多少阶图 )？
如果将红色边形成的子图记为 G，则蓝色边形成的子图是 G 的补图。因此上述问题也可
描述为,
求 min{ |r 每个 r 阶图 G 要么本身含有 p-团，要么其补图 G 含有 q-团 }。
亦即,求 min{ |r 每个 r 阶图 G 要么有 p-团，要么有含 q 个顶点的独立集 }。
这个问题称为 Ramsey 问题,所求的最少顶点数（即完全图应具有的最小阶数）称为
Ramsey 数,记为 (,)rpq。特别地，定义 r (1,q) = r ( p,1) =1。
Ramsey 问题的上述三种表述经常交替使用。例 5.4.1 实际上证明了 r (3,3) ≤ 6。
定理 5.4.1 r (3,3) = 6。
证明：由例 5.4.1,r (3,3) ≤ 6。另一方面，长为 5 的圈 C
5
既无 3-团又无 3 个点的独立集，这表明 r (3,3) ≥ 6。因此 r (3,3) = 6。证毕。
定理 5.4.2 r (3,4) = 9。
证明,先证 r (3,4) ≥ 9。
对具有 9 个顶点的任何图 G，必存在顶点 v
0
，其度
0
() 3dv ≠ 。 （否则,G 的顶点度之和为奇数） 。
18
如果
0
() 4dv ≥,设 v
1
,v
2
,v
3
,v
4
是其 4 个邻点。若 v
1
,v
2
,v
3
,v
4
有一条连边，比如 v
1
v
2
，
则 v
0
,v
1
,v
2
构成 G 的一个 3-团；否则,v
1
,v
2
,v
3
,v
4
间没有连边，形成 G 的一个 4 顶点独立集。
如果
0
() 3dv <,则 G 中至少有 6 个顶点与 v
0
不相邻。由于 r (3,3)=6，故这 6 个顶点在 G
导出的子图要么有 3-团，要么有含 3 个顶点的独立集。如果是前者，则结论已成立；如果是后者，则与 v
0
一起构成含 4 个顶点的独立集。
综上,具有 9 个顶点的任何图 G,要么有 3-团,要么有 4 个顶点的独立集,因此 r(3,4) ≥ 9。
另一方面，如下所示的 8 阶图既无 3-团，又无 4 个顶点的独立集，这说明 r (3,4) ≤ 9。于是 r (3,4) = 9。证毕。
定理 5.4.3 r(4,4) =18。
证明,对具有 18 个顶点的任何图 G，任取其一个顶点 v
0
。
如果
0
() 9dv ≥,取其 9 个邻点,将这 9 个邻点在 G 中的点导出子图记为 G
1
,由定理 5.4.2，
r (3,4) = 9，故 G
1
中要么有 3-团，要么有 4 个顶点的独立集。若是前者，则这个 3-团与 v
0
组成 G 的一个 4-团；若是后者，则这个独立集也是 G 中的 4 个顶点的独立集。
如果
0
() 9dv <,则与 v
0
不相邻的顶点至少有 9 个，即在 G 的补图 G 中 v
0
至少有 9 个邻点。与以上类似可得,G 中要么有 4-团，要么有 4 个顶点的独立集。从而 G 中要么有 4-团，
要么有 4 个顶点的独立集。
以上结果表明 r(4,4) ≤ 18。
下证 r (4,4) > 17。我们只需找出对 K
17
的边的一种红蓝染色，使得不出现同色的 K
4
即可。
在一个圆周上画出 17 个等分点，将其依次编号为 v
0
,v
1
,v
2
,…,v
16
，把整数 1,2,…,16 分为两组,
X={1,2,4,8,9,13,15,16},Y={3,5,6,7,10,11,12,14}。
按下列规则对 K
17
进行红、蓝边染色：对于边,(0,16)
ij
vv i j≤ ≤,
当 ||ijX?∈时，将边
ij
vv 染成红色；当 ||ijY? ∈ 时，将边
ij
vv 染成蓝色。
按此规则，下列边被染成红色
01 02 04 08 09 013 015 016
(,),(,),(,),(,),(,),(,),(,),(,);vv vv vv vv vv vv vv vv
12 13 15 19 116
(,),(,),(,),(,),,(,)vv vv vv vv vvnull ；
… … … … … … … … … …
15 16
(,)vv 。
其余边全染蓝色。可以检验，在这样的颜色下 K
17
中没有同色的 K
4
。这表明 r(4,4) >17。
由以上两方面便得 r(4,4) = 17。证毕。
19
有时用“边染色”的说法进行论证更为直观和简便。比如上一定理的前半部分可以用边染色方法论述如下。
设对 K
18
的边进行了任意的红、蓝染色。考察 K
18
中从任一顶点 v
0
出发的 17 条边。由鸽笼原理知，其中至少有 9 条边是同色的，不妨设为红色。这 9 条边异于 v
0
的 9 个端点构成完全子图 K
9
，由 r (3,4) =9 知，该 K
9
中要么有红色 K
3
，要么有蓝色 K
4
。若是前者，则这个红色
K
3
与 v
0
一起便构成了红色 K
4；若是后者，则本身就是一个蓝色 K
4
。由此便知 r (4,4) ≤ 18。
三,Ramsey 数的性质
定理 5.4.4
（ 1） r ( p,q ) = r ( q,p );
（ 2） r ( 2,q ) = q,r ( p,2 ) = p;
（ 3）当 p,q ≥ 2 时，有 r ( p,q ) ≤ r ( p,q –1 )+ r ( p –1,q )，且当 r ( p,q –1 )和 r ( p –1,q )都是偶数时，不等号严格成立。
证明,(1) 设 r ( p,q ) = k，则对任何 k 阶图 G，其补图 G 也是一个 k 阶图，故 G 中要么有 p-
团，要么有 q 个顶点的独立集，从而 G 中要么有 q-团，要么有 p 个顶点的独立集，由 G 的任意性，知 r ( q,p ) = k。
(2) 对任一个 q 阶图，要么至少有一条边，任何一条边的两个端点即构成 2-团；要么没有边，此时所有 q 个顶点构成一个独立集。故 r ( 2,q ) = q。同理可证 r ( p,2 ) = p。
(3) 我们用“边染色”的方法来该性质，读者可尝试用团和独立集的方式改写这个证明。
令 n = r ( p,q–1 ) + r ( p –1,q )，下面证明，用红蓝两色对 K
n
的边任意染色后，必有红色的 K
p
或蓝色的 K
q
,从而 r ( p,q ) ≤ n,
事实上，任取 K
n
的一个顶点 v,设 v 连出的 n?1 条边中有 n
1
条红色边,n
2
条蓝色边。则
n
1
+ n
2
= n –1 = r ( p,q–1 ) + r ( p –1,q ) –1 。
1）若 n
1
≥ r ( p –1,q)，则 v 通过红边相连的顶点至少有 r ( p –1,q) 个。按照 r ( p –1,q) 的定义，这 r ( p –1,q) 个点构成的完全图 K
r(p?1,q)
中要么含有红色的 K
p?1
，要么含有蓝色的 K
q
。
若是前者，则该红色的 K
p?1
与 v 便构成 K
n
中一个红色的 K
p；若是后者，则自然有蓝色的 K
q
。
2）若 n
1
< r ( p –1,q)，则 n
2
≥ r ( p,q–1 )。与上述过程同样可 证得：红蓝染色后的 K
n
中必有红色的 K
p
或蓝色的 K
q
。
因此，用红蓝两色对 K
n
的边任意染色后，必有红色的 K
p
或蓝色的 K
q
,故
r ( p,q ) ≤ n = r ( p,q –1 )+ r ( p –1,q )。
下面证明当 r ( p,q –1 )和 r ( p –1,q )都是偶数时,不等号严格成立。 设 m= r ( p,q–1 ) + r ( p
–1,q ) –1。因 m 是奇数，故用红蓝两色对完全图 K
m
的边任意染色后，必有某点 v
0
关联的边有偶数条被染红（若每点处都有奇数条红边，则所有红色边导数的子图中顶点度之和为奇数，
这是不可能的） 。因
0
()dv = m?1=r ( p,q–1 ) + r ( p –1,q ) –2。如果与 v
0
关联的 m?1 条边中红色边至少有 r ( p –1,q )条，则与上述（ 1）同样可证,K
m
中必有红色的 K
p
或蓝色的 K
q；如果与 v
0
关联的红色边少于 r ( p –1,q )条，则由 v
0
的取法（与 v
0
关联的红色边有偶数条）,v
0
至多有 r ( p –1,q )?2 条红边，因此至少有 r ( p,q–1 )条蓝边。此时与上述（ 2）同样可知,K
m
中必有红色的 K
p
或蓝色的 K
q
。
20
由以上可见 r ( p,q–1 ) + r ( p –1,q ) –1 个顶点的完全图 K
m
的边任意红蓝染色，必有红色的 K
p
或蓝色的 K
q
，故 r ( p,q ) ≤ r ( p,q –1 )+ r ( p –1,q ) –1< r ( p,q –1 )+ r ( p –1,q )。证毕。
例 5.4.2 证明,r ( 3,5 ) =14。
证,由性质 (3),r ( 3,5 ) ≤ r ( 3,4 )+ r (2,5) = 9 + 5 = 14。
另一方面，按如下方法对完全图 K
13
的边进行红、蓝染色：设 K
13
的顶点为 0,1,2,···,12，
将这些顶点依次放在一个圆周的 13 等分点上。当点 i 与 k 满足
k = i+1,i+5,i+8,i+12,(mod 13),
时，点 i 与 k 之间连红色边；否则，连蓝色边。可以检验，这样构成的对 K
13
的红蓝染色，既无红色的 K
3
，又无蓝色的 K
5
。这表明 r ( 3,5 ) ≥ 14。
由以上两方面即知,r ( 3,5 ) =14。证毕。
四,Ramsey 数的上下界
定理 5.4.5 设,2pq≥,则
2
(,)
1
pq
rpq
p
+?
≤
，其中
2
1
pq
p
+?
表示从 2pq+?个元素中取 1p? 个元素的组合数。
证明,对 p q+ 用归纳法。
由性质，
22
(2,)
21
q
rq q
+?
==
，
22
(,2)
1
p
rp p
p
+?
==
,可见当 1p = 或 1q = 时，
结论成立。假定对满足 4 p qst≤+<+的所有正整数对 (,)p q,结论都成立。则
332
(,) ( 1,) (,1)
21 1
st st st
rst rs t rst
sss
+?+?+?
≤?+?≤ + =
。
这里用到了组合恒等式
11
1
nn n
mm m
+=
。证毕。
定理 5.4.6 当 3q ≥ 时，
2
3
(3,)
2
q
rq
+
≤ 。
证明：对 q 进行归纳。当 3q = 时,(3,3) 6r =,且
2
3
6
2
q +
=,结论不等式成立。
当 4q = 时,(3,4) 9r =,且 (3,1) 6rq? =,而
2
319
22
q +
=,结论不等式严格成立。
假设 1qk≤?时结论成立。则 qk= 时,
22
(1)3 4
(3,) (2,) (3,1)
22
kk
rk rk rk k
++
≤+?≤+ =。
下证上述不等式严格成立，这样便证明了
2
3
(3,)
2
k
rk
+
≤ 。
事实上，若 k 是奇数，则
2
4k + 是奇数，故此时，
2
4
(3,)
2
k
rk
+
< ；下设 k 是偶数。此
21
时如果
2
(1)3
(3,1)
2
k
rk
+
<,则所证不等式严格成立；如果
2
(1)3
(3,1)
2
k
rk
+
=,
则因 k 是偶数，从而 (2,)rk k= 和
22
(1)3
(3,1) 2
22
kk
rk k
+
==?+都是偶数，由定理
5.4.4，此时 (3,) (2,) (3,1)rk rk rk<+?，故所证不等式严格成立。证毕。
当 p q= 时,Ramsey 数 (,)rpp称为 对角 Ramsey 数,对角 Ramsey 数的一个下界如下。
定理 5.4.7 当 3p ≥ 时，
2
(,) 2
p
rpp≥ 。
证明,对 n 阶完全图 K
n
进行任意红蓝边染色时，由于其每条边都有染 红和染蓝两种可能，而
K
n
共有
(1)
2
nn?
条边，故不同的染色方案共有
(1)
2
2
nn?
种。对于 K
n
中指定的 p 个顶点，它们之间的连边有
(1)
2
pp?
条。在 K
n
的所有染色方案中，使这 p 个顶点形成的完全子图 K
p
全染红边的方案有
n(n 1) ( 1)
22
2
pp
种（除 K
p
的边外，其余
(1)
2
nn?
(1)
2
pp?
条边每条有 2 种染法） 。
因 K
n
中指定 p 个顶点的方式有
n
p
种，故在 K
n
的所有红蓝边染色方案中，出现红色 K
p
的染法有
n
p
n(n 1) ( 1)
22
2
pp
种。它占染色方案总数的比例为
(1) ( 1)
22 (1)
(1)
2
2
(1)
2
2
2
2
!
2
nn pp
pp
pp p
nn
n
np
n
p p
=<
。
假定
2
2
p
n <,则
2
(1) (1)
22 (1)
22 2
(1)
2
2
22 2 2 2 2 2 1
!!123 2
2
nn pp
ppp p
nn
n
p
pp p
< == <。
这表明在 K
n
的所有红蓝边染色方案中，出现红色 K
p
的染法不到染色方案总数的一半。由两种颜色的对等性,出现蓝色 K
p
的染法也不到染色方案总数的一半。 有此可知,只要
2
2
p
n <,
则必有 K
n
的一种红蓝边染色方案，即不出现红色 K
p
也不出现蓝色 K
p
。故
2
(,) 2
p
rpp≥ 。证毕。
由定理 5.4.7 容易得到下列推论（习题） 。
推论 5.4.1 设 min{,}mpq=,则
2
(,) 2
m
rpq≥ 。
下表列出了目前已经确定的所有 Ramsey 数和一些上下界，此表引自 [37]和 [38]。
[37] D.B.West,Introduction to Graph theory (2
nd
edition),2001
[38]《图论及其应用,（张先迪、李正良编）高教出版社,2005。
22
一些 r(p,q)的值和界
q
p
3 4 5 6 7 8 9 10 11 12 13 14 15
3 6 9 14 18 23 28 36 40/43 46/51 51/60 59/69 66/78 73/89
4 18 25 35/41 49/61 55/84 69/115 80/149 96/191 106
/238
118
/291
129
/349
134
/417
5 43/49 58/87 80/143 95/216 121/316?/442
6 102/165 109/298 122/495 153/780?/1171
7 205/540?/1031?/1713?/2826
8?/1870 282/3583?/6096
9?/6625 565/
12715
10?/23854 798/?
表中 a/b 表示 a 为下界,b 为上界。
五,Ramsey 数的一般形式
定义 5.4.2 设 p
1
,p
2
,···,
p
m
是一组给定的大于 1 的正整数，用 m 种颜色 C
1
,C
2
,···,
C
m
对完全图的边染色，要求不论怎么染，都能要么出现 C
1
色的完全子图
1
K
p
,要么出现 C
2
色的完全子图
2
K
p
,···,要么出现 C
m
色的完全子图 K
m
p
,这样的完全图至少应有多少个顶点 (即至少应为多少阶图 )？ 这个问题称为 一般 Ramsey 问 题,所求的最少顶点数 (即完全图的阶数 )称为 一般
Ramsey 数,记为 r ( p
1
,p
2
,···,
p
m
)。
例 5.4.3 有 17 位学者，每人给其他人各写一封信，讨论三个问题中的某一个问题，且两人之间互相通信讨论的是同一问题。证明至少有三位学者，他们之间通信讨论的是同一个问题。
证明,此问题等价于证明用红黄蓝三种颜色对 K
17
的边任意染色后，必出现同色三角形 K
3
。
设 v
0
,v
1
,v
2
,…,v
16
是 K
17
的顶点。对 K
17
的边任意进行红黄蓝三染色后,v
0
与其余 16 点的连边中至少有
16
6
3
=
条同色边，无妨设为 v
0
v
1
,v
0
v
2
,···,v
0
v
6
这六条边被染红色。考虑由
v
1
,v
2
,…,v
6
组成的完全子图 K
6
。如果其中有一条红色边，比如 v
1
v
2
，则 v
0
,v
1
,v
2
三点便组成红色三角形；如果其中没有红色边，则 K
6
的边全为黄蓝两色，归结为 K
6
的边 2 染色问题，由例
5.3.1 知，其中必含有黄色三角形或蓝色三角形。证毕。
关于一般 Ramsey 数，有如下类似于定理 5.4.4 的性质。
（ 1）对正整数 p
1
,p
2
,…,p
m
的任一种排列
12
,,,
m
ii i
p ppnull,有
r ( p
1
,p
2
,···,
p
m
)= r (
12
,,,
m
ii i
p ppnull );
（ 2） r ( 2,p
1
,p
2
,…,p
m
) = r ( p
1
,p
2
,···,
p
m
);
（ 3） r ( p
1
,p
2
,···,
p
m
)≤ r ( p
1
1,p
2
,···,
p
m
)+ r ( p
1
,p
2
1,···,
p
m
)+ ··· + r ( p
1
,p
2
,···,
p
m
1 )?m+2;
（ 4） r ( p
1
+1,p
2
+1,···,
p
m
+1)≤
12
12
()!
!! !
m
m
p pp
pp p
+++null
null
。
23
其中（ 1） ~（ 3）的证明与定理 5.4.4 类似,（ 4）的证明与定理 5.4.5 类似。
Greenwood和 Gleason 已经证明,r (3,3,3)=17。 另有一些一般 Ramsey 数已获得其上下界。
Ramsey 理论是一个十分精彩而又相当难的研究方向。 Ramsey 数有多种推广形式。有关更深入的内容可参看专著 [39],[40]。
[39] T.D,Parsons,Ramsey graph theory,in Selected Topics in Graph Theory (L,W,Beineke,and
R.J,Wilson eds.),Academic Press,London,(1978) 361-384,
[40] R.L,Graham,B.L,Rothschild,and J.E,Spencer,Ramsey Theory,Wiley,New York,1990,
第五章习题
1,证明：图 G 是二部图当且仅当对 G 的每个子图 H 均有 )(
2
1
)( HH να ≥ 。
2,设 G 是一个二部图,证明
1
(G) (G)
2
αν= 当且仅当 G 有一个完美匹配。
3,证明：图 G 是二部图当且仅当对 G 的每个适合 0)( >Hδ 的子图 H 均有 )()( HH βα ′= 。
4,如图 G，求,
（ 1） G 的所有极小支配集及支配数；
（ 2） G 的所有极小点覆盖集及点覆盖数；
（ 3） G 的所有极大点独立集及点独立数；
（ 4） G 的所有极大匹配及匹配数；
（ 5） G 的所有极小边覆盖及边覆盖数。
5,下图是连接 10 个城市的宽带流媒体骨干网络的结构示意图。在这个网络上，用户可以进行通信或获取各种网络信息，也可以召开网络会议、进行远程教学，还可以实时在线点播音乐、电影和电视剧、玩电子游戏或视屏聊天。现在网络设计者想要在部分节点设置一些大型数据库存放网络资源供用户下载，这些数据库完全相同并需要定期更新。为了节省网络带宽和缩短用户下载时延，要求每个城市经过至多一跳（即一条边）便能访问到数据库。
另一方面，出于建设成本和更新维护成本的考虑，设计者又希望设置尽可能少的数据库达到上述要求。请建立这一问题的图论模型，并帮设计者找出一个最优的设置方案，同时要解释你的方案为什么是最优的。
6,利用 Konig 定理证明：任一个二部图 G 有一个至少含
(G)
(G)
ε
Δ
条边的匹配。并由此证明：设
H 是完全二部图 K
n,n
的一个子图，如果 (H) ( 1)knε >?,则 H 中存在至少含有 k 条边的匹配。
7,设 G 是一个非平凡简单图,证明,（ 1） (G)
ε
αυ≤?
Δ；（ 2） 如果 G 是正则图,则 (G)
2
υ
α ≤ 。
a
e
d
c
b
f
v
1
v
4
v
3
v
2
v
5
24
8,设 G 是恰含一个圈的非二部图，证明
1
(G)
2
υ
α
≥
。
9,设 G 是一个无孤立点的图,M 是 G 的一个极大匹配,L 是 G 的一个极小边覆盖。证明,
（ 1） M 是最大匹配当且仅当 M 含于某个最小边覆盖中；
（ 2） L 是最小边覆盖当且仅当 L 包含一个最大匹配。
10,设 G 是一个简单图，其中任意 k 个顶点的度之和小于 nk?,证明图 G 的任意极大独立集的顶点数大于 k,
11,表述支配数为 1 的图的特征。
12,找出支配数和点覆盖数不相等的最小树。
13,
n
C 和
n
P 分别表示有 n 个顶点的圈和路。给出求 ()
n
Cγ 和 ()
n
Pγ 的公式。
14,设 G 是一个简单图，证明,(G)
2
υ
γ ≤ 。 （提示：利用结论：若 S 是极小支配集，则 S也是支配集。 ）
15,设 G 是无孤立点的图，证明,(G) (G)
2
υ
γυβ′≤?≤。
16,设 G 是简单图，证明,（ 1） (G) (G)
1(G)
υ
γυ
≤≤?Δ
+Δ；
（ 2）
1diamG diamG
(G)
32
γυ
+
≤≤?
。
17,证明：若图 G 的直径至少是 3，则 (G) 2γ ≤ 。
18,确定 Petersen 图的支配数。
19,(1) 证明：对 9 个顶点构成的完全图 K
9
，将它的边进行任意红、蓝染色后，一定会出现同色的三角形或同色的 K
4
。
(2) 对完全图 K
8
，找出一种对其边进行红蓝染色的方案，使得既不出现红色的 K
3
又不出现蓝色的 K
4
。
20,设 min{,}mpq=,证明
2
(,) 2
m
rpq≥ 。
21,证明：对任意正整数整数 p
1
,p
2
,…,p
m
，有 r ( p
1
,p
2
,···,
p
m
) ≤ r ( p
1
,r(p
2
,···,
p
m
))。
22,证明,（ 1）对正整数 p
1
,p
2
,…,p
m
的任一种排列
12
,,,
m
ii i
p ppnull,有 r ( p
1
,p
2
,···,
p
m
)= r
(
12
,,,
m
ii i
p ppnull )。 （ 2） r ( 2,p
1
,p
2
,…,p
m
) = r ( p
1
,p
2
,···,
p
m
)。
23,证明,r (3,3,3) ≤ 17。
24,平面上有 6 个点，其中任意三点都能组成一个不等边三角形。证明：在这些点构成的所有三角形中，必有一个三角形的最短边是另一个三角形的最长边。
25,九位科学家在一次国际会议上相遇，发现他们中的任意 3 个人中，至少有 2 个人可以用同一种语言交谈。如果每个科学家最多会说 3 种语言，证明至少有 3 个科学家可以用同一种语言交谈。
