一类定向平面图的存活率
2016-09-29王维凡裘霞霜黄丹君
王维凡, 裘霞霜, 黄丹君
(浙江师范大学 数理与信息工程学院,浙江 金华 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