图的存活率

论文摘要

设G为顶点数至少为2的连通图.如果火随机地在图G的某一个顶点v处开始燃烧,则防火员从没有燃烧的顶点中选择k个进行防护,其中k≥ 1且k为正整数.只要某个顶点被防火员救下,那么在整个防火过程中该顶点就不会着火,也就是说该顶点是安全的.在防火员移动救下图G的顶点之后,火蔓延到v的其它（未被保护且没有燃烧）的邻点.消防员和火在图G上依次交替移动.直到火无法继续在图G上蔓延时,整个防火过程就结束了.用snk（v）表示当火在点v处燃烧时,k个消防员最多能保护的顶点数.将图G的k-存活率定义为当图G的任意一个顶点开始起火时,防火员可以救下的最多的顶点数的平均比例,记为ρk（G）,它的计算公式为ρk（G）=（?）snk（v）/n2.设D为有向图,且v∈V（D）.若火在v点处燃起,那么从没有燃烧的顶点中防火员选择一些进行保护.之后,通过弧的方向火蔓延到已着火的顶点的其他邻点.如此反复下去,防火员和火在有向图上依次进行移动.同样地,我们仍可以用snk（v）表示某个顶点v着火时的存活数.那么,有向图D的k-存活率用公式表示为ρk（D）=（?）snk（v）/n2.本学位论文主要研究了平面图的存活率,IC-图的存活率和1-平面有向图的存活率,共分为三章.在第一章中,我们交代了图的存活率的相关研究背景以及一些基本概念,简要的概述了图的存活率的一些现有的研究成果,另外还给出了本文的研究结果.在第二章中,我们研究了平面图G的2-存活率,证明了:（1）不含7-圈和8-圈的平面图G的2-存活率ρ2（G）>1/291.在第三章中,我们研究了 IC-图的5-存活率,证明了:（2）IC-图G的5-存活率ρ5（G）>1/10.在第四章中,我们研究了 1-平面有向图的3-存活率,证明了:（3）1-平面图G的一个定向G的3-存活率ρ3（G）>1/65.

论文目录

文章来源

类型: 硕士论文

作者: 包沈潇

导师: 王维凡

关键词: 防火问题,存活率,平面图,平面有向图

来源: 浙江师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 浙江师范大学

分类号: O157.5

DOI: 10.27464/d.cnki.gzsfu.2019.000775

总页数: 54

文件大小: 2967K

下载量: 15

相关论文文献

• [1].基于加权有向图的中医量化诊断方法研究[J]. 中华中医药杂志 2020(04)
• [2].超欧拉和双有向迹的强积有向图[J]. 四川师范大学学报(自然科学版) 2018(04)
• [3].有向图是极大连通的和超连通的充分条件（英文）[J]. 中国科学技术大学学报 2018(08)
• [4].局部内(外)半完全有向图可迹的充分条件[J]. 应用数学学报 2016(02)
• [5].圆有向图中的泛弧[J]. 贵州师范大学学报(自然科学版) 2017(01)
• [6].基于有向图相似的应急响应程序模块化问题研究[J]. 中国管理科学 2017(04)
• [7].关于超欧拉的幂有向图[J]. 廊坊师范学院学报(自然科学版) 2017(03)
• [8].超欧拉路可合并有向图及半完全有向图（英文）[J]. 新疆师范大学学报(自然科学版) 2017(03)
• [9].圆有向图的(1,2)步竞争图中存在哈密尔顿圈的条件[J]. 重庆工商大学学报(自然科学版) 2017(06)
• [10].圆有向图的(i,κ)步竞争图[J]. 应用数学学报 2013(06)
• [11].数据中心高压冷水机组定性故障诊断模型构建[J]. 制冷与空调(四川) 2020(01)
• [12].一种高效的面向动态有向图的增量强连通分量算法[J]. 中国科学:信息科学 2019(08)
• [13].循环有向图的距离和与平均距离[J]. 山西师范大学学报(自然科学版) 2014(01)
• [14].关于强哈密尔顿连通有向图的一个反例[J]. 山西大学学报(自然科学版) 2012(01)
• [15].有向图极大与超级局部边连通性的依赖团数的度序列条件[J]. 山东科学 2012(04)
• [16].本原不可幂几乎可约定号有向图的k重下广义基[J]. 中北大学学报(自然科学版) 2012(06)
• [17].一种有向图最长路的算法、灵敏度分析及其应用[J]. 科学技术与工程 2011(16)
• [18].强哈密尔顿连通有向图的一个注记[J]. 数学的实践与认识 2010(14)
• [19].具有最小弧数的唯一泛圈有向图的计数[J]. 数学的实践与认识 2009(04)
• [20].极小强连通有向图[J]. 厦门大学学报(自然科学版) 2009(05)
• [21].扩张的局部内(外)半完全有向图的可迹性[J]. 中北大学学报(自然科学版) 2008(05)
• [22].图论中有向图的矩阵方法[J]. 榆林学院学报 2018(06)
• [23].基于修正赋权有向图功能结构的可变功能机械建模方法[J]. 机械制造 2016(01)
• [24].有向图中爪的一个重要性质[J]. 长春工业大学学报 2015(03)
• [25].平衡半传递有向图的弧连通性(英文)[J]. 新疆大学学报(自然科学版) 2014(01)
• [26].存在至少2个非临界点的强连通有向图[J]. 山西大学学报(自然科学版) 2013(02)
• [27].一类双色有向图的本原指数集[J]. 数学的实践与认识 2012(24)
• [28].一种有向图的特殊搜索算法及其实现[J]. 福建工程学院学报 2011(01)
• [29].赋权有向图的最小生成树算法[J]. 计算机工程 2010(02)
• [30].途径正则有向图的途径正则不变性[J]. 河北师范大学学报(自然科学版) 2010(03)

标签：防火问题论文;  存活率论文;  平面图论文;  平面有向图论文;