不含5-圈平面图的边存活率

2021-01-28 16:14:20郭文婷孔将旭
中国计量大学学报 2020年4期
关键词:关联

郭文婷,孔将旭

(中国计量大学 理学院,浙江 杭州 310018)

1995年,Hartnell[1]首次提出了消防员问题(Firefighter Problem)。设G是一个连通图,k是正整数。假设火在图G的一个顶点或多个点燃起,消防员每步选择k个没有着火的顶点加以防护,然后火蔓延到其未被保护且没有着火的邻点,火和消防员在图G上交替移动。当火没法再传播时,整个过程结束。

为了研究一个图的整体防火能力,蔡雷震和王维凡[2]首先提出了图的存活率的概念。设G是n阶连通图,snk(v)表示当v为火源点时,k个消防员最多能防护的顶点个数。当火等概率的在图G的一个顶点燃起时,k个消防员最多能保护的顶点数的期望称为图G的k-存活率,记为ρk(G),即

显然,0<ρk(G)<1,且对任意i>j,有ρi(G)≥ρj(G)成立。关于存活率和消防员问题的最新研究进展,请参阅王维凡和孔将旭的综述文献[3]。

1 几个预备引理设

G是简单平面图,我们用V(G),E(G),F(G),Δ(G)和δ(G)分别表示图G的顶点集、边集、面集,最大度和最小度。对v∈V(G),N(v)={u|uv∈E(G)},点v的度数d(v)=|N(v)|。对f∈F(G),用b(f)表示围成面f的周界,d(f)表示围成面f的周界的边数,称为f的度。一个度为k,至少为k或至多为k的点(面)分别称为k-点,k+-点或k--点(k-面,k+-面或k--面)。对于一条边uv,如果u是i-点,v是j-点,那么uv边称为(i,j)-边,并且用f1和f2表示与uv相关联的两个面,当uv是割边时,f1=f2。对于一个3-面[uvw],如果u是i-点,v是j-点,w是k-点,那么[uvw]面称为(i,j,k)-面。

引理1[8](平面图分离定理)设G是一个极大平面图,|V(G)|=n,T是G的任意一棵支撑树,则存在一条边e∈E(G)E(T)使得T+e中的唯一一个圈C满足圈内和圈外的点数都小于(2n)/3。

引理2[6]设G是平面图,T是G的任意一棵以r为根点的支撑树,则T中存在一条以x,y为端点的路P(xy),使得圈C=P(xy)+{xy}(xy可以不是G中的边,x,y≠r)满足圈内和圈外的点数都小于(2n)/3。……

登录APP查看全文

猜你喜欢
关联
不惧于新,不困于形——一道函数“关联”题的剖析与拓展
“苦”的关联
当代陕西(2021年17期)2021-11-06 03:21:36
船山与宋学关联的再探讨
原道(2020年2期)2020-12-21 05:47:06
“一带一路”递进,关联民生更紧
当代陕西(2019年15期)2019-09-02 01:52:00
新制度关联、组织控制与社会组织的倡导行为
奇趣搭配
基于广义关联聚类图的分层关联多目标跟踪
自动化学报(2017年1期)2017-03-11 17:31:17
智趣
读者(2017年5期)2017-02-15 18:04:18
探讨藏医学与因明学之间的关联
西藏科技(2016年5期)2016-09-26 12:16:39
GPS异常监测数据的关联负选择分步识别算法