圖的積的廣義燃燒數(shù)

劉佩佩 何志紅

摘 要：圖的燃燒數(shù)是指在圖的燃燒過程中所需要的最少時間數(shù)。2021年，李銀奎等人提出圖的廣義燃燒數(shù)。圖G的廣義燃燒數(shù)br（G）是指圖的廣義燃燒過程需要的最少時間數(shù)。本文解決了完全k叉樹的廣義燃燒數(shù)的一般性結(jié)果，并部分解決了字典積和笛卡爾積的廣義燃燒數(shù)問題。

關(guān)鍵詞：燃燒數(shù);廣義燃燒數(shù);完全k叉樹;字典積;笛卡爾積;強積

中圖分類號：O157.5 ?文獻標識碼：A ?文章編號：1673-260X（2022）01-0001-04

1 引言

圖的燃燒最早由BONATO等人[1]提出。在社交網(wǎng)絡中，一個人得到信息后，下一步會傳遞給他的朋友，而消息會隨著時間的推移而繼續(xù)傳播。如果要考慮信息傳播到整個網(wǎng)絡所需的最少時間，那么可以轉(zhuǎn)化成圖論問題來解決，也就是將信息在社會網(wǎng)絡中的傳播過程轉(zhuǎn)化成圖的燃燒過程。圖的燃燒是在簡單圖G的點集上定義的一個離散時間的圖過程。具體如下：在燃燒過程中，每個頂點要么被燃燒，要么未被燃燒。在初始時間t=0時，所有頂點未被燃燒。在時間t≥1時，每個時間選擇一個未被燃燒的頂點進行燃燒。一旦某個頂點在時間t被燃燒，則在時間t+1，它的所有鄰點都會自動被燃燒。如果一個頂點v被燃燒，則v保持燃燒狀態(tài)直到G的燃燒過程結(jié)束。當所有頂點全部被燃燒時，燃燒過程結(jié)束。G的燃燒數(shù)記作b（G），它表示G的燃燒過程結(jié)束所需要的最少時間數(shù)。

然而，在現(xiàn)實生活中，當一個人只從一個渠道接收到某個信息時，他可能不會立即傳播，因為他不確定信息的真實性。但當他從幾個來源收到這個信息時，會增加對信息的識別，然后他才會將信息傳播給他的朋友。……