岳緒彬, 王維凡

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江金華 321004)

設(shè) G是一個(gè)連通圖,V(G)和 E(G)分別表示 G的頂點(diǎn)集合和邊集合.令 n表示圖 G的頂點(diǎn)數(shù),有時(shí)記 n=|G|=|V(G)|.設(shè) v∈V(G),且 k≥1是一個(gè)整數(shù).k-防火問(wèn)題敘述如下:火開(kāi)始在頂點(diǎn) v處燃起,一個(gè)消防員可以選擇 k個(gè)沒(méi)有起火的頂點(diǎn)加以防護(hù) (等價(jià)地,有 k個(gè)消防員每人每次保護(hù) 1個(gè)頂點(diǎn)),消防員和火源在圖 G上交替移動(dòng).假設(shè)一旦一個(gè)頂點(diǎn)已經(jīng)被消防員防護(hù)下來(lái),那么在接下來(lái)火源的傳播過(guò)程中,它一直是受保護(hù)的.當(dāng)消防員移動(dòng)后,起火的頂點(diǎn)將使那些沒(méi)有被防護(hù)的鄰點(diǎn)起火.當(dāng)火源沒(méi)法再傳播時(shí),整個(gè)過(guò)程就結(jié)束了.消防員的任務(wù)是防護(hù)盡可能多的頂點(diǎn),也就是當(dāng)這個(gè)過(guò)程結(jié)束時(shí)沒(méi)有被燒的頂點(diǎn)盡可能地多.用 snk(v)表示當(dāng) v為火源時(shí),k-防火過(guò)程中消防員救下的最多頂點(diǎn)個(gè)數(shù).圖 G的k-存活率ρk(G)定義為 G的頂點(diǎn)隨機(jī)起火時(shí) k-防火過(guò)程可救下的頂點(diǎn)的平均存活率,即

文獻(xiàn)[1]首先引入了圖的存活率的概念,并對(duì)樹(shù)、外可平面圖和哈林圖等特殊圖類(lèi)研究了單人防火問(wèn)題,即證明了以下結(jié)果:

最近,文獻(xiàn)[2]應(yīng)用概率方法證明了幾乎所有圖 G都有ρk(G)→0(當(dāng) G的點(diǎn)數(shù)逐漸增加時(shí)).此外,文獻(xiàn)[2]還證明了以下一些結(jié)果:

關(guān)于圖的防火問(wèn)題的其他結(jié)果可參考文獻(xiàn)[3-5].

一個(gè)哈林圖定義為 H=T∪C,其中 T是被嵌入歐幾里得平面的一棵樹(shù),T中沒(méi)有 2度點(diǎn)且至少有一個(gè)度大于等于 3的頂點(diǎn),C是依照 T的嵌入順次連接 T的所有葉點(diǎn)所得到的圈.稱 T是 H的特征樹(shù),C為 H的外圈.顯然,H是 3-連通的平面圖.關(guān)于哈林圖的結(jié)構(gòu)性質(zhì)和相關(guān)參數(shù)見(jiàn)文獻(xiàn)[6-8].

本文考慮哈林圖的 2-防火問(wèn)題,即證明 n-點(diǎn)哈林圖 H滿

引理 1 設(shè) H=T∪C是一個(gè)哈林圖.若 P為 T中有 k(≥2)個(gè)頂點(diǎn)的一條路,則 sn2(P)>(k-2)n.

證明 假設(shè) P=v1v2…vk,k≥2,那么 T-E(P)是一個(gè)森林.對(duì) 1≤i≤k,設(shè) Ti表示 T-E(P)中唯一包含 vi的分支,且令 ti=|Ti|.對(duì) 2≤i≤k-1,設(shè) Tl(i)和 Tr(i)分別表示 Ti在路 P的左側(cè)和右側(cè)部分,亦即Ti=Tl(i)∪Tr(i)且 Tl(i)∩Tr(i)={vi}.設(shè) C=y0y1…ym-1y0是 H的外圈,其中 m≥3,且假定 C的方向是順時(shí)針的.由哈林圖的定義,存在 C中的子路Q=yiyi+1…yj使得 V(Q)是 T1的所有葉子的集合,這里下標(biāo)取模 m.稱 yi是 T1的最后面的葉子 (依順時(shí)針?lè)较蛟?C上),yj是 T1的最前面的葉子 (依順時(shí)針?lè)较蛟?C上),2,3,…,k-2},能夠定義 Td在 C上的最后面的和最前

圖 1 路 P上頂點(diǎn) vi處起火時(shí)的防火策略

易見(jiàn):當(dāng)火在 v1處燃起時(shí),采用策略 1)能救下 T-V(T1)中的所有頂點(diǎn),即 sn2(v1)≥n-t1;當(dāng)火在vk處燃起時(shí),采用策略 2)能救下 T-V(Tk)中的所有頂點(diǎn),即 sn2(vk)≥n-tk;當(dāng)火在 vi處燃起時(shí) (2≤i≤k-1),采用策略 3)能救下 T-V(Ti)-V(Ti+1)中的所有頂點(diǎn),即 sn2(vi)≥n-ti-ti+1.因此

引理 1證畢.

設(shè) T是一個(gè)哈林圖的特征樹(shù),Tr表示 T中以 r為根的子樹(shù).對(duì)每個(gè)點(diǎn) v∈V(T),存在唯一一條 (r,v)-路 rx1x2…xkv,稱 xk為 v的父親,而 v的其他鄰點(diǎn)稱為 v的兒子.一個(gè)有根樹(shù) Tr的高度定義為它的從根到葉子的最長(zhǎng)路的長(zhǎng)度;一個(gè)頂點(diǎn) v在 Tr中的高度定義為有根子樹(shù) Tv的高度.

圖 2 有根子樹(shù)的防火策略

引理 2 設(shè) H=T∪C是一個(gè)哈林圖,S是 T中高度為 h的有根子樹(shù),那么 sn2(S)≥(n-h)|S|.

證明 任取 v∈V(S).設(shè) Tv是 T的以 v為根的子樹(shù),C=y0y1…ym-1y0是 H的外圈,且定義 C的方向是順時(shí)針的.于是,存在 C中的一段路 Q=yiyi+1…yj,使得 V(Q)是 Tv的所有葉子的集合,其中下標(biāo)取模 m.

假設(shè)火在 v處燃起,則執(zhí)行下面的防護(hù)策略 (如圖2所示):

第 1步:防護(hù) yj和 v在 T中的父親 v′;

第 2步:防護(hù) yi-1.

易見(jiàn),應(yīng)用上面的策略,可以救下 yi-1和 T-V(Tv)中的所有頂點(diǎn) (注意 Tv=Sv).如果 S=T且火源在根部,那么就能防護(hù)根的兒子節(jié)點(diǎn).

設(shè) Hi(0≤i≤h)是 S中高度為 i的頂點(diǎn)集合,那么對(duì)任意示 Tv的頂點(diǎn)個(gè)數(shù).因此

故

引理 2證畢.

證明 任選一個(gè)頂點(diǎn)作為 T的根,然后對(duì) T的高度運(yùn)用歸納法,證明 T可以被剖分成長(zhǎng)路集合 P和短樹(shù)集合 S的并.設(shè) P是 T中一條從根到葉子的最長(zhǎng)路.如果 P的頂點(diǎn)個(gè)數(shù)少于 2n,那么 T的高度至多為 2n-2.因此 T就是一棵短樹(shù),結(jié)論成立.否則,刪去 T中所有 P的頂點(diǎn)得到一個(gè)森林 F.F是有根樹(shù)的集合,且 P的選擇保證了 F中的每棵有根子樹(shù)也是 T的有根子樹(shù).另外,F的每棵子樹(shù)的高度小于它在 T中的高度.由歸納假設(shè),F中的每棵子樹(shù)可以被剖分成長(zhǎng)路集合和短樹(shù)集合.這些集合和 P就可以滿足對(duì) T的剖分要求.

如果 T本身是一棵短樹(shù),即 P=?,結(jié)論可以由引理 2直接得到.否則假設(shè) |P|≥1,由引理 1和引理2得

故

因此

定理 1證畢.

由定理 1立即得到推論 1.

[1]CaiLeizhen,WangWeifan.The surviving rate of a graph for the firefighter problem[J].SI AM J DiscreteMath,2009,23(4):1814-1826.

[2]WangWeifan,Finbow S,Wang Ping.The surviving rate of an infected network[J].Theoretical Computer Science,2010,411(40/41/42):3651-3660.

[3]Finbow S,King A,MacGillivraya G,et al.The firefighter problem for graphs of maximum degree three[J].Discrete Math,2007,307(16):2094-2105.

[4]Wang Ping,Moeller SA.Fire control on graphs[J].J CombMath Comb Comp,2002,41:19-34.

[5]Finbow S,HartnellB,LiQ.On minimizing the effects of fire or a virus on a network[J].J CombMath Comb Comp,2000,33:311-322.

[6]ChanW H,PeterC B Lam,ShiuW C.Edge-face total chromatic numberof Halin graphs[J].SI AM J DiscreteMath,2009,23(3):1646-1654.

[7]ChenMin,WangWeifan.The 2-dipath chromatic number of Halin graphs[J].Inform ProcessLett,2006,99(2):47-53.

[8]Stadler P F.Minimum cycle bases of Halin graphs[J].J Graph Theory,2003,43(2):150-155.