哈林圖的防火問題＊

岳緒彬, 王維凡

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

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

文獻[1]首先引入了圖的存活率的概念,并對樹、外可平面圖和哈林圖等特殊圖類研究了單人防火問題,即證明了以下結果:

最近,文獻[2]應用概率方法證明了幾乎所有圖 G都有ρk(G)→0(當 G的點數逐漸增加時).此外,文獻[2]還證明了以下一些結果:

關于圖的防火問題的其他結果可參考文獻[3-5].

一個哈林圖定義為 H=T∪C,其中 T是被嵌入歐幾里得平面的一棵樹,T中沒有 2度點且至少有一個度大于等于 3的頂點,C是依照 T的嵌入順次連接 T的所有葉點所得到的圈.稱 T是 H的特征樹,C為 H的外圈.顯然,H是 3-連通的平面圖.關于哈林圖的結構性質和相關參數見文獻[6-8].

本文考慮哈林圖的 2-防火問題,即證明 n-點哈林圖 H滿

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

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

圖 1 路 P上頂點 vi處起火時的防火策略

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

引理 1證畢.

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

圖 2 有根子樹的防火策略

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

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

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

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

第 2步:防護 yi-1.

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

設 Hi(0≤i≤h)是 S中高度為 i的頂點集合,那么對任意示 Tv的頂點個數.因此

故

引理 2證畢.

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

如果 T本身是一棵短樹,即 P=?,結論可以由引理 2直接得到.否則假設 |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.