第五章支配集、独立集、覆盖集和 Ramsey数 本章讨论图中具有某种特性的顶点子集和边子集,以及它们之间的关系。本章所讨论的 图均为简单图。 §5.1支配集、点独立集、点覆盖集 、支配集( Domination set) 定义511设DcH(G),若对v∈V(G),要么u∈D,要么u与D中的某些顶点相邻 则称D为图G的一个支配集。如果一个支配集的任何真子集都不是支配集,则称它为极小支 配集。图G的含顶点最少的支配集称为最小支配集。最小支配集的顶点个数称为G的支配数, 记为y(G)或y。 例如,在下图中,D={0},D1={v1,v4,V7},D2={1,"3,V5,v6}都是G的支配集 前两个是极小支配集,D是最小支配集。y(G)=1 注:(1)最小支配集必是一个极小支配集,反之不然。 (2)任一支配集必含有一个极小支配集 (3)极小支配集不唯一,最小支配集一般也不唯一。 (4)对二部图G=(X,),X和Y都是支配集。 (5)若图G有完美匹配M,则从M中每边取一个端点构成的顶点集是一个支配集。 定理511设图G中无孤立顶点,则存在支配集D,使得D=(G)-D也是一个支配集 证明:无妨设G是连通图。于是G有生成树T。任取vo∈V(G D={v|v∈(G)且d(vo,v)=偶数} 则D=V(G)-D={|v∈v(G)且d(v,v)=奇数},且D和D都是支配集。证毕。 定理51,2设图G无孤立顶点,D1是一个极小支配集,则D1=(G)-D也是一个支配集。 证明(反证法):若不然,存在v∈D1,它与D中所有顶点都无边相连,但它又不是孤立顶 点,故必与D中顶点连边,因此D1-v0仍是支配集。这与D1是极小支配集矛盾。证毕 推论511设图G中无孤立顶点。对G的任一个极小支配集D1,必存在另一个极小支配集D2 使得D1∩D2=p 证明:由定理512,D1=V(G)-D1也是一个支配集,且D1∩D=φ。D中必含有一个极 小支配集D2。显然D1∩D2=φ。证毕
1 第五章 支配集、独立集、覆盖集和 Ramsey 数 本章讨论图中具有某种特性的顶点子集和边子集，以及它们之间的关系。本章所讨论的 图均为简单图。 §5.1 支配集、点独立集、点覆盖集 一、支配集(Domination set) 定义 5.1.1 设 D ⊆ V (G)，若对∀u ∈V (G) ，要么u ∈ D ，要么 u 与 D 中的某些顶点相邻， 则称 D 为图 G 的一个支配集。如果一个支配集的任何真子集都不是支配集，则称它为极小支 配集。图 G 的含顶点最少的支配集称为最小支配集。最小支配集的顶点个数称为 G 的支配数， 记为γ ( ) G 或γ 。 例如，在下图中， { } 0 0 D = v ， { , , } 1 1 4 7 D = v v v ， { , , , } 2 1 3 5 6 D = v v v v 都是 G 的支配集， 前两个是极小支配集， D0 是最小支配集。γ (G) = 1。 G 注：（1）最小支配集必是一个极小支配集，反之不然。 （2）任一支配集必含有一个极小支配集。 （3）极小支配集不唯一，最小支配集一般也不唯一。 （4）对二部图G = (X ,Y ) ，X 和 Y 都是支配集。 （5）若图 G 有完美匹配 M* ，则从 M* 中每边取一个端点构成的顶点集是一个支配集。 定理 5.1.1 设图 G 中无孤立顶点，则存在支配集 D，使得 D VG D = ( ) − 也是一个支配集。 证明：无妨设 G 是连通图。于是 G 有生成树 T。任取 ( ) v0 ∈V G 。令 D = {v | v ∈V(G) 且 ( , ) 0 d v v T ＝偶数}， 则 D VG D v v VG = −= ∈ ( ) {| ( ) 且 ( , ) 0 d v v T ＝奇数}，且 D 和 D 都是支配集。证毕。 定理 5.1.2 设图 G 无孤立顶点， D1是一个极小支配集，则 1 1 D VG D = ( ) − 也是一个支配集。 证明（反证法）：若不然，存在 0 D1 v ∈ ，它与 D1中所有顶点都无边相连，但它又不是孤立顶 点，故必与 D1中顶点连边，因此 1 0 D − v 仍是支配集。这与 D1是极小支配集矛盾。证毕。 推论 5.1.1 设图 G 中无孤立顶点。对 G 的任一个极小支配集 D1，必存在另一个极小支配集 D2 ， 使得 D1 ∩ D2 = φ 。 证明：由定理 5.1.2， 1 1 D VG D = − ( ) 也是一个支配集，且 D1 ∩ D = φ 。D1中必含有一个极 小支配集 D2 。显然 D1 ∩ D2 = φ 。证毕。 v7 v8 v1 v2 v6 v5 v3 v4 v0
定理513图G的支配集D是一个极小支配集当且仅当D中每个顶点ν满足下列条件之一: (1)存在∈V(G)-D使得N(u)∩D={v}:(2)N(v)∩D=φ。 证明:充分性:设D是G的一个支配集。对D中任一个顶点v,因γ满足上述条件之一,故 要么与ν相邻的某个顶点不能被D-{v}支配,要么v自己不能被D-{v}支配,可见,D-{v} 不再是支配集。这表明D是极小支配集。 必要性:设D是G的一个极小支配集,则对D中任一个顶点v,D-{}不再是支配集。因 此在D-{v}之外存在顶点u,它不与D-{v}中任何点相邻。如果u=v,则说明v不与D 中任何点相邻,即N(v)∩D=φ:如果u≠v,则因D是支配集,故u必与v相邻,但不与 D中其它点相邻,即N(a)∩D={v}。证毕 定理514设G是无孤立顶点的图,则G必有最小支配集D满足:对v∈D,丑∈G-D 使得N(u)∩D={v} 证明:用反证法。在G的全部最小支配集中,设D为使得导出子图G[D]含边数最多的一个。 假定定理结论不真,即 v∈D,使得对vu∈G-D都有N(u)∩D≠{v}。 由定理5.13,N(v)∩D=φ,即D中所有其它点都不与v相邻。而上式表明,G-D中每 个点要么不与v相邻,要么既与v相邻也与D中另外某些点相邻。因G无孤立点,故v在G-D 中必有某个邻点w,令D1=(D-{v)U{w},则D也是G的一个最小支配集,但其导出子 图G[D]含的边数比G[D中多。这与D的取法矛盾。证毕。 以下是关于支配数的几个估计式。 定理515如果图G无孤立顶点,则(G)≤ 证明:设D是G的一个极小支配集,则由定理512,V(G)-D也是G的支配集。因此, y(G)≤minDⅤ(G)-D}≤2 证毕 定理51.6( Arnautov197, Payan1975)设G是一个最小度为d图,则()shn(GAN 1+δ 证明:对G的任一非空顶点子集S∈V(G),用U表示未被S中顶点支配的所有顶点之集。 对v∈(G),用N'(v)表示顶点v及其所有邻点组成的集合,即N(v)=N(v)∪{v}。由 于U中每个顶点至少有k个邻点,故∑|N()|2Ul(6+1)。从而在(G)-S中至少有 个顶点x,它在求和过程中至少被重复计算|(6+1) 次。(否则,若V(G)-S中每个点被 重复计算都少于C|(+1) 次,则∑|N()<(U-|sD(6+1)<U(+1),与前 式矛盾),这意味着在(G)-S中存在某个顶点x,它支配U中至少1(1+1D各顶点
2 定理 5.1.3 图 G 的支配集 D 是一个极小支配集当且仅当 D 中每个顶点 v 满足下列条件之一： （1）存在u VG D ∈ − ( ) 使得 Nu D v ( ) {} ∩ = ；（2） Nv D ( ) ∩ = φ 。 证明：充分性：设 D 是 G 的一个支配集。对 D 中任一个顶点 v，因 v 满足上述条件之一，故 要么与 v 相邻的某个顶点不能被 D v −{ }支配，要么 v 自己不能被 D v −{ }支配，可见，D v −{ } 不再是支配集。这表明 D 是极小支配集。 必要性：设 D 是 G 的一个极小支配集，则对 D 中任一个顶点 v， D v −{ }不再是支配集。因 此在 D v −{ }之外存在顶点 u，它不与 D v −{ }中任何点相邻。如果u v = ，则说明 v 不与 D 中任何点相邻，即 Nv D ( ) ∩ = φ ；如果u v ≠ ，则因 D 是支配集，故 u 必与 v 相邻，但不与 D 中其它点相邻，即 Nu D v ( ) {} ∩ = 。证毕。 定理 5.1.4 设 G 是无孤立顶点的图，则 G 必有最小支配集 D 满足：对∀v D ∈ ，∃∈ − uGD 使得 Nu D v ( ) {} ∩ = 。 证明：用反证法。在 G 的全部最小支配集中，设 D 为使得导出子图 G[D]含边数最多的一个。 假定定理结论不真，即 ∃v D ∈ ，使得对∀uGD ∈ − 都有 Nu D v ( ) {} ∩ ≠ 。 由定理 5.1.3， Nv D ( ) ∩ = φ ，即 D 中所有其它点都不与 v 相邻。而上式表明，G D− 中每 个点要么不与 v 相邻，要么既与 v 相邻也与 D 中另外某些点相邻。因 G 无孤立点，故 v 在G D− 中必有某个邻点 w，令 1 D Dv w = − ( { }) { } ∪ ，则 D1也是 G 的一个最小支配集，但其导出子 图 G[D1]含的边数比 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 是一个最小度为δ 图，则 1 ln( 1) (G) 1 δ γ υ δ + + ≤ + 。 证明：对 G 的任一非空顶点子集S V(G) ⊆ ，用 U 表示未被 S 中顶点支配的所有顶点之集。 对∀ ∈v VG( ) ，用 N v( ) ∗ 表示顶点 v 及其所有邻点组成的集合，即 N v Nv v ( ) ( ) {} ∗ = ∪ 。由 于 U 中每个顶点至少有 k 个邻点，故 | ( ) | | | ( 1) v U Nv U δ ∗ ∈ ∑ ≥ + 。从而在VG S ( ) − 中至少有一 个顶点 x，它在求和过程中至少被重复计算 | | ( 1) U δ υ + 次。(否则，若VG S ( ) − 中每个点被 重复计算都少于 | | ( 1) U δ υ + 次，则 | | | ( ) | ( | S |) ( 1) | | ( 1) v U U Nv U υ δδ υ ∗ ∈ ∑ < − ⋅ +< + ，与前 式矛盾)。这意味着在VG S ( ) − 中存在某个顶点 x，它支配 U 中至少 | | ( 1) U δ υ + 各顶点
现在我们通过迭代来生成G的一个支配集,用S表示在迭代过程中形成的支配集的一部 分,初始时可取最大度顶点放入S。在迭代的每一步选择一个顶点放入S,所选择的顶点应能 够尽可能多地支配当前的S尚未支配的顶点。由前一部分的结论,如果当前的S尚未支配的 顶点有U=k个,则在(G)-S中存在某个顶点x,它支配U中至少k(6+1) 个顶点。因 此按照我们的选点规则,再选择一个点放入S后,剩下未被支配的顶点不超过M、+1个 n(δ+1 在+1步后,未被支配的顶点个数至多为 +1) (1 6+1 (上式推导中用到不等式1-P<e)。将当前S中的点和未被S支配的点放在一起,便组成 G的一个支配集,它含有+1)+D=1+1mo+1),个顶点。结论得证。 定理517对任何图G,有 2x4G|s(G)sD-△(G) 证明:设D是G的一个最小支配集,则v(G)-Ds∪N(v),因此(G)-D≤△(G)。 而|V(G)-D=b-|D|,|D=y(G),故U-y(G)≤y(G)△(G),于是y(G)≥ 1+△(G) 图的支配集是内容相当丰富的一个研究专题,它在许多学科领域有重要的应用,是目前研 究的一个热点方向[1~5]。进一步的了解可参看 Haynes- Hedetniemi- Slater的长达1200页的 专著6]。支配集理论在电力网络中的应用见文献[]。支配集在无线通信网络中的应用见文献 [8~l1]l [1B.G. Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics, 154(2006) 1541-1546 [2]TW. 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 [].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
3 现在我们通过迭代来生成 G 的一个支配集，用 S 表示在迭代过程中形成的支配集的一部 分，初始时可取最大度顶点放入 S。在迭代的每一步选择一个顶点放入 S，所选择的顶点应能 够尽可能多地支配当前的 S 尚未支配的顶点。由前一部分的结论，如果当前的 S 尚未支配的 顶点有| | U k = 个， 则在VG S ( ) − 中存在某个顶点 x，它支配 U 中至少 k( 1) δ υ + 个顶点。因 此按照我们的选点规则，再选择一个点放入 S 后，剩下未被支配的顶点不超过 1 k(1 ) δ υ + − 个。 在 ln( 1) 1 δ υ δ + + 步后，未被支配的顶点个数至多为 ln( 1) 1 1 ln( 1) (1 ) 1 e δ υ δ δ δ υ υ υ υ δ + ⋅ + + − + − <= + 。 （上式推导中用到不等式1 p p e− − < ）。将当前 S 中的点和未被 S 支配的点放在一起，便组成 G 的一个支配集，它含有 ln( 1) 1 δ υ δ + + + 1 υ δ + = 1 ln( 1) 1 δ υ δ + + + 个顶点。结论得证。 定理 5.1.7 对任何图 G，有 (G) (G) 1 (G) υ γ υ ⎡ ⎤ ≤ ≤ −Δ ⎢ ⎥ ⎢ ⎥ + Δ 。 证明：设 D 是 G 的一个最小支配集，则 V(G) D ( ) v D N v ∈ − ⊆ ∪ ，因此|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
[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 an.2001 [9]. Wu, and H.L. Li, On calculating connected dominating set for efficient routing in ad wireless networks, Proceedings of the 3 ACM International Workshop on Discrete Algorithms 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, ICC97, Montreal, Canada, June, 1997 、点独立集( vertex independent se) 定义5.1.2设Ⅰ∈V(G),若l中任二顶点均不相邻,则称l为图G的一个点独立集(简称 独立集);若对vu∈V(G)\,U{都不再是G的独立集,则称独立集为图G的一个 极大点独立集。G的含点数最多的点独立集称为最大点独立集,它含点的个数称为G的独立 数,记为a(G)或a 例如,在下图中,D={V},1=智1,v4,"n},l2={1,v3,V5,"}都是G的独立集, 且都是极大独立集,其中l2是最大独立集,a(G)=4。 些文献中将独立集称为稳定集( stable set),相应地将独立数称为稳定数。 独立集与支配集的关系 定理518图G的极大独立集必是G的极小支配集。 证明:设I是G的一个极大独立集。对wu∈I(G)\I,u必与/中某顶点相邻(否则与极大 性矛盾)。可见/是一个支配集。又对回v∈I,v必与I\{v}中的顶点不相邻,可见/是极小 支配集。证毕。 注:该定理的逆不真。例如在下图中,{v1,v2}是极小支配集,但却不是极大独立集。实际上 它根本不是独立集
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 3rd 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 设 I ⊆ V（G），若 I 中任二顶点均不相邻，则称 I 为图 G 的一个点独立集（简称 独立集）；若对∀u ∈V(G) \ I ， I ∪{u}都不再是 G 的独立集，则称独立集 I 为图 G 的一个 极大点独立集。G 的含点数最多的点独立集称为最大点独立集，它含点的个数称为 G 的独立 数，记为α(G) 或α 。 例如，在下图中， { } 0 0 I = v ， { , , } 1 1 4 7 I = v v v ， { , , , } 2 1 3 5 7 I = v v v v 都是 G 的独立集， 且都是极大独立集，其中 2 I 是最大独立集，α(G) = 4 。 一些文献中将独立集称为稳定集(stable set)，相应地将独立数称为稳定数。 z 独立集与支配集的关系 定理 5.1.8 图 G 的极大独立集必是 G 的极小支配集。 证明：设 I 是 G 的一个极大独立集。对∀u ∈V(G) \ I ，u 必与 I 中某顶点相邻（否则与极大 性矛盾）。可见 I 是一个支配集。又对∀v ∈ I ，v 必与 I \ {v}中的顶点不相邻，可见 I 是极小 支配集。证毕。 注：该定理的逆不真。例如在下图中，{ , } 1 2 v v 是极小支配集，但却不是极大独立集。实际上 它根本不是独立集。 v1 v2 v4 v3 v7 v8 v1 v2 v6 v5 v3 v4 v0 G
但我们有如下结论 定理519若I是独立集,则它是极大独立集当且仅当它是支配集 证明:必要性由定理518显然。 充分性:设l是独立集又是支配集,则对vv∈(G)\1,因/是支配集,v必与I中某顶点相 邻。故U{v}不是独立集。可见/是极大独立集。 注:(1)由定理518和定理5.1.9,虽然G的一个独立集未必是G的支配集,但一个极大独 立集必是G的极小支配集;反过来,G的一个支配集要么不是独立集,要么是极大独立集; (2)一个支配集若不是极小支配集,则必不是G的独立集。 定理5110对任何图G,a(G)≥y(G)。 证明:设I是G的一个最大独立集,则它必是一个极大独立集,由定理5.1.8,I是G的一个 (极小)支配集,因此y(G)SIF=a(G)。证毕。 注:定理51.10中的等号未必总成立,也就是说,虽然G的一个最大独立集必是G的极小支 配集,但它未必是最小支配集。例如完全二部图K13,最大独立集含三个点,而最小支配集含 一个点。 点独立集与连通度 定理5111( Bondy,1978)设vG)≥2。若图G中任二不相邻顶点x与y均有 d(x)+d(y)≥v(G),则a(G)≤k(G)。 证明:首先易知G是连通的(若G不连通,设x、y属于不同的连通分支G1,G,,则 d(x)SG1|-1,d(y)≤G2|-1,从而d(x)+d(y)G1|+|G2|-2<v)。 若G为完全图K,则a(K,)=1≤v-1=K(K,),结论成立。下设G不是完全图。用 反证法证明结论。 假定a(G)≥k(G)+1。设和S分别是G中的最大点独立集和最小点割集。则 Fa(G)≥2,|SF=K(G)=k。设G\S的连通分支为G1,G2,…G1,(≥2)。由于对 vx,y∈I,|N(x)∪NG(y)kv-a。 (含a个顶点) GI含v-a个顶点) kh ING(x)nNG()=ING(x)I+ING(y)I-ING(x)UNG() =d(x)+d(y)-|Nc(x)UNa(y)|≥v-(-a)=a≥k+1 这表明Ⅰ\S含在G\S的同一个连通分支中(因在I\S中任二点x与y有公共的邻点,故有
5 但我们有如下结论。 定理 5.1.9 若 I 是独立集，则它是极大独立集当且仅当它是支配集。 证明：必要性由定理 5.1.8 显然。 充分性：设 I 是独立集又是支配集，则对∀v ∈V(G) \ I ，因 I 是支配集，v 必与 I 中某顶点相 邻。故 I ∪{v}不是独立集。可见 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 的极小支 配集，但它未必是最小支配集。例如完全二部图 K1,3，最大独立集含三个点，而最小支配集含 一个点。 z 点独立集与连通度 定 理 5.1.11 (Bondy, 1978) 设 ν (G) ≥ 2 。若图 G 中任二不相邻顶点 x 与 y 均 有 d (x) d ( y) (G) G + G ≥ν ，则α(G) ≤ κ (G) 。 证明：首先易知 G 是连通的（若 G 不连通，设 x、y 属于不同的连通分支 1 2 G , G ，则 dG (x) ≤| G1 | −1， dG ( y) ≤| G2 | −1，从而dG (x) + dG ( y) ≤| G1 | + | G2 | −2 <ν ）。 若 G 为完全图 Kν ，则 ( ) 1 1 ( ) α Kν = ≤ν − = κ Kν ，结论成立。下设 G 不是完全图。用 反证法证明结论。 假定α(G) ≥ κ (G) +1 。设 I 和 S 分别是 G 中的最大点独立集和最小点割集。则 | I |= α(G) ≥ 2 ，| S |= κ (G) = k 。设G \ S 的连通分支为G G "Gl , , 1 2 ， (l ≥ 2) 。由于对 ∀x, y ∈ I ，| NG (x) ∪ NG ( y) |≤ν −α 。 故 | N (x) N ( y) | G ∩ G ＝| N (x) | | N ( y) | G + G | N (x) N ( y) | − G ∪ G ＝ d (x) d ( y) G + G | N (x) N ( y) | − G ∪ G ≥ν − (ν −α) = α ≥ k +1。 这表明 I \ S 含在G \ S 的同一个连通分支中（因在 I \ S 中任二点 x 与 y 有公共的邻点，故有 I (含α 个顶点) y x G-I (含ν −α 个顶点)
路相通)。无妨设I\S∈VG1),即lcV(G1)∪S。因a≥k+1,故丑∈∩v(G1)。 取v∈H(G2),则 NG()∪NG(v)v-2-(nv(G1)|-1)=v-|n(G1)|-1=v-(a-|mnSD- 又因NG()∩NG(v)sS\,故N(a)nN(v)≤k-|∩S|。由此二式可得 dG(u)+d(v)=NG(uUNG(v)I+ING(unNG(v) I∩S|-1)+(k-|mnSD -a+k-1≤v-(k+1)+k-1=v 这与定理条件矛盾。因此a(G)≤k(G)。证毕。 推论512设G是v(v≥2)阶简单图。若(G)≥,则a(G)≤k(G)。 独立数与 Hamilton性 定理5112( Chvatal& Erdos,1972)设G是v(v≥3)阶简单图。若k(G)≥a(G),则G是 Hamilton图 证明:若a(G)=1,则G是完全图,从而是 Hamilton图。下设a(G)≥2。 由于(G)≥a(G)≥2,故G含有圈。设C是G的最长圈。下面用反证法证明C是 Hamilton 若C不含G的所有顶点,则V(G)\F(C)非空。令H是G-V(C)的任一连通分支,并 令{x,x2,…,x,}是C中与H相邻的顶点集。因K(G)≥2,故s≥2(香则,C上只有一个 顶点ⅴ与H相邻,G-{v}不连通)。由C的最大性及H的连通性知x12x2…,x,在C上互不 相邻(否则可得更大的圈)。 因此|r(C)卜s,且{x1,x2,…,x,}是G的点割集(因去掉{x1,x2…;x,}后H与C上其 余点不连通)。所以K(G)≤S(由k(G)的定义)
6 路相通）。无妨设 \ ( ) V G1 I S ⊆ ，即 I V (G ) ∪ S ⊆ 1 。因α ≥ k + 1，故 ( ) V G1 ∃u ∈ I ∩ 。 取 ( ) V G2 v ∈ ，则 | NG (u) ∪ NG (v) |≤ν − 2 − (| I ∩V(G1 ) | −1) =ν − | I ∩V(G1 ) | −1 =ν − (α− | I ∩ S |) −1. 又因 N u N v S I G G ( ) ∩ ( ) ⊆ \ ，故| N (u) N (v) | G ∩ G ≤ k− | I ∩ S |。由此二式可得 ( ) ( ) | ( ) ( )| | ( ) ( )| GG G G G G du dv Nu Nv Nu Nv + = + ∪ ∩ ≤ −+ −+ − ( | | 1) ( | |) ν α I ∩ ∩ S kIS = − + −≤ − + + −= − ν αν ν k kk 1 ( 1) 1 2 这与定理条件矛盾。因此α(G) ≤ κ (G) 。证毕。 推论 5.1.2 设 G 是ν (ν ≥ 2) 阶简单图。若 2 ( ) ν δ G ≥ ，则α(G) ≤ κ (G) 。 z 独立数与 Hamilton 性： 定理 5.1.12（Chvátal & Erdös, 1972）设 G 是ν (ν ≥ 3) 阶简单图。若κ (G) ≥ α(G) ，则 G 是 Hamilton 图。 证明：若α(G) = 1，则 G 是完全图，从而是 Hamilton 图。下设α(G) ≥ 2 。 由于κ (G) ≥ α(G) ≥ 2 ，故G含有圈。设C是G的最长圈。下面用反证法证明C是Hamilton 圈。 若 C 不含 G 的所有顶点，则V(G) \V(C) 非空。令 H 是G −V(C) 的任一连通分支，并 令{ , , , } 1 2 s x x " x 是 C 中与 H 相邻的顶点集。因κ (G) ≥ 2 ，故 s ≥ 2 （否则，C 上只有一个 顶点 v 与 H 相邻，G −{v}不连通）。由 C 的最大性及 H 的连通性知 s x , x , , x 1 2 " 在 C 上互不 相邻（否则可得更大的圈）。 因此|V(C) |> s ，且{ , , , } 1 2 s x x " x 是 G 的点割集（因去掉{ , , , } 1 2 s x x " x 后 H 与 C 上其 余点不连通）。所以κ (G) ≤ s （由κ (G) 的定义）。 G1 G2 I S u v y1 x1 C H y2 x2 ys xs … …
给圈C定一个方向,得有向圈C。令Y={y|xy1∈E(C,=1,2,…,S}。则由x在C 上的不相邻性知,|YFs≥2。下面证明,Y是G的一个独立集。 事实上,若Y不是G的独立集,则有边yy∈E(G)。设通过H中顶点连接x和x的 路为P,则C-xy-xy+yy+P是G中一条比C更长的圈。这与C是最长圈矛盾。 于是Y是独立集。 由于y与x1相邻,故y不与H中任何点相邻(否则会得到比C更长的圈),=12…,s 任取y∈(H),则S={y,y1,…,y,}是G的独立集,且a(G)2SFs+1≥(G)+1。这 与定理的条件矛盾。因此C必是 Hamilton圈。证毕。 有关独立集和独立数的研究较为活跃。有兴趣的读者可查阅近期文献(如[2-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, Zdenek Ryjacek 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 L ubomir Soltes, A Generalization of maximal independent sets, Discrete Applied Mathematics, 117(2002), 223-235 、点覆盖 vertex covering set 定义513设FcV(G),若G的每条边至少有一个端点属于F,则称F是G的一个点覆盖 若对任给的v∈F,F-{v}不再是G的点覆盖,则称点覆盖F是一个极小点覆盖。图G的 含点数最少的点覆盖称为最小点覆盖,其点数称为G的点覆盖数,记为B(G)或B。 例如,在下图中,{,V1,v3,V5,v7}和{v1,V2,V3,V4,Vs,v6,v7,V}都是G的点覆盖,且都 是极小点覆盖。前一个点覆盖是最小点覆盖,B(G)=4 注:(1)最小点覆盖必为极小点覆盖 (2)点覆盖集与支配集是容易混淆的两个概念,它们的本质区别在于,点覆盖集是用点覆 盖边,而支配集使用点支配点。在连通图中,点覆盖集必为支配集。但支配集未必是覆盖集。 比如上例中{v}及{1v4,V7}都是G的支配集,但不是覆盖集。 (3)极小点覆盖集未必是极小支配集。 例如上例中{v0,v1,v3,v5,V7}是G的极小点覆盖集,但它不是G的极小支配集
7 给圈 C 定一个方向，得有向圈C G 。令Y {y | x y E(C),i 1,2, ,s} i i i " G = ∈ = 。则由 i x 在 C 上的不相邻性知，|Y |= s ≥ 2 。下面证明，Y 是 G 的一个独立集。 事实上，若 Y 不是 G 的独立集，则有边 y y E(G) i j ∈ 。设通过 H 中顶点连接 i x 和 j x 的 路为 Pij ，则 i i j j i j Pij C − x y − x y + y y + 是 G 中一条比 C 更长的圈。这与 C 是最长圈矛盾。 于是 Y 是独立集。 由于 i y 与 i x 相邻，故 i y 不与 H 中任何点相邻（否则会得到比 C 更长的圈），i=1,2,…,s。 任取 y ∈V(H)，则 { , , , } 1 s S = y y " y 是 G 的独立集，且α(G) ≥| S |= s +1 ≥ κ (G) +1。这 与定理的条件矛盾。因此 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 设 F ⊂ V(G) ，若 G 的每条边至少有一个端点属于 F，则称 F 是 G 的一个点覆盖。 若对任给的v ∈ F ， F −{v}不再是 G 的点覆盖，则称点覆盖 F 是一个极小点覆盖。图 G 的 含点数最少的点覆盖称为最小点覆盖，其点数称为 G 的点覆盖数，记为 β (G) 或 β 。 例如，在下图中，{ , , , , } 0 1 3 5 7 v v v v v 和{ , , , , , , , } 1 2 3 4 5 6 7 8 v v v v v v v v 都是 G 的点覆盖，且都 是极小点覆盖。前一个点覆盖是最小点覆盖， β (G) ＝4。 G 注：（1）最小点覆盖必为极小点覆盖； （2）点覆盖集与支配集是容易混淆的两个概念，它们的本质区别在于，点覆盖集是用点覆 盖边，而支配集使用点支配点。在连通图中，点覆盖集必为支配集。但支配集未必是覆盖集。 比如上例中{ }0 v 及{ , , } 1 4 7 v v v 都是 G 的支配集，但不是覆盖集。 （3）极小点覆盖集未必是极小支配集。 例如上例中{ , , , , } 0 1 3 5 7 v v v v v 是 G 的极小点覆盖集，但它不是 G 的极小支配集。 v7 v8 v1 v2 v6 v5 v3 v4 v0
点盖与点独立集的关系: 定理5113顶点子集F是图G的点覆盖集当且仅当V(G)\F是G的点独立集。 证明:F是图G的点覆盖集分G的每条边至少有一端在F中没有两端都在V(G)\F中的 边V(G)\F是点独立集。证毕 推论513F是图G的极小点覆盖集当且仅当(G)\F是G的极大点独立集 推论514a(G)+B(G)=V S5.2边独立集与边覆盖集 边独立集 定义52.1.图G的一个匹配M称为G的一个边独立集。G的最大匹配所含的边数称为G的 边独立数或匹配数,记为a(G)。 边独立集与点覆盖有密切关系。由于任意一个顶点不能覆盖边独立集中的两条边,因此 图有大的边独立集,就有大的点覆盖集。另一方面,独立集中不同的边不能用同一个顶点覆 盖,因此图G中任何点覆盖集的含的点数不会小于任何边独立集含的边数。边独立数与点覆 盖的下列关系是显然的。 a'K 2n-1=B(K2n) ·a(C2n)=n=B(C2n) ·a'(K2n)=n<2n=B(K2n) (C2n)=n<n+1=B(C2n) a (Km)=min m, n)=B(Kmm) 一般地,有 定理521对任何无环边的图G,a(G)≤B(G) 证明:设S是G中一个最小点覆盖,M是G中最大匹配。M中任一条边e的两端点至少有一 个属于S,因而a(G)≤B(G)。证毕 定理5K6ng, egervary,1931)1m对于二部图G,有a'(G)=B(G),即G中最大匹配 的边数等于最小覆盖的点数。 116] D. Konig, Graphen und Matrizen, Math. Lapok, 38(1931), 116-119. [ E Egervary, On combinatorial properties of matrices, Math. Lapok, 38(1931), 16-28 证明:设M是G=(X,Y)的最大匹配。设X图Y|。 若M饱和X,则a'=M'|。另一方面,X显然是一个最小点覆盖(因M中每条边需要 个点来覆盖)。故B(G)= XMEa'。 若M不饱和X,设 U={x∈X|x未被M所饱和},A={v∈V(G)v到U有M交错路}UU S=A∩X,T=A∩Y
8 z 点覆盖与点独立集的关系： 定理 5.1.13 顶点子集 F 是图 G 的点覆盖集当且仅当V(G) \ F 是 G 的点独立集。 证明：F 是图 G 的点覆盖集⇔G 的每条边至少有一端在 F 中⇔没有两端都在V(G) \ F 中的 边⇔ V(G) \ F 是点独立集。证毕。 推论 5.1.3 F 是图 G 的极小点覆盖集当且仅当V(G) \ F 是 G 的极大点独立集。 推论 5.1.4 α(G) + β (G) =ν . §5.2 边独立集与边覆盖集 一、边独立集 定义 5.2.1. 图 G 的一个匹配 M 称为 G 的一个边独立集。G 的最大匹配所含的边数称为 G 的 边独立数或匹配数，记为α′(G) 。 边独立集与点覆盖有密切关系。由于任意一个顶点不能覆盖边独立集中的两条边，因此 图有大的边独立集，就有大的点覆盖集。另一方面，独立集中不同的边不能用同一个顶点覆 盖，因此图 G 中任何点覆盖集的含的点数不会小于任何边独立集含的边数。边独立数与点覆 盖的下列关系是显然的。 z ( ) 2 1 ( ) α K2n = n < n − = β K2n ′ ； z ( ) ( ) α C2n = n = β C2n ′ ； z ( ) 2 ( ) 2 +1 = < = 2 +1 ′ α K n n n β K n ； z ( ) 1 ( ) 2 +1 = < + = 2 +1 ′ α C n n n β C n ； z ( ) min{ , } ( ) α Km,n = m n = β Km,n ′ 。 一般地，有 定理 5.2.1 对任何无环边的图 G，α′(G) ≤ β (G) 。 证明：设 S 是 G 中一个最小点覆盖，M 是 G 中最大匹配。M 中任一条边 e 的两端点至少有一 个属于 S，因而α′(G) ≤ β (G) 。证毕。 定理 5.2.2 (König，Egerváry, 1931)[16],[17] 对于二部图 G，有α′(G) = β (G)，即 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 )的最大匹配。设| X |≤|Y |。 若 M* 饱和 X，则 | | * α′ = M 。另一方面，X 显然是一个最小点覆盖（因 M* 中每条边需要 一个点来覆盖）。故 β ( ) =| |=| |= α′ * G X M 。 若 M* 不饱和 X，设 U = {x ∈ X | x 未被 M* 所饱和}， A = {v ∈V (G) | v 到 U 有 M* 交错路}∪U , S = A∩ X ，T = A∩Y
(S)=7 令K=(X-S)UT,则G的每条边至少有一端在K中(否则必存在一条边,其一端在S中 另一端在￥\T中,这与N(S)=T矛盾)。因此K是G的一个点覆盖,且 K 结合定理52.1,便有| KEMA(G)≤B(G)。而K是G的一个点覆盖,因此又有 KB(G)。从而B(G)=KHM=a(G)。证毕。 附:(*)式的证明 首先TcN(S):对vy∈T,y到U有M交错路P,且y必是M饱和的(否则P是 可扩路)。设yx∈M,则x到U有M交错路P+x。这表明x∈S,故y∈N(S) 其次N(S)∈T:对vy∈N(S),设y在S中的邻点是x。因x到U有交错路P,故若 y∈P,则y到U有交错路;若y∈P’,则P+xy是y到U的M'交错路。总之y∈A故y∈T 证毕。 (*)的证明:首先X-S是M饱和的(因X中的非饱和点全在U中),T也是M饱和的(否 则有M可扩路)。故K中每一点都对应有一条M的边;其次,X-S与T间不会有M的边 (否则X-S中的点到U有M交错路)。因此每条M'的边仅有K中一个点与之相关联。可 见M的边与K的点一一对应,因而M”FK|。证毕。 关于边独立数有如下估计式。 定理523设图G无孤立点,则 ≤a(G)≤ 1+△(G) 证明:因为每条匹配边匹配图G的两个顶点,故上界是显然的。 为证明下界,对图的边数E作数学归纳法 E=1时结论显然成立。 假设对任何不超过k条边的图G,下界都成立。 设G是具有k+1条边且无孤立点的图。若G中每条边都有至少一个端点是1度顶点,则 G的每个连通分支都是星(星是一个完全二部图,其中一个分部仅含一个点,如K1)。一颗星 K的最大匹配只有一条边,且△(K1)=S,D(K)=+1,因此a(K,)=lsU(K,) 1+△(K,) 设G由r颗星T1,T2,…T组成(r≥1),则
9 则 N(S) = T 。 （*） 令 K = (X − S) ∪T ，则 G 的每条边至少有一端在 K 中（否则必存在一条边，其一端在 S 中， 另一端在Y \ T 中，这与 N(S) = T 矛盾）。因此 K 是 G 的一个点覆盖，且 | | | | * M = K 。 （**） 结合定理 5.2.1，便有 | | | | ( ) ( ) * K = M = α′ G ≤ β G 。而 K 是 G 的一个点覆盖，因此又有 | K |≥ β (G)。从而 ( ) | | | | ( ) * β G = K = M = α′ G 。证毕。 附：（*）式的证明： 首先T ⊆ N(S) ：对∀y ∈T ，y 到 U 有 M* 交错路 P，且 y 必是 M* 饱和的（否则 P 是 M* 可扩路）。设 * yx ∈ M ，则 x 到 U 有 M* 交错路 P + yx。这表明 x ∈ S ，故 y ∈ N(S) ； 其次 N(S) ⊆ T ：对∀y ∈ N(S) ，设 y 在 S 中的邻点是 x。因 x 到 U 有交错路 P′ ，故若 y ∈ P′，则y到U有交错路；若 y ∉ P′，则 P′ + xy 是y到U的M* 交错路。总之 y ∈ A故 y ∈T 。 证毕。 （**）的证明：首先 X − S 是 M* 饱和的（因 X 中的非饱和点全在 U 中），T 也是 M* 饱和的（否 则有 M* 可扩路）。故 K 中每一点都对应有一条 M* 的边；其次， X − S 与 T 间不会有 M* 的边 （否则 X − S 中的点到 U 有 M* 交错路）。因此每条 M* 的边仅有 K 中一个点与之相关联。可 见 M* 的边与 K 的点一一对应，因而| | | | * M = K 。证毕。 关于边独立数有如下估计式。 定理 5.2.3 设图 G 无孤立点，则 (G) 1 (G) 2 υ υ α ⎡ ⎤ ⎢ ⎥ ≤ ≤ ′ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ + Δ ⎣ ⎦ 。 证明：因为每条匹配边匹配图 G 的两个顶点，故上界是显然的。 为证明下界，对图的边数ε 作数学归纳法。 ε = 1时结论显然成立。 假设对任何不超过 k 条边的图 G，下界都成立。 设 G 是具有 k+1 条边且无孤立点的图。若 G 中每条边都有至少一个端点是 1 度顶点，则 G 的每个连通分支都是星 (星是一个完全二部图，其中一个分部仅含一个点, 如 K1, s)。一颗星 K1,s 的最大匹配只有一条边，且 1, 1, (K ) , (K ) 1 s s Δ = =+ s s υ , 因此 1, 1, 1, (K ) (K ) 1 1 (K ) s s s υ α′ = = + Δ 。 设 G 由 r 颗星 1 2 , , TT T " r 组成（ r ≥ 1），则 U T=N(S) S X \ S
a(G)=∑a(7)=∑ UT) ∑v(T) 1+△( 1+△(G)1+△(G) 下设G中存在边e,其两端点都不是1度点。设G-e有m个连通分支G1,G2,…Gn (m≥1),则每个连通分支都不是孤立点,且边数都不超过k。因此根据归纳假设, a(G)≥YG (i=1,2 1+△G1) ∑v(G) 从而a'(G)≥a(G-e)=∑a(G,)≥ U(G) 1+△(G,)1+△(G-e)1+△(G) 归纳完成。证毕。 、边覆盖 定义522设LcE(G)。若G的每个顶点都与L中至少一条边关联,则称L是G的边覆盖 若边覆盖L的任何真子集都不是G的边覆盖,则称L是G的极小边盖。G的含边数最少的 边覆盖称为G的最小边覆盖,其所含边的数目称为G的边覆盖数,记为B(G)或B 例如,在下图中,L1={e2,e3,e6}和L2={e2,e3,e}都是边覆盖,也是极小边覆盖,还 是最小边覆盖;L3={e1,e4,e5,en}是边覆盖,但不是极小边覆盖 点独立数与边覆盖数的关系 定理524对任何图G,都有a(G)≤B(G)。 证明:设/是G的最大点独立集。因/中点彼此不相邻,故至少要用条边才能覆盖住/中 所有顶点,故a(G)=I≤B(G)。证毕 边覆盖与边独立数(匹配数)的关系 定理525(Gala,1959)若δ(G)>0,则a(G)+B'(G)=v。 证明:设M是G的最大匹配。若M是G的完美匹配,则显然B'sM==a',从而 Q+B≤ v;若M不是G的完美匹配,U是M非饱和点之集。则G[U]是无边图 (否则在G[U中取一边可使M扩大)。由于(G)>0,所以U的每个点在G中都至少与 条边关联。对应于每个点取这样一条边,这些边的集合记为E′。显然M∪E是G的边覆盖
10 1 1 1 ( ) ( ) (G) (G) ( ) 1 ( ) 1+ (G) 1 (G) r r r i i i i i i i T T T T υ υ υ α α = = = ′ ′ = = ≥= +Δ Δ +Δ ∑ ∑ ∑ 。 下设 G 中存在边 e，其两端点都不是 1 度点。设G − e 有 m 个连通分支G ,G , G 1 2 " m （ m ≥ 1），则每个连通分支都不是孤立点，且边数都不超过 k。因此根据归纳假设， (G ) (G ) , ( 1,2, ) 1 (G ) i i i i m υ α′ ≥ = + Δ " 。 从而 1 1 1 (G ) (G ) (G) (G) (G ) (G ) 1 (G ) 1+ ( ) 1 (G) m m m i i i i i i i e G e υ υ υ αα α = = = ′′ ′ ≥ −= ≥ ≥ ≥ +Δ Δ − +Δ ∑ ∑ ∑ 。 归纳完成。证毕。 二、边覆盖 定义 5.2.2 设 L ⊆ E(G) 。若 G 的每个顶点都与 L 中至少一条边关联，则称 L 是 G 的边覆盖。 若边覆盖 L 的任何真子集都不是 G 的边覆盖，则称 L 是 G 的极小边覆盖。G 的含边数最少的 边覆盖称为 G 的最小边覆盖，其所含边的数目称为 G 的边覆盖数，记为 β ′(G) 或 β ′。 例如，在下图中， { , , } 1 2 3 6 L = e e e 和 { , , } 2 2 3 7 L = e e e 都是边覆盖，也是极小边覆盖，还 是最小边覆盖； { , , , } 3 1 4 5 7 L = e e e e 是边覆盖，但不是极小边覆盖。 z 点独立数与边覆盖数的关系 定理 5.2.4 对任何图 G，都有α(G) ≤ β ′(G)。 证明：设 I 是 G 的最大点独立集。因 I 中点彼此不相邻，故至少要用|I|条边才能覆盖住 I 中的 所有顶点，故α(G) =| I |≤ β ′(G) 。证毕。 z 边覆盖与边独立数（匹配数）的关系 定理 5.2.5(Gallai,1959) 若δ (G) > 0，则α′(G) + β ′(G) =ν 。 证明：设 M 是 G 的最大匹配。若 M 是 G 的完美匹配，则显然 α ν β ′ ≤ = = ′ 2 | M | ，从而 ν ν ν α′ + β ′ ≤ + = 2 2 ；若 M 不是 G 的完美匹配，U 是 M 非饱和点之集。则G[U]是无边图 （否则在 G[U]中取一边可使 M 扩大）。由于δ (G) > 0 ，所以 U 的每个点在 G 中都至少与一 条边关联。对应于每个点取这样一条边，这些边的集合记为 E′。显然 M ∪ E′是 G 的边覆盖， e1 e3 e5 e6 e7 e2 e4