一類定向平面圖的存活率

王維凡,　裘霞霜,　黃丹君

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

?

一類定向平面圖的存活率

王維凡,裘霞霜,黃丹君

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

防火問題;存活率;有向圖;平面圖

0　引　言

1995年,Hartnell[1]在第25屆曼尼托巴組合數學與計算會議上提出了有限圖G上的防火問題.假設火在圖G的某個頂點v處開始燃燒,消防員選擇某個未燃燒的頂點進行防護,消防員和火在圖G上依次交替移動.一旦某個頂點被消防員防護下來,就稱這個頂點在接下來的防火過程中一直都是受防護的.在消防員移動后,火繼續向已燃燒頂點的其他鄰點(未被防護的)蔓延.當火無法再繼續蔓延時,就稱整個防火過程結束了.2009年,文獻[2]提出了圖的存活率的概念.設G是含有n個頂點的連通圖,并假設v是著火點.在整個防火過程中,稱消防員最多能防護下來的頂點數為v的存活數,記為sn(v).當火隨機地在G的某個頂點處燃起時,稱消防員最多能防護下來的頂點數的平均比例為圖G的存活率,記為ρ(G),公式表示為

類似地,給定一個正整數k≥1,若在防火的過程中,消防員每一步選擇k個未燃燒的頂點進行防護,稱其為k-防火問題.用snk(v)表示當點v為火源時,消防員最多能防護下來的頂點數.ρk(G)表示圖G的k-存活率,公式表示為

文獻[4-5]分別證明了：平面圖是4-好的.這個結果最近被改進為：平面圖是3-好的[6-7]；文獻[8]證明了圍長至少為7的平面圖是1-好的；使得平面圖是2-好的一些充分條件則在文獻[4,9-10]中被給出.

假設有向圖D上的某一個頂點v開始起火(規定火是沿著弧的方向傳播的),消防員選擇一些未被燃燒的頂點進行防護,消防員和火在圖上依次交替移動.類似地,用snk(v)表示v的k-存活數,于是有向圖D的k-存活率定義為

當k=1時,記ρ(D)=ρ1(D).有向圖的防火問題是由文獻[11]首先提出和研究的,證明了下面幾個結果:

本文旨在擴充上面的結果 3),即證明以下定理:

1　結構性質

若圖G能被畫到平面上,使得任意2條邊都只在端點處相交,則稱G是可平面圖,且稱在平面上以這種方式畫出的圖為平面圖.平面圖G的頂點集、邊集、面集分別記為V(G),E(G),F(G).設n=|V(G)|.對于任意的面 f∈F(G),記 f的邊界為b(f).若u1,u2,…,um是b(f)上按照順時針方向排列的頂點,則記 f=[u1u2…um].設x∈V(G)∪F(G),x 在G中的度數記為d(x).一個度數為k、至少為k或者至多為k的面分別記作k-面、k+-面、k--面.設v∈V(G),用t(v)表示與v相關聯的3-面的個數.如果2個圈(或面)至少有1條公共邊,那么稱這2個圈(或面)是相鄰的.

若點v∈V(D)滿足sn(v)≥n-3,則稱v是好點,反之為壞點.記Vg是D中由所有好點構成的集合,Vb=V(D)Vg,ng=|Vg|.顯然,出度至多為1的點是一個好點.

P1:3-面和3-面相鄰;

P2:3-面和4-面相鄰;

P3:4-面和4-面相鄰.

引理1若一個頂點v滿足d+(v)=2,d-(v)=0,且v在一個3-面 f上,則與v相關聯的另一個面是6+-面.

證明設 f=[vv1v2],且假設與v相關聯的另一個面 f ′是5--面,由P1～P3知 f ′是一個5-面,記f ′=[v1vv2v3v4],從而可以找到一個4-圈v1v2v3v4v1與3-圈v1v2vv1相鄰,矛盾.引理1證畢.

引理2設 f=[uvw]是一個3-面,v是一個出度為2的壞點,且v→u,v→w,則max{d+(u),d+(w)}≥3.

證明反證法,不妨設d+(u)=d+(w)=2且u→w.設N+(u)={u1,w}和N+(w)={w1,w2}.當點v起火時,先防w,火向u蔓延后,再防u1,使得火不再蔓延.所以,sn(v)≥n-2,說明點v是一個好點,矛盾.引理2證畢.

引理3設 f=[uvw]是一個3-面,則max{d+(u),d+(v),d+(w)}≥3,或者u,v,w 中至少有1點是好點.

證明假設u,v,w都是出度為2的壞點，則由對稱性可分以下2種情況討論：

1)v→u,u→w,w→v.設N+(v)={u,v1},N+(u)={w,u1},N+(w)={v,w1}.當點v起火時,消防員依次防護點v1,u1,w1,使得火不再蔓延.所以,sn(v)≥n-3,說明點v是一個好點,矛盾.

2)v→u,v→w,u→w.設N+(u)={u1,w}.當點v起火時,消防員先防w,火向點u蔓延后,消防員再防u1,使得火不再蔓延.因此,sn(v)≥n-2,說明點v是一個好點,矛盾.引理3證畢.

2　權轉移

可以得到以下恒等式:

定義以下權轉移規則:

記通過權轉移以后得到的新的權函數為ω′.

1)若v∈Vg,則ω′(v)≥-4;

2)設v∈Vb,則 d+(v)≥2.分下面3種情形:

②d+(v)=3,即ω(v)=2.按與v相關聯的3-面的個數t(v)分以下幾種子情形進行討論.

引理4證畢.

接下來證明定理1.由引理4可得,

定理1證畢.

3　結　語

證明了沒有相鄰4--圈的定向平面圖是1-好的.這個結果推廣了文獻[11]的一個結果:不含4-圈的定向平面圖是1-好的.結合平面圖的結構性質,接下來可以考慮下面的問題:

問題1是否所有的定向平面圖都是1-好的?

問題2是否所有的平面圖(不是定向的)都是2-好的?

[1]HartnellB.Firefighter!Anapplicationofdomination[C]//Presentationatthe25thManitobaConferenceonCombinatorialMathematicsandComputing.Winnipeg:UniversityofManitoba,1995.

[2]CaiLZ,WangWF.Thesurvivingrateofagraphforthefirefighterproblem[J].SIAMJDiscreteMath,2009,23(4):1814-1826.

[3]WangW,FinbowS,WangP.Thesurvivingrateofaninfectednetwork[J].TheoretComputSci,2010,411(40/41/42):3651-3660.

[4]EsperetL,HeuvelJ,MaffrayF,etal.Firecontainmentinplanargraphs[J].JGraphTheory,2012,73(3):267-279.

[5]KongJiangxu,WangWeifan,ZhuXuding.Thesurvivingrateofplanargraphs[J].TheoretComputSci,2012,416:65-70.

[6]GordinowiczP.Planargraphisonfire[J].TheoretComputSci,2013,593:160-164.

[7]KongJiangxu,ZhangLianzhu,WangWeifan.Structuralpropertiesandsurvivingrateofplanargraphs[J].DiscreteMathAlgorithmsAppl,2014,6(4):1450052-1450074.

[8]WangWeifan,FinbowS,WangPing.Alowerboundofthesurvivingrateofaplanargraphwithgirthatleastseven[J].JCombOptim,2012,27(4):621-642.

[9]WangWeifan,FinbowS,KongJiangxu.The2-survivingrateofplanargraphswithout6-cycles[J].TheoretComputSci,2014,518:22-31.

[10]WangW,KongJ,ZhangL.The2-survivingrateofplanargraphswithout4-cycles[J].TheoretComputSci,2012,457(457):158-165.

[11]KongJiangxu,ZhangLianzhu,WangWeifan.Thesurvivingrateofdigraphs[J].DiscreteMath,2014,334(6):13-19.

(責任編輯陶立方)

The surviving rate of some oriented planar graphs

WANG Weifan,QIU Xiashuang,HUANG Danjun

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

firefighter problem; surviving rate; digraph; planar graph

10.16218/j.issn.1001-5051.2016.03.001

收文日期：2016-03-23；2016-04-06

國家自然科學基金資助項目(11371328)

王維凡(1955-)，男，遼寧沈陽人，教授，博導.研究方向：圖論與組合優化.

O157.5

A

1001-5051(2016)03-0241-05