主題
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

參見

冷卻數, 滲流

使用 探索

參考文獻

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. "燃燒數。" 來自 Web 資源。 https://mathworld.tw/BurningNumber.html

主題分類