圖的弱毀裂度與網絡抗毀性

劉 勇, 楊淑姝, 魏宗田, 岳 超

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

1 引言

網絡的廣泛使用和中斷的頻繁發(fā)生，使得抗毀性與可靠性研究愈發(fā)重要.連通度與邊連通度可以刻畫圖的結構特征，但這兩個參數考慮的是在最壞情形下破壞網絡的難易程度[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 型問題.本節(jié)主要考慮圖的弱毀裂度和形式的N-G 型問題.

注4 定理中的界是緊的，且達到該界的圖不唯一.如C5取得下界-2；K1,n-1取得上界n-2.

4 結語

本文給出若干弱毀裂度的界，以及該參數與圖的其它參數之間的關系.在此基礎上，進一步研究了弱毀裂度的N-G 型問題.通過建立參數模型，利用微分或差分方法計算和比較參數值的大小關系，得到弱毀裂度值與網絡結構的部分關系.本文的研究表明，弱毀裂度在區(qū)分圖的抗毀性差異方面有一定的優(yōu)勢.

在圖的抗毀性參數中，屬于毀裂度系列的有毀裂度，邊毀裂度和弱毀裂度三個.這類參數本質上反映的是在最極端的情形下網絡被破壞的程度和恢復難度.這些參數相互獨立，且在定量刻畫網絡抗毀性方面?zhèn)戎夭煌?，因此各有?yōu)劣.關于這些新的參數還有很多重要問題值得研究，如樹等特殊圖類的參數算法設計與復雜性分析，毀裂度意義下的極值網絡構造等.