強(qiáng)正則圖與完全圖字典積的平均首達(dá)時(shí)間及其應(yīng)用

倪湘鈞，徐 慧，潘向峰

（安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230601）

平均首達(dá)時(shí)間是有限馬爾可夫鏈中的一個(gè)重要參數(shù)，廣泛應(yīng)用于物理、化學(xué)、統(tǒng)計(jì)學(xué)上。國(guó)內(nèi)外學(xué)者致力于尋找平均首達(dá)時(shí)間的簡(jiǎn)約表達(dá)式與數(shù)值計(jì)算。陳海燕等[1]給出了強(qiáng)正則圖及其與帶自環(huán)的完全圖、完全圖等經(jīng)過(guò)二元運(yùn)算（弱直積、直積、卡氏積）后所得到圖的平均首達(dá)時(shí)間表達(dá)式和對(duì)于賦權(quán)有向圖上的隨機(jī)游走，利用最小多項(xiàng)式刻畫(huà)了任意兩頂點(diǎn)間的平均首達(dá)時(shí)間計(jì)算公式。文獻(xiàn)[2]給出了強(qiáng)正則圖的特征值與其對(duì)應(yīng)重?cái)?shù)的完整信息。王志俊等[3]刻畫(huà)了連通圖G與正則圖H作字典積對(duì)應(yīng)的譜。文獻(xiàn)[4]給出了正則圖最小多項(xiàng)式與其特征值重?cái)?shù)之間的關(guān)系。受到上述文獻(xiàn)的啟發(fā)，本文考慮強(qiáng)正則圖與完全圖字典積的平均首達(dá)時(shí)間表達(dá)式及其應(yīng)用，且本文只考慮簡(jiǎn)單的無(wú)向連通圖，所涉及的其他圖論術(shù)語(yǔ)可參見(jiàn)文獻(xiàn)[5]。

1 預(yù)備知識(shí)

定義1 設(shè)G=(V,E)是一個(gè)階為d的k正則圖，若G滿足任意兩個(gè)相鄰頂點(diǎn)的公共鄰點(diǎn)個(gè)數(shù)為λ，任意兩個(gè)不相鄰頂點(diǎn)的公共鄰點(diǎn)個(gè)數(shù)為μ，其中λ，μ(μ＞1)是常數(shù)，則稱之為具有參數(shù)(d,k,λ,μ)的強(qiáng)正則圖。

這里Aij(2)表示A2的ij元素。

命題[7]設(shè)H是m階完全圖，其鄰接矩陣特征值為-1，m-1，對(duì)應(yīng)重?cái)?shù)分別為m-1，1。

定義2圖G和圖H的字典積G[H]指頂點(diǎn)集為V(G)×V(H)的簡(jiǎn)單圖，其中(u,v)與(u′,v′)相鄰當(dāng)且僅當(dāng)uu′∈E(G)，或者u=u′且vv′∈E(H)。

下面利用圖G和正則圖H的特征值來(lái)表示其字典積G[H]的特征值。

定理1[3]設(shè)圖G的特征值為λ1,λ2,λ3,…,λn(λ1≥λ2≥λ3≥…≥λn)，正則圖H的特征值為μ1,μ2,μ3,…,μm(μ1≥μ2≥μ3≥…≥μm)，則相應(yīng)字典積圖G[H]的特征值為λ1m+μ1,λ2m+μ1,λ3m+μ1,…,λn m+μ1,μ2,μ3,…,μm，且μ2,μ3,…,μm的重?cái)?shù)均為n。

圖1 字典積圖G1[H1]

定理2[1]設(shè)P是圖G上隨機(jī)游走的概率轉(zhuǎn)移矩陣，若多項(xiàng)式f(x)=xn+a1xn-1+a2xn-2+…+an-1x+an，滿足f(1)≠0且f(P)是一個(gè)具有相同行向量的矩陣，那么對(duì)于任意i,j∈V，有

其中，πj是圖G上隨機(jī)游走的平穩(wěn)分布π的第j個(gè)分量。

因?yàn)镻是概率轉(zhuǎn)移矩陣，即非負(fù)不可約的隨機(jī)矩陣，所以1是P重?cái)?shù)為1的最大特征值。由文獻(xiàn)[1]可知P的最小多項(xiàng)式q(x)=(x-1)f(x)，故只需研究P的最小多項(xiàng)式即可得到滿足具有相同行向量的矩陣f(P)且f(1)≠0的f(x)，進(jìn)一步研究平均首達(dá)時(shí)間。

定理4[9]設(shè)G是一個(gè)具有m條邊n個(gè)點(diǎn)的連通圖，則Kf*(G)=2mKe(G)。

現(xiàn)利用強(qiáng)正則圖與完全圖字典積中任意兩點(diǎn)的平均首達(dá)時(shí)間來(lái)表示圖中任意兩點(diǎn)間的電阻距離。

定理5[9]設(shè)G是一個(gè)具有m條邊的連通圖，則對(duì)任意i,j∈VG，有EiTj(G)+EjTi(G)=2mrij(G)。

2 主要結(jié)果

下面給出強(qiáng)正則圖與完全圖字典積中任意兩點(diǎn)間的平均首達(dá)時(shí)間。設(shè)G是一個(gè)具有參數(shù)(d,k,λ,μ)的強(qiáng)正則圖，A為G的鄰接矩陣。設(shè)H是m階完全圖，則G[H]是一個(gè)階為dm的m+mk-1正則連通圖。由文獻(xiàn)[3]知，G[H]的鄰接矩陣為A(G[H])=A(G)?J+I?A(H)，這里?表示張量積，J表示全1矩陣。由定理1可知，G[H]只有4個(gè)不同的特征值：m+mk-1，m+mr-1，m+ms-1，-1。它的最小多項(xiàng)式[4]為

因?yàn)镠是m階完全圖，所以對(duì)于?v1,v2∈V(H)，它們均是鄰接的，故只需對(duì)u1，u2的情況進(jìn)行分類討論。利用定理2，可以得到以下結(jié)論。

定理6對(duì)于G[H]上的簡(jiǎn)單隨機(jī)游走，對(duì)?i=u1v1，j=u2v2∈V(G[H])，有

接下來(lái)，根據(jù)字典積圖G[H]和圖G特征值之間的關(guān)系，計(jì)算一些與G[H]有關(guān)的圖不變量，給出G[H]的度積基爾霍夫指數(shù)和凱梅尼常數(shù)的公式。此外，基于G[H]任意兩個(gè)頂點(diǎn)之間的平均首達(dá)時(shí)間，建立G[H]上任意兩個(gè)頂點(diǎn)之間的電阻距離。這些圖不變量均由圖G和圖H的參數(shù)和相關(guān)不變量決定。對(duì)于度積基爾霍夫指數(shù)，文獻(xiàn)[8]給出了它與N(G)特征值之間的良好關(guān)系。

3 結(jié)束語(yǔ)

近年來(lái)，有限圖上的隨機(jī)游走在近似算法設(shè)計(jì)上的應(yīng)用受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，算法的相關(guān)性能又與隨機(jī)游走上的平均首達(dá)時(shí)間、通勤時(shí)間等緊密相關(guān)。通過(guò)研究文獻(xiàn)[1]中關(guān)于強(qiáng)連通非周期有向圖上隨機(jī)游走平均首達(dá)時(shí)間的新表達(dá)式，結(jié)合文獻(xiàn)[4]中兩圖的譜與二者字典積圖的譜的關(guān)系，本文得到強(qiáng)正則圖與完全圖字典積的譜與鄰接矩陣，再利用代數(shù)方法進(jìn)一步研究對(duì)應(yīng)字典積圖上任意兩點(diǎn)間的平均首達(dá)時(shí)間、電阻距離、度積基爾霍夫指數(shù)和凱梅尼常數(shù)。另外，隨機(jī)游走與電網(wǎng)絡(luò)之間有著緊密的聯(lián)系，這也是今后研究的重點(diǎn)方向。