郭文婷,孔將旭

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

1995年,Hartnell[1]首次提出了消防員問(wèn)題(Firefighter Problem)。設(shè)G是一個(gè)連通圖,k是正整數(shù)。假設(shè)火在圖G的一個(gè)頂點(diǎn)或多個(gè)點(diǎn)燃起,消防員每步選擇k個(gè)沒(méi)有著火的頂點(diǎn)加以防護(hù),然后火蔓延到其未被保護(hù)且沒(méi)有著火的鄰點(diǎn),火和消防員在圖G上交替移動(dòng)。當(dāng)火沒(méi)法再傳播時(shí),整個(gè)過(guò)程結(jié)束。

為了研究一個(gè)圖的整體防火能力,蔡雷震和王維凡[2]首先提出了圖的存活率的概念。設(shè)G是n階連通圖,snk(v)表示當(dāng)v為火源點(diǎn)時(shí),k個(gè)消防員最多能防護(hù)的頂點(diǎn)個(gè)數(shù)。當(dāng)火等概率的在圖G的一個(gè)頂點(diǎn)燃起時(shí),k個(gè)消防員最多能保護(hù)的頂點(diǎn)數(shù)的期望稱為圖G的k-存活率,記為ρk(G),即

顯然,0<ρk(G)<1,且對(duì)任意i>j,有ρi(G)≥ρj(G)成立。關(guān)于存活率和消防員問(wèn)題的最新研究進(jìn)展,請(qǐng)參閱王維凡和孔將旭的綜述文獻(xiàn)[3]。

1 幾個(gè)預(yù)備引理設(shè)

G是簡(jiǎn)單平面圖,我們用V(G),E(G),F(G),Δ(G)和δ(G)分別表示圖G的頂點(diǎn)集、邊集、面集,最大度和最小度。對(duì)v∈V(G),N(v)={u|uv∈E(G)},點(diǎn)v的度數(shù)d(v)=|N(v)|。對(duì)f∈F(G),用b(f)表示圍成面f的周界,d(f)表示圍成面f的周界的邊數(shù),稱為f的度。一個(gè)度為k,至少為k或至多為k的點(diǎn)(面)分別稱為k-點(diǎn),k+-點(diǎn)或k--點(diǎn)(k-面,k+-面或k--面)。對(duì)于一條邊uv,如果u是i-點(diǎn),v是j-點(diǎn),那么uv邊稱為(i,j)-邊,并且用f1和f2表示與uv相關(guān)聯(lián)的兩個(gè)面,當(dāng)uv是割邊時(shí),f1=f2。對(duì)于一個(gè)3-面[uvw],如果u是i-點(diǎn),v是j-點(diǎn),w是k-點(diǎn),那么[uvw]面稱為(i,j,k)-面。

引理1[8](平面圖分離定理)設(shè)G是一個(gè)極大平面圖,|V(G)|=n,T是G的任意一棵支撐樹(shù),則存在一條邊e∈E(G)E(T)使得T+e中的唯一一個(gè)圈C滿足圈內(nèi)和圈外的點(diǎn)數(shù)都小于(2n)/3。

引理2[6]設(shè)G是平面圖,T是G的任意一棵以r為根點(diǎn)的支撐樹(shù),則T中存在一條以x,y為端點(diǎn)的路P(xy),使得圈C=P(xy)+{xy}(xy可以不是G中的邊,x,y≠r)滿足圈內(nèi)和圈外的點(diǎn)數(shù)都小于(2n)/3。

由引理4我們可以得到以下推論。

推論1設(shè)G是n(≥24)階不含5-圈平面圖,uv∈E(G)。如果d(u)+d(v)≤9,那么sn(4,2)(uv)≥(n-4)/3。

令E1(G)={uv∈E(G)|d(u)+d(v)≤9}。

推論2設(shè)G是n(≥24)階不含5-圈平面圖,uv∈E(G),并且uv僅關(guān)聯(lián)一個(gè)3-面。如果d(u)+d(v)≤10,那么sn(4,2)(uv)≥(n-4)/3。

令E2(G)={uv∈E(G)|uv僅關(guān)聯(lián)一個(gè)3-面且d(u)+d(v)≤10}。

推論3設(shè)G是n(≥24)階不含5-圈平面圖,uv∈E(G),并且uv關(guān)聯(lián)兩個(gè)3-面。如果d(u)+d(v)≤11,那么sn(4,2)(uv)≥(n-4)/3。

令E3(G)={uv∈E(G)|uv關(guān)聯(lián)兩個(gè)3-面且d(u)+d(v)≤11},E*(G)=E1(G)∪E2(G)∪E3(G)。

2 (4,2)-邊存活率

本節(jié)我們運(yùn)用權(quán)轉(zhuǎn)移的方法證明最小度至少為3且不含5-圈的平面圖的(4,2)-邊存活率大于某個(gè)正常數(shù)。

對(duì)任意的uv∈E(G),首先我們對(duì)每條邊定義初始權(quán)函數(shù)

其中a=1/42。由歐拉公式|V(G)|-|E(G)|+|F(G)|=2,可導(dǎo)出下面的等式:

(Rule)設(shè)uv∈E(G)E*(G)關(guān)聯(lián)兩個(gè)3-面f1=[uvw]和f2=[uvz],d(u)=i,d(v)≥12-i,其中3≤i≤6。假設(shè)d(w)≤d(z)。(如圖1)

圖1 權(quán)轉(zhuǎn)移規(guī)則示意圖Figure 1 Discharging rules

(R1)若d(z)≤10-i,則

(R2)若d(w)≤10-i

(R3)若d(w)≥11-i,則

因?yàn)镚是最小度至少為3的不含5-圈平面圖,所以G不含下面三個(gè)結(jié)構(gòu):

(i)5-面;

(ii)兩個(gè)相鄰的3-面和4-面;

(iii)3-面相鄰兩個(gè)不相鄰的3-面。

觀察1設(shè)xy∈E*(G),則xy最多得到權(quán)1/9+a。

斷言1設(shè)xy∈E(G)E*(G)。若xy為(9+,9+)-邊,則xy最多得到權(quán)1/9+a,此時(shí)xy關(guān)聯(lián)一個(gè)(3,9+,9+)-面;否則,xy最多得到權(quán)1/18+a/2,特別地,如果xy是(3,8+)-邊,則xy得不到權(quán)。

證明設(shè)xy關(guān)聯(lián)的兩個(gè)面為f1和f2,由對(duì)稱性,不妨設(shè)d(f2)≥d(f1)。

1)d(f2)≥d(f1)≥4,則根據(jù)(Rule)xy不得到權(quán)。

2)d(f2)≥4,d(f1)=3,設(shè)f1=[xyz]。只有當(dāng)fxz和fyz都是3-面,邊xz和yz才給邊xy各轉(zhuǎn)權(quán)1/18+a/2,即2×(1/18+a/2)=1/9+a。由于G不含3-面相鄰兩個(gè)不相鄰的3-面,所以fxz和fyz相鄰,此時(shí)d(z)=3,由(Rule)得d(x)≥9,d(y)≥9,即f1是(3,9+,9+)-面。如果xy是(3,8+)-邊,那么只有當(dāng)xz關(guān)聯(lián)兩個(gè)3-面時(shí)才轉(zhuǎn)權(quán),此時(shí)d(z)≥9,根據(jù)(R2)得xy沒(méi)得到權(quán)。

3)d(f1)=d(f2)=3,設(shè)f1=[xyz],f2=[xyw]。由于G不含3-面相鄰兩個(gè)不相鄰的3-面,當(dāng)d(y)≥d(x)≥4時(shí),fxz,fyz,fxw,fyw都是4+-面,因此xy得不到權(quán);當(dāng)d(x)=3時(shí),因?yàn)閤y∈E(G)E*(G),由推論3得d(y)≥9,若fxz,fyz,fxw,fyw都是4+-面,則xy得不到權(quán),否則其中至少有一個(gè)是3-面,由于G不含3-面相鄰兩個(gè)不相鄰的3-面,因此zw∈E(G)且fxz=fxw,由(Rule)得只有當(dāng)z和w都是9+-點(diǎn)時(shí)才轉(zhuǎn)權(quán),并且由(R3)得xy沒(méi)得到權(quán)。因此,斷言1得證。

引理5設(shè)G是不含5-圈的連通平面圖,n>23,δ(G)≥3,則對(duì)G的每條邊uv滿足:

1)若uv∈E*(G),則w0(uv)≤4/9+2a;

2)若uv∈E(G)E*(G),則w0(uv)≤0。

證明1)若uv∈E*(G),當(dāng)d(u)=d(v)=d(f1)=d(f2)=3時(shí),初始權(quán)最大。由觀察1得,邊uv最多得到權(quán)1/9+a。因此,

2)uv∈E(G)E*(G),設(shè)f1和f2是與uv關(guān)聯(lián)的兩個(gè)面(當(dāng)uv是割邊時(shí),f1和f2是同一個(gè)面),且d(f1)≤d(f2)。根據(jù)推論1得d(u)+d(v)≥10。

①d(f1)≥4。由(R1)—(R3)得,邊uv既沒(méi)有得到權(quán)也沒(méi)有轉(zhuǎn)出權(quán)。因此,

w0(uv)=w(uv)

②d(f1)=3,d(f2)≥4。由推論2得,d(u)+d(v)≥11,不妨設(shè)d(u)≤d(v)。因?yàn)镚不含5-面,兩個(gè)相鄰的3-面和4-面以及3-面相鄰兩個(gè)不相鄰的3-面,所以d(f2)≥6。由于uv只關(guān)聯(lián)一個(gè)3-面,因此uv至多得到權(quán)2×(1/18+a/2)。

若d(u)≥6,則

若d(u)=5,則d(v)≥6,由斷言1得uv最多得到權(quán)1/18+a/2,從而得

若d(u)=4,則d(v)≥7,由斷言1得uv最多得到權(quán)1/18+a/2,從而得

若d(u)=3,則d(v)≥8,由斷言1得uv沒(méi)得到權(quán),從而得

③d(f1)=d(f2)=3。由推論3可得,d(u)+d(v)≥12。由(R1)—(R3)得,邊uv通過(guò)關(guān)聯(lián)3-面f1,f2轉(zhuǎn)出權(quán)2×(1/18+a/2)。因此,

證明由于經(jīng)過(guò)權(quán)轉(zhuǎn)移后權(quán)和保持不變,可得下面的不等式,

因此,

3 結(jié) 語(yǔ)

由于圖F是有2n+2個(gè)點(diǎn)和5n條邊且最小度為3的平面圖(如圖2),不難證明ρ′(F)→0(n→∞),所以至少需要兩個(gè)消防員。因此,對(duì)最小度至少為3的平面圖的邊存活率我們提出如下問(wèn)題。

圖2 圖FFigure 2 Graph F

DOI:10.11845/sxjz.2020007a.

DOI:10.11845/sxjz.2020007a.