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

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

1 引言

網(wǎng)絡(luò)的廣泛使用和中斷的頻繁發(fā)生，使得抗毀性與可靠性研究愈發(fā)重要.連通度與邊連通度可以刻畫圖的結(jié)構(gòu)特征，但這兩個參數(shù)考慮的是在最壞情形下破壞網(wǎng)絡(luò)的難易程度[1-3].后來一些新的參數(shù)不斷被引入[4-7]，用以度量網(wǎng)絡(luò)抗毀性.這些參數(shù)既考慮了破壞網(wǎng)絡(luò)的難度，又反映了網(wǎng)絡(luò)被破壞的程度.但是它們的側(cè)重點各不相同，因而至今沒有度量網(wǎng)絡(luò)抗毀性的統(tǒng)一標準.

弱毀裂度是一個視角較為全面的抗毀性參數(shù).設(shè)G是一個簡單連通圖，其弱毀裂度定義為[8]

其中X表示G的點割集，ω(G-X)和me(G-X)分別表示G-X的連通分支數(shù)和最大分支中的邊數(shù).若存在X*?V(G)，使得rw(G) =ω(G-X*)-|X*|-me(G-X*)，則稱X*為G的一個rw-集.

本文通過研究該參數(shù)的性質(zhì)和取值范圍，以及Nordhaus-Gaddum(N-G)型問題，揭示圖的弱毀裂度與網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系.

2 弱毀裂度與圖的結(jié)構(gòu)

圖(網(wǎng)絡(luò))的抗毀性參數(shù)有很多，這些參數(shù)與圖的基本參數(shù)之間的關(guān)系，在很大程度上反映了圖的結(jié)構(gòu)特征.下面給出圖的弱毀裂度與其它基本參數(shù)之間的關(guān)系，也可以看作是弱毀裂度的界，是估計一般圖的弱毀裂度大小的重要工具.

定理1 設(shè)G是周長為c(c ＞0)的n(n ≥4)階連通圖，則rw(G)≤n-c.

證明 設(shè)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 設(shè)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 設(shè)G是n(n ≥4)階連通圖，則rw(G)≤n-2δ(G).

證明 設(shè)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,··· ,ω)所含點數(shù)不少于2.否則，若存在一個孤立點u，那么就有d(u)≤|X|＜δ，導致矛盾.

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

下面討論函數(shù)f(x)的單調(diào)性.首先，有

因為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 上述結(jié)論中的界是最好可能的，可在n(n ≥4，偶數(shù))階-正則圖達到.

推論1 對于n階圖G，有rw(G)≤n-2κ(G), rw(G)≤n-2λ(G).

定理3 設(shè)G是n階圖，則有rw(G)≤r(G)+1，其中r(G)為G的毀裂度[5].

證明 設(shè)X*是G的一個rw-集.因為對于G的任一點割集X，有

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

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

推論2 若連通圖G同構(gòu)于樹或圈，則rw(G)=r(G)+1.

證明 設(shè)X是圖G的任一點割集.如果去掉X中的點，則G-X的任一分支要么是樹，要么是孤立點，且m(G-X)-1=me(G-X).故有

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

定理4 假設(shè)圖G是非完全連通的，則rw(G)≤α(G)-Iw(G)，其中Iw(G)為G的弱完整度.

證明 設(shè)X是G的一個rw-集，則

從而

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

堅韌度作為一個重要的網(wǎng)絡(luò)抗毀性參數(shù)已被廣泛地應用.對于非完全連通圖G，其堅韌度定義為[3]

其中ω(G-X)表示G-X的連通分支數(shù).

下面的定理5 揭示了堅韌度和弱毀裂度之間的關(guān)系.

從而

因為對任意的X ?V(G), κ(G)≤|X|≤β(G), me(G-X)≥0，故有

定理6 不存在rw(G)=t(G)的n階連通圖G.

證明 假設(shè)存在一個n階圖G，使得rw(G) =t(G).由于t(G)≥0，且rw(G)是整數(shù)，就有t(G)≥1.設(shè)X是G的一個點割集，則|X|≥ω(G-X)，從而

因為對任意的X ?V(G)都有-me(G-X)≤0，所以rw(G)≤0，即t(G)≤0，這顯然是不可能的.定理得證.

圖的相對斷裂度(亦稱為離散數(shù))是一個常用的網(wǎng)絡(luò)抗毀性參數(shù).對于圖G，其定義為s(G)=max{ω(G-X)-|X|:ω(G-X)≥2}，其中X是G的點割集，ω(G-X)表示G-X的連通分支數(shù)[10].

弱毀裂度與離散數(shù)有如下的關(guān)系：

定理7 設(shè)G是連通圖，則rw(G)≤s(G).

證明 設(shè)X是G的一個點割集，則有ω(G-X)-|X|≤s(G).所以有

于是

因為，對任意的X ?V(G)，都有me(G-X)≥0，所以rw(G)≤s(G).

3 弱毀裂度的N-G 型問題

當一個圖的邊數(shù)明顯大于同階完全圖的一半時，其補圖的研究相對容易一些.圖與其補圖結(jié)構(gòu)之間的關(guān)系可以通過某些參數(shù)和與積的形式刻畫.這個問題是Nordhaus 和Gaddum 提出的，稱為N-G 型問題.本節(jié)主要考慮圖的弱毀裂度和形式的N-G 型問題.

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

4 結(jié)語

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

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