一类定向平面图的存活率

王维凡,　裘霞霜,　黄丹君

(浙江师范大学 数理与信息工程学院,浙江 金华　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