平面图的存活率

发布时间：2017-07-14 02:21

  本文关键词：平面图的存活率

  更多相关文章： 防火问题 存活率 边存活率 圈 平面图

【摘要】：设G是含有n≥2个顶点和m≥1条边的连通图,正整数k≥1.假设火在图G的某一个顶点v处开始燃烧,消防员选择一些顶点开始保护.在每一步中,消防员选择k个未燃烧的顶点进行保护,然后,火向已燃烧顶点的邻点(未被保护的)蔓延.设snk(v)表示当v为火源时,整个防火过程中消防员最多可救下的顶点数.可救下的顶点的平均比率称为G的j-存活率,记为ρk(G),即假设火在图G的某一条边uv的两个端点(相邻的两个顶点)处开始燃烧,消防员选择G中的一些顶点开始保护.在第一步中,消防员选择k个未燃烧的顶点进行保护,在接下去的每一步中,消防员选择l个未燃烧的顶点进行保护.在每一步的最后,火向已燃烧顶点的邻点(未被保护的)蔓延.依次下去,火和消防员交替地在图G上移动.当火无法再蔓延时,整个防火过程结束.设sn'(k,l)(uv)表示当uv为火源时,整个防火过程中消防员最多可以救下的顶点数.图G的(k,l)-边存活率,ρ(k,l)'(G)定义为本论文主要研究了平面图的存活率和边存活率,共分为三章.第一章介绍图的一些基本概念,简述存活率的部分研究结果,并给出了本文的主要结果.第二章研究平面图的2-存活率,证明了下面一些结果：(1)无5-圈平面图的2-存活率ρ2(G)1/363；(2)无7-圈平面图的2-存活率ρ2(G)1/783；(3)无6-圈平面图的2-存活率p2(G)1/41.第三章研究平面图的边存活率,设G是最小度δ(G)≥3的平面图,证明了下面一些结果：(1)ρ'(5,2)(G)11/3753；(2)若G不含3-圈,则ρ'(4,2)(G)≥1/24;(3)若G不含3,4-圈,则ρ'(3,2)(G)≥1/6.
【关键词】：防火问题 存活率 边存活率 圈 平面图
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O157.5
【目录】：

• 摘要3-5
• ABSTRACT5-8
• 1 绪论8-14
• 1.1 研究背景8-12
• 1.2 基本概念12-14
• 2 平面图的2-存活率14-51
• 2.1 预备引理14-18
• 2.2 无5-圈平面图的2-存活率18-26
• 2.3 无7-圈平面图的2-存活率26-39
• 2.4 无6-圈平面图的2-存活率39-51
• 3 平面图的边存活率51-61
• 3.1 预备引理51-53
• 3.2 平面图的(5,2)-边存活率53-58
• 3.3 无3-圈平面图的(4,2)-边存活率58-59
• 3.4 无3,4-圈平面图的(3,2)-边存活率59-61
• 参考文献61-64
• 在学期间的研究成果及发表的论文64-65
• 致谢65-67
• 浙江师范大学学位论文诚信承诺书67

【相似文献】

中国期刊全文数据库 前10条

1 石琳;;调和平衡图直径与顶点数的关系[J];内蒙古大学学报(自然科学版);1992年01期

2 蔡茂诚;图的路连通问题[J];曲阜师范大学学报(自然科学版);1994年03期

3 施永兵;关于UC图[J];自然杂志;1984年12期

4 郭玉端;关于顶点子集凝聚度的若干定理(续)[J];福州大学学报(自然科学版);1992年02期

5 郑汉鼎;树的序列表示法及其在数树上的应用[J];科学通报;1981年20期

6 李萃萃;;波兰表达式构成图及顶点数的探讨[J];韶关学院学报;2010年12期

7 苏凤婷;唐高华;黄立强;;树图中进攻性联盟的顶点数上界[J];广西科学;2008年04期

8 王应前;K方图的若干性质[J];安庆师范学院学报(自然科学版);1996年04期

9 刘象武,何宇新;两类满足A(H)=3的图[J];数学杂志;1989年04期

10 赖在抗;;L—幂和树的一类全序子集[J];新疆大学学报(自然科学版);1982年02期

中国博士学位论文全文数据库 前1条

1 焦继业;低功耗高性能移动图形顶点处理器设计关键技术研究[D];西安电子科技大学;2013年

中国硕士学位论文全文数据库 前4条

1 丁鑫;基于BSP模型的分布式图计算系统性能优化研究[D];复旦大学;2014年

2 伍婷婷;平面图的存活率[D];浙江师范大学;2015年

3 屠九如;树的密度与平均顶点数[D];上海交通大学;2013年

4 赵福生;基于Web服务的路径计算实用算法的设计与实现[D];华东师范大学;2012年

，

本文编号：539325