主题
Search

燃烧数

下载 Mathematica Notebook下载 Wolfram Notebook

Bonato 等人 (2014, 2015) 如下定义了有限、简单、无向图的燃烧数。考虑一个称为燃烧的过程，该过程涉及离散时间步。每个节点要么被燃烧，要么未被燃烧；如果一个节点被燃烧，那么它将保持该状态直到过程结束。在每一轮中，选择一个额外的未燃烧节点进行燃烧（如果存在这样的节点）。一旦一个节点在第 t 轮被燃烧，在第 t+1 轮，其每个未燃烧的邻居都将被燃烧。当所有节点都被燃烧时，过程结束。图 G 的燃烧数，用 b(G) (Bonato 等人 2014) 或 bn(G) (Gautam 等人 2020) 表示，然后被定义为过程结束所需的最小轮数。

Burning

上述过程以路径图 path graph P_4 (其中 b(P_4)=2) 和完全二分图 complete bipartite graph K_(2,3) (其中 b(K_(2,3))=2) 为例进行了说明。

图燃烧问题的决策版本是 NP-完全 的 (Bessy 等人 2017)。在 非连通图上计算燃烧数比在 连通图上更难 (Gautam 等人 2021)。这是因为在非连通图中，您可以较早地在较大的连通分量中开始燃烧，并让这些火自行蔓延，同时在较小的分量上设置火。

通过构造，燃烧数满足

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

其中 CL(G) 是冷却数。这是因为燃烧数对应于完全燃烧的图首次出现的第一次迭代，而冷却数对应于不再存在部分未冷却图的迭代。

Bonato 等人 (2015) 证明了对于可追踪图 G，其顶点数为 n，

b(G)<=[sqrt(n)],
(2)

并且推测该不等式适用于任何连通图。Bonato (2020) 将此陈述称为“燃烧数猜想”，并将任何满足该不等式的图称为“良好可燃图”。已知的最佳上界由下式给出

b(G)<=[(-3+sqrt(24n+33))/4]
(3)

(Land 和 Lu 2016, Bonato 2020)。

对于任何图半径为 r 和图直径为 d 的连通图 G，

[sqrt(d+1)]<=b(G)<=r+1
(4)

(Bonato 2015, Bonato 2020)。

Bonato 等人 (2015) 表明对于 G^_，图 G 的补图，

4<=b(G)+b(G^_)<=n+2.
(5)

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

族b(n)
反棱柱图|_(sqrt(16n-1)+5)/4_|
鸡尾酒会图 K_(n×2)2
冠图 K_2 square K_n^_3
圈图 C_n[sqrt(n)]
空图 K^__nn
齿轮图3
舵图3
超立方体图 Q_n|_(n+3)/2_|
国王图 n×n1+|_n/2_|
梯子图 P_2 square P_n|_3/2+sqrt(n)_|
梯子阶图 nP_2n+1
莫比乌斯梯子 M_n|_3/2+sqrt(n)_|
奇图 O_nn
路径图 P_n[sqrt(n)]
棱柱图 P_2 square C_n|_3/2+sqrt(n)_|
车图 K_n square K_n3
星图 S_n{1 for n=1; 2 otherwise
太阳图3
环面网格图 C_n square C_n1+[n/2]
转置图 T_nn
轮图 W_n2

参见

冷却数, 渗流

使用 Wolfram|Alpha 探索

参考文献

Bessy, S.; Bonato, A.; Jansen, J.; Rautenbach, D.; and Roshanbin, E. "Bounds on the Burning Number." 2 Nov 2016. https://arxiv.org/abs/1511.06023.Bessy, S.; Bonato, A.; Jansen, J.; Rautenbach, D. R.; and Roshanbin, E. "Burning a Graph Is Hard." Disc. Appl. Math. 232, 73-87, 2017.Bonato, S. "A Survey of Graph Burning." 22 Sep 2020. https://arxiv.org/abs/2009.10642v1.Bonato, A.; Janssen, J.; and Roshanbin, E. "Burning a Graph as a Model of Social Contagion." In Algorithms and Models for the Web Graph: 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings (Ed. A. Bonato A., F. Graham F., and P. Prałat). Springer, pp. 13-22, 2014.Bonato, A.; Janssen, J.; and Roshanbin, E. "How to Burn a Graph." To appear in Internet Mathematics. 23 Jul 2015. https://arxiv.org/abs/1507.06524.Bonato, A.; Marbach, T. G.; Milne, H.; and Mishura, T. "How to Cool a Graph." https://arxiv.org/abs/2401.03496. 7 Jan 2024.Gautam, R. K.; Kare, A. S.; and Bhavani, S. D. "Faster Heuristics for Graph Burning." Appl. Intelligence 52, 1351-1361, 2021.Land, M. and Lu, L. "An Upper Bound on Burning Number of Graphs." In Proceedings of WAW'16. 2016.

请引用为

Weisstein, Eric W. "燃烧数。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/BurningNumber.html

主题分类