主题
Search

冷却数

下载 Mathematica 笔记本下载 Wolfram 笔记本

给定一个有限、简单、无向图 G，定义冷却为一个离散时间过程，其中所有节点最初都未冷却。在随后的每个步骤中，如果存在这样的节点，则选择一个新的未冷却节点（称为源）进行冷却。如果一个节点被冷却，那么它将保持该状态直到过程结束。一旦一个节点被冷却，其未冷却的邻居将在下一步中被冷却。当 G 的所有节点都被冷却时，过程终止，G 的冷却数 CL(G) 定义为冷却过程结束的最大步骤数 (Bonato et al. 2024)。

图的冷却数衡量图中缓慢移动的传染病的速度，冷却数越低，传染病传播得越快 (Bonato et al. 2024)。因此，与图的燃烧数（给出燃烧所有节点的最小轮数）相反，冷却数给出冷却所有节点的最大轮数。

Cooling

上面的图示说明了路径图 P_4（其中 CL(P_4)=3）和完全二部图 K_(2,3)（其中 CL(K_(2,3))=3）。

根据定义，冷却数满足

b(G)<=CL(G),
(1)

其中 b(G) 是燃烧数。这是因为燃烧数对应于首次出现完全燃烧图的第一次迭代，而冷却数对应于没有部分未冷却图剩余的迭代。

冷却数的上界为

CL(G)<=[(n+1)/2]
(2)

下界和上界分别为

[(diam(G)+2)/2]<=CL(G)<=diam(G)+1,
(3)

其中 diam(G) 是图直径 (Bonato et al. 2024)。

下表总结了一些参数化图族的冷却数值，其中 [n] 表示向上取整函数。

图族CL
完全图 K_n{1 for n=1; 2 otherwise
圈图 C_n[(n+2)/3]
空图 K^__nn
路径图 P_n[(n+1)/2]
星图 S_n{1 for n=1; 2 otherwise
轮图 W_n2

另请参阅

燃烧数

使用 探索

参考文献

Bonato, A.; Marbach, T. G.; Milne, H.; and Mishura, T. "How to Cool a Graph." https://arxiv.org/abs/2401.03496. 7 Jan 2024.

请引用为

Weisstein, Eric W. "冷却数。" 来自 Web 资源。 https://mathworld.net.cn/CoolingNumber.html

学科分类