路相通)。无妨设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