一類稀疏圖的邊存活率

郭文婷,孔將旭

(中國(guó)計(jì)量大學(xué) 理學(xué)院,浙江 杭州 310018)

1995年,Hartnell[1]在第25屆曼尼托巴會(huì)議上提出了消防員問(wèn)題。設(shè)G是一個(gè)有n個(gè)點(diǎn)的連通圖,假設(shè)火源在G的某個(gè)頂點(diǎn)v處燃起,k個(gè)消防員任意選擇k個(gè)沒(méi)有著火的點(diǎn)進(jìn)行保護(hù),然后火蔓延到v的沒(méi)有被保護(hù)且沒(méi)著火的鄰點(diǎn),接著消防員又任意選擇k個(gè)沒(méi)有著火的頂點(diǎn)進(jìn)行保護(hù),火繼續(xù)蔓延,火和消防員依次這樣交替地在圖G上移動(dòng)。當(dāng)火源無(wú)法再傳播時(shí),整個(gè)過(guò)程結(jié)束。

2002年,為了研究圖的魯棒性,Cai和Wang[2]提出了圖的存活率的概念。當(dāng)火在v處燃起時(shí),用snk(v)表示k個(gè)消防員最多能保護(hù)的頂點(diǎn)數(shù)。當(dāng)火隨機(jī)地在圖G的一個(gè)頂點(diǎn)燃起時(shí),k個(gè)消防員最多能保護(hù)的頂點(diǎn)數(shù)的平均值稱為圖G的k-存活率,記為ρk(G),即

當(dāng)k=1時(shí),sn(v)=sn1(v),ρ(G)=ρ1(G)。

一般的,當(dāng)火源點(diǎn)多個(gè)時(shí),有對(duì)應(yīng)的存活率的概念[3,4]。設(shè)F?V(G),|F|=f≥2為固定的正整數(shù)。snk(G,F)表示當(dāng)火源在集合F中的點(diǎn)燃起時(shí),k個(gè)消防員能保護(hù)的最大頂點(diǎn)數(shù)。當(dāng)火隨機(jī)地在圖G的f個(gè)頂點(diǎn)燃起時(shí),k個(gè)消防員最多能保護(hù)的頂點(diǎn)數(shù)的平均值稱為圖G的多火源存活率,記為ρk(G,f),即

1 主要結(jié)果

本文運(yùn)用圖染色理論中的經(jīng)典方法“權(quán)轉(zhuǎn)移”[7]證明以下結(jié)果:

推論4設(shè)G是一個(gè)n≥3且δ(G)=2的連通圖。

推論5設(shè)G是一個(gè)至少有3個(gè)點(diǎn)的連通平面圖且δ(G)=2。

2 定理3的證明

(1)

表達(dá)式(1)可以寫成如下形式:

其中,

我們先通過(guò)權(quán)轉(zhuǎn)移的方法證明如下斷言。

根據(jù)上面的規(guī)則將初始權(quán)重新分配,得到新的權(quán)函數(shù)記為w′(uv)。由于權(quán)轉(zhuǎn)移只是將權(quán)重新分配,不改變權(quán)的總和,因此,可得下面的等式

根據(jù)不等式(1)和斷言1,有

引理2設(shè)G是一個(gè)至少有3個(gè)頂點(diǎn)的連通圖,那么對(duì)任意的uv∈E(G),有

根據(jù)引理1和引理2,我們可以得到如下不等式:

因此,

定理3得證。

3 結(jié) 語(yǔ)

本文研究了最小度為2且平均度小于2.4的連通圖的邊存活率,用“權(quán)轉(zhuǎn)移”的方法證明了這類稀疏圖有正的邊存活率,從火源的角度推廣了定理1的結(jié)果。定理3中邊存活率的下界不是最優(yōu)的,可以通過(guò)設(shè)計(jì)更精細(xì)的權(quán)轉(zhuǎn)移規(guī)則得到更好的下界,但尋找最好的下界并不是本文的主要目的。此外,定理3中最小度為2的條件是必須的,因?yàn)棣?K1,n-1)=1且ρ′(K1,n-1)→0(n→∞)。最后,定理3條件中的上界也不是最優(yōu)的,因此可以提出下面兩個(gè)問(wèn)題:

問(wèn)題1設(shè)k*,ε為正實(shí)數(shù),G是一個(gè)有n個(gè)點(diǎn)m條邊的連通圖,滿足mε。

問(wèn)題2設(shè)ε為正實(shí)數(shù),g*為正整數(shù),G是一個(gè)g(G)≥g*且δ(G)=2的連通平面圖,確定g*的閾值使得ρ′(G)>ε。