平面 4 · 82 格子图的消防员问题

消防员问题 (Firefighter Problem) 是一个离散的动态传播模型,与疫情控制、谣言传播、森林防火等实际问题密切相关,它最早是由著名计算机理论学家 Hartnell 在 1995 年的第 25 届组合数学与计算大会上首次提出的。令 G = (V (G), E(G)) 是 n (n ≥ 2) 个顶点的连通图。假设火在图 G 中任意一个顶点 v 处燃起,消防员则选择未着火的顶点去保护(一旦某个顶点被保护,则在整个过程中都将处千被保护状态),然后火蔓延到 v 的未加保护且没着火的邻点。依次下去,火和消防员交替地在图 G 上移动, 直到火不能继续蔓延,整个过程结束,消防员的任务是使最后获救的点数最多。令 sn(v) 表示当图 G 中的顶点 v 作为火源点时一个消防员所能保护的最多顶点数。图 G 的存活率 ρ(G) 定义为 ,即当火随机地在图 G 的一个顶点燃起时,一个消防员最多能保护的顶点数的平均值。本文首先研究有限平面 4 ·82 格子图的存活率,分析格子图中点存活数的变化出有限 4 ·82 格子图的存活率的确切值;从而证明了对于无限平面 4 ·82 格子图, 每个回合使用一个消防员经过有限次保护后可以控制火的蔓延。

图的L(2,1)标号与移动通讯频率分配问题

图G的L(2,1)标号是一个从顶点集V(G)到非负整数集的函数f(x),使得若d(x,y)=1,则|f(x)-f(y)|≥2;若d(x,y)=2,则|f(x)-f(y)|≥1.移动通讯频率分配问题可以转化为图的L(2,1)标号问题.本文首先给出平面格子图的L(2,1)标号,然后通过平面格子图及相关图的L(2,1)标号得到平面近正六边形剖分图的L(2,1)面标号,从而解决了移动通讯的频率分配问题.

几类乘积图的均匀着色

考虑了几类乘积图的均匀着色数，证明了这几类乘积图可均匀k-着色(k≥2或3)。

图的L(2,1)-标号与移动通讯频率分配问题

移动通讯频率分配问题可以转化为图的L(2,1)-标号问题。平面格子图、三角格子图在移动通讯上起着重要的作用。该文通过对平面格子图、三角格子图的结构进行分析来研究这两类图类的L(2,1)-标号问题。首先研究了参考文献[1]中的一个错误结果,并精确刻划了上述两类图的L(2,1)-标号的边跨距及λ-L(2,1)-标号的边跨距,从而全面地解决了平面格子图、三角格子图上的移动通讯频率分配问题。

二维带宽的浓度下界（英）

二维带宽的浓度下界（英）林诒勋二维带宽的浓度下界（英）@林诒勋...