一类平面图消防员问题的边存活率

设G是一个有n个点m条边的连通图.假设火在图G的一条边uv的两个端点燃起,消防员保护若干个没有着火的顶点,火接着蔓延到其他未保护且没有着火的邻点,火和消防员交替地在图G上移动.设sn(G,uv;(k1,k2))表示当火在边uv的两个端点燃起时,消防员采取第一步保护k1个点,后面每步保护k2个点的策略所能救下的最大顶点数.定义图G的边存活率ρ(G,e;(k1,k2))=∑uv∈E(G)sn(G,uv;(k1,k2))/nm,即当火随机地在图G的一条边的两个端点燃起时,消防员最多能救下的顶点数的平均率.本文证明了如果G是一个至少有3个点且最小度至少为3的不含4-圈连通平面图,那么ρ(G,e;(4,2))>7/705.

一类稀疏图的边存活率

目的:研究最小度为2且平均度有界的连通图的边存活率。方法:利用图染色理论中的经典方法权转移进行推导证明。结果:得到了如果G是一个有n个点m条边且最小度为2的连通图,满足m≤(6/5-ε)n,其中0<ε≤1/5,那么图G的边存活率ρ′(G)>5ε/6-5ε。并由此推得如果G是一个最小度为2且围长至少为13的连通平面图,那么图G的边存活率ρ′(G)>1/65。结论:若图G是一个最小度为2且平均度小于2.4的连通图,当火随机地在图G的任意两个相邻的顶点燃起时,1个消防员最多能保护的顶点数的平均值为正。

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

目的:主要研究最小度至少为3且不含5-圈的连通平面图的(4,2)-边存活率。方法:主要利用平面图分离定理和图染色理论中的经典方法权转移进行推导证明。结果:得到了如果G是最小度至少为3的不含5-圈的连通平面图,那么图G的(4,2)-边存活率至少为1/62。结论:当火随机的在最小度至少为3且不含5-圈的连通平面图G的两个相邻顶点燃起时,消防员采取第一步保护4个点,后面每一步保护2个点的防火策略,使得最后获救的顶点数的平均值至少为图G顶点数的1/62。

凯莱图上的消防员问题

令 G 是 n 个顶点的连通图。假设火在图 G 的某一点 u 处燃起,消防员选择一个未着火的顶点进行保护(一旦某个顶点被保护,则在整个过程中都将处千被保护状态),然后火蔓延到 u 的未加保护且没着火的邻点。依次下去,火和消防员交替地在图 G 上移动,直到火不能继续蔓延,整个过程结束。本文主要讨论了模 n 剩余类加群 Zn 在 k(k ≥ 2) 元逆闭子集的凯莱图上的消防员问题。首先考虑了凯莱图在二元逆闭子集上的消防员问题,这部分确定了凯莱图的结构并且提出了结构算法和该算法的 matlab 语言;其次研究了凯莱图在三元逆闭子集上的消防员问题, 这部分也确定了凯莱图的结构,并且考虑了点存活率,边存活率以及 MV S 问题;最后研究了凯莱图在大千三元逆闭子集上的消防员问题,这部分以点的标号顺序画出了凯莱图,按逆闭子集的阶数把凯莱图并分为两类,并考虑了凯莱图的任意一个顶点着火时,一个消防员能控制火的充要条件。