图的弱毁裂度与网络抗毁性

刘 勇, 杨淑姝, 魏宗田, 岳 超

(西安建筑科技大学理学院，西安 710055)

1 引言

网络的广泛使用和中断的频繁发生，使得抗毁性与可靠性研究愈发重要.连通度与边连通度可以刻画图的结构特征，但这两个参数考虑的是在最坏情形下破坏网络的难易程度[1-3].后来一些新的参数不断被引入[4-7]，用以度量网络抗毁性.这些参数既考虑了破坏网络的难度，又反映了网络被破坏的程度.但是它们的侧重点各不相同，因而至今没有度量网络抗毁性的统一标准.

弱毁裂度是一个视角较为全面的抗毁性参数.设G是一个简单连通图，其弱毁裂度定义为[8]

其中X表示G的点割集，ω(G-X)和me(G-X)分别表示G-X的连通分支数和最大分支中的边数.若存在X*⊂V(G)，使得rw(G) =ω(G-X*)-|X*|-me(G-X*)，则称X*为G的一个rw-集.

本文通过研究该参数的性质和取值范围，以及Nordhaus-Gaddum(N-G)型问题，揭示图的弱毁裂度与网络结构之间的关系.

2 弱毁裂度与图的结构

图(网络)的抗毁性参数有很多，这些参数与图的基本参数之间的关系，在很大程度上反映了图的结构特征.下面给出图的弱毁裂度与其它基本参数之间的关系，也可以看作是弱毁裂度的界，是估计一般图的弱毁裂度大小的重要工具.

定理1 设G是周长为c(c ＞0)的n(n ≥4)阶连通图，则rw(G)≤n-c.

证明 设C为G的一个最长圈，即|V(C)| =c.若X为G的一个点割集，则在GX中，至多有n-c个分支包含V(G) V(C)中的点；至多有|V(C)∩X|个分支包含V(C)中的点.从而ω(G-X)≤|V(C)∩X|+n-c.

另一方面，由于|X|≥|V(C)∩X|, me(G-X)≥0，则由定义可知

定理得证.

注1 设G是将圈C2k的一个点与星图S1,n-2k的中心点重合所得之图，其中k ≥2, n ≥2k，则rw(G)=n-c.这表明，定理1 中的上界可以达到.

引理1[9]对于n阶图G，有κ(G)≥max{1,2δ(G)-n+2}.

定理2 设G是n(n ≥4)阶连通图，则rw(G)≤n-2δ(G).

证明 设X是G的任一点割集.由于ω(G-X)≤n-|X|, me(G-X)≥0，所以ω(G-X)-|X|-me(G-X)≤n-2|X|.于是，当|X|≥δ时，

当|X|≤δ-1 时，G-X的任一分支Gi(|V(Gi)|=ni, i=1,2,··· ,ω)所含点数不少于2.否则，若存在一个孤立点u，那么就有d(u)≤|X|＜δ，导致矛盾.

由于ni-1+|X|≥δ(i=1,2,··· ,ω)，于是，有

下面讨论函数f(x)的单调性.首先，有

因为x=|S|≤δ-1，所以f(x+1)-f(x)≥0 等价于x2-(2δ+1)x+(δ+1)2-n ≤0.

由引理1 和x=|X|≤δ-1，有

因此，有

因为

所以rw(G)≤n-2δ.

综上所述，定理得证.

注2 上述结论中的界是最好可能的，可在n(n ≥4，偶数)阶-正则图达到.

推论1 对于n阶图G，有rw(G)≤n-2κ(G), rw(G)≤n-2λ(G).

定理3 设G是n阶图，则有rw(G)≤r(G)+1，其中r(G)为G的毁裂度[5].

证明 设X*是G的一个rw-集.因为对于G的任一点割集X，有

所以m(G-X*)≤me(G-X*)+1.由r(G)的定义，有

即rw(G)≤r(G)+1.

推论2 若连通图G同构于树或圈，则rw(G)=r(G)+1.

证明 设X是图G的任一点割集.如果去掉X中的点，则G-X的任一分支要么是树，要么是孤立点，且m(G-X)-1=me(G-X).故有

由定义，即得rw(G)=r(G)+1.

定理4 假设图G是非完全连通的，则rw(G)≤α(G)-Iw(G)，其中Iw(G)为G的弱完整度.

证明 设X是G的一个rw-集，则

从而

由定义，即得rw(G)≤α(G)-Iw(G).

坚韧度作为一个重要的网络抗毁性参数已被广泛地应用.对于非完全连通图G，其坚韧度定义为[3]

其中ω(G-X)表示G-X的连通分支数.

下面的定理5 揭示了坚韧度和弱毁裂度之间的关系.

从而

因为对任意的X ⊆V(G), κ(G)≤|X|≤β(G), me(G-X)≥0，故有

定理6 不存在rw(G)=t(G)的n阶连通图G.

证明 假设存在一个n阶图G，使得rw(G) =t(G).由于t(G)≥0，且rw(G)是整数，就有t(G)≥1.设X是G的一个点割集，则|X|≥ω(G-X)，从而

因为对任意的X ⊆V(G)都有-me(G-X)≤0，所以rw(G)≤0，即t(G)≤0，这显然是不可能的.定理得证.

图的相对断裂度(亦称为离散数)是一个常用的网络抗毁性参数.对于图G，其定义为s(G)=max{ω(G-X)-|X|:ω(G-X)≥2}，其中X是G的点割集，ω(G-X)表示G-X的连通分支数[10].

弱毁裂度与离散数有如下的关系：

定理7 设G是连通图，则rw(G)≤s(G).

证明 设X是G的一个点割集，则有ω(G-X)-|X|≤s(G).所以有

于是

因为，对任意的X ⊆V(G)，都有me(G-X)≥0，所以rw(G)≤s(G).

3 弱毁裂度的N-G 型问题

当一个图的边数明显大于同阶完全图的一半时，其补图的研究相对容易一些.图与其补图结构之间的关系可以通过某些参数和与积的形式刻画.这个问题是Nordhaus 和Gaddum 提出的，称为N-G 型问题.本节主要考虑图的弱毁裂度和形式的N-G 型问题.

注4 定理中的界是紧的，且达到该界的图不唯一.如C5取得下界-2；K1,n-1取得上界n-2.

4 结语

本文给出若干弱毁裂度的界，以及该参数与图的其它参数之间的关系.在此基础上，进一步研究了弱毁裂度的N-G 型问题.通过建立参数模型，利用微分或差分方法计算和比较参数值的大小关系，得到弱毁裂度值与网络结构的部分关系.本文的研究表明，弱毁裂度在区分图的抗毁性差异方面有一定的优势.

在图的抗毁性参数中，属于毁裂度系列的有毁裂度，边毁裂度和弱毁裂度三个.这类参数本质上反映的是在最极端的情形下网络被破坏的程度和恢复难度.这些参数相互独立，且在定量刻画网络抗毁性方面侧重不同，因此各有优劣.关于这些新的参数还有很多重要问题值得研究，如树等特殊图类的参数算法设计与复杂性分析，毁裂度意义下的极值网络构造等.