平面图的存活率

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:a24287490
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
设G是含有n≥2个顶点和m≥1条边的连通图,正整数k≥1.假设火在图G的某一个顶点v处开始燃烧,消防员选择一些顶点开始保护.在每一步中,消防员选择k个未燃烧的顶点进行保护,然后,火向已燃烧顶点的邻点(未被保护的)蔓延.设snk(v)表示当v为火源时,整个防火过程中消防员最多可救下的顶点数.可救下的顶点的平均比率称为G的k-存活率,记为ρk(G),即ρk(G)=∑v∈v(G)snk(v)/n2.  假设火在图G的某一条边uv的两个端点(相邻的两个顶点)处开始燃烧,消防员选择G中的一些顶点开始保护.在第一步中,消防员选择k个未燃烧的顶点进行保护,在接下去的每一步中,消防员选择l个未燃烧的顶点进行保护.在每一步的最后,火向已燃烧顶点的邻点(未被保护的)蔓延.依次下去,火和消防员交替地在图G上移动.当火无法再蔓延时,整个防火过程结束.设sn(k,l)(uv)表示当uv为火源时,整个防火过程中消防员最多可以救下的顶点数.图G的(k,l)-边存活率,ρ(k,l)(G)定义为ρ(k,l)(G)=∑uv∈E(G) sn(k,l)(uv)/nm.  本论文主要研究了平面图的存活率和边存活率,共分为三章.  第一章介绍图的一些基本概念,简述存活率的部分研究结果,并给出了本文的主要结果.  第二章研究平面图的2-存活率,证明了下面一些结果:  (1)无5-圈平面图的2-存活率ρ2(G)>1/363;  (2)无7-圈平面图的2-存活率ρ2(G)>1/783;  (3)无6-圈平面图的2-存活率ρ2(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.
其他文献
设C是一个范畴,T是C中的单子(monad).本文将范畴C中代数和余代数的一些命题和结论推广到单子和余单子(comonad)上,得到一些有意义的结论.全文共分为五章. 第一章主要介绍单子与
本文主要证明了所有非次正规子群形成一个共轭类的群的一些性质. 定理2.2.若有限群G只含两个非次正规子群共轭类H=H,H,…,H和K=K,K,…,K,则G有下列性质: (1)至少有一个非次正规
论文分为三部分.第一部分讨论了度量空间中相容映象和非相容映象对的一些公共不动点问题;第二部分讨论了拓扑空间中(φ)-压缩映象的公共不动点问题;第三部分讨论了Banach空间
设图G=(V,E)是一个没有孤立点的无向简单图.如果V的一个非空子集D满足VD中的每个顶点都有一个邻点在D中,则称D是图G的一个控制集.进一步,如果D是图G的一个控制集并且由D导出的