倪 琦，周 環(huán)，呂寧寧，潘向峰

(1.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,合肥 230601；2.安徽工業(yè)經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院公共教學(xué)部，合肥 230051)

平均首達(dá)時間是有限隨機(jī)游走的重要性質(zhì)參數(shù)之一,被廣泛用于各種網(wǎng)絡(luò)的動態(tài)研究,國內(nèi)外學(xué)者致力于研究其數(shù)值計算和理論表達(dá)式。[1]陳海燕[2]等通過多項式方法推導(dǎo)出了強(qiáng)連通非周期有向圖上隨機(jī)游走的平均首達(dá)時間的表達(dá)式,并利用這個新的公式給出了強(qiáng)正則圖與完全圖的二元運(yùn)算(弱直積、直積、卡氏積)生成圖上的平均首達(dá)時間。文獻(xiàn)[3]和[4]分別給出了Johnson 圖J(n,3)的特征值與相應(yīng)的特征重數(shù)。王志俊[5]等確定了圖G 與連通正則圖H 的字典積圖的特征多項式和鄰接譜。倪湘鈞[6]等研究了強(qiáng)正則圖與完全圖的字典積的平均首達(dá)時間。圖的字典積是一種二進(jìn)制運(yùn)算，它可以從舊圖生成新圖。與笛卡爾積和圖的強(qiáng)積等其他二元運(yùn)算不同,圖的字典積不滿足交換律,其特征多項式一般不能由兩個組成圖的特征多項式確定。[5]

受到上述文獻(xiàn)的啟發(fā),基于連通的強(qiáng)正則圖是直徑為2 的一類距離正則圖這一事實(shí),本文繼續(xù)深入研究直徑為3的一類距離正則圖Johnson圖J(n,3)與完全圖字典積的平均首達(dá)時間和電阻距離以及度積基爾霍夫指數(shù)、凱梅尼常數(shù)等圖不變量。文獻(xiàn)[7]闡述了基爾霍夫指數(shù)近年來的研究情況。這里只討論無向的簡單連通圖,如無特殊說明將遵循文獻(xiàn)[8]中的符號和術(shù)語。

1 預(yù)備知識

定義1[9]Johnson 圖J(n,m)定義如下:其中n是N元集合N={1,2,3,…,n}的元素個數(shù),頂點(diǎn)集V(J(n,m))由N 的m元子集構(gòu)成,顯然圖中有個點(diǎn),其中任意兩點(diǎn)相鄰當(dāng)且僅當(dāng)它們中僅有一個元素不同。易見J(n,m)是m(n-m)正則圖,其直徑為min(m,n-m)。例如,J(n,0)是一個單點(diǎn);J(n,1)是一個完全圖Kn;J(n,2)是三角形圖T(n),見圖1。

圖1 n=1和2時的Johnson圖

Johnson 圖J(n,3)的直徑為min(3,n-3)。本文主要研究Johnson 圖G=J(n,3)(n≥6)與完全圖字典積的平均首達(dá)時間,以下對J(n,3)不再指明n≥6。

如果讓d(x,y)表示兩個頂點(diǎn)x,y之間的距離,Δ(x,y)表示與x,y都相鄰的頂點(diǎn)數(shù)量,n2(x)是與點(diǎn)x距離為2的點(diǎn)y的數(shù)目,A(G)是G的鄰接矩陣,簡記為A,那么特征為n的Johnson圖G具有以下性質(zhì)[3，10]:

2)G是連通且正則的,正則度為3(n-3)；

3)n2(x)=(n-3)(n-4),?x∈V(G)；

4)A(G)的不同特征值是3(n-3),2n-9,n-7,-3,其特征重數(shù)分別為1,n-1,

5)如果d(x,y)=1,那么Δ(x,y)=n-2；

6)如果d(x,y)=2,那么Δ(x,y)=4。

由文獻(xiàn)[3]和[11]可知,矩陣A滿足等式即Hoffman多項式h(A)=J,即

其中：J是全1矩陣；I是單位矩陣。

因此

這里表示Ak的ij元素。

命題設(shè)H是m階完全圖,其鄰接矩陣特征值為m-1,-1,對應(yīng)重數(shù)分別為1,m-1。

定義2兩個圖G和H的字典積G[H]具有頂點(diǎn)集V(G)×V(H),其中(u1,v1)與(u2,v2)相鄰當(dāng)且僅當(dāng)u1和u2在G中相鄰,或u1=u2且v1和v2在H中相鄰。

定 理1[5]設(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,…,λnm+μ1,μ2,μ3,…,μm,且μ2,μ3,…,μm的重數(shù)等于n。

本文主要討論的是Johnson 圖J(n,3)與完全圖字典積的平均首達(dá)時間,利用定理1,G[H]僅有五個不同的鄰接譜:3mn-8m-1,2mn-8m-1,mn-6m-1,-2m-1,-1,且對應(yīng)重數(shù)[4]分別為1,n-1,。J(n,3) 的例子見圖2。

定理2[2]設(shè)G是一個強(qiáng)連通非周期有向圖,則G上隨機(jī)游走是不可約非周期的馬爾科夫鏈,P是概率轉(zhuǎn)移矩陣,存在多項式f(x)=xn+a1xn-1+a2xn-2+…+an-1x+an,其中f(1)≠0 且f(P)是一個行向量相同的矩陣,那么?i,j∈V(G),有

圖J(6,3)

其中：π是馬爾科夫鏈的平穩(wěn)分布；πj是其第j個分量。

由于P是圖上的概率轉(zhuǎn)移矩陣,即不可約非負(fù)的隨機(jī)矩陣,因而1是P的最大特征值,且重數(shù)為1,從而可得P的極小多項式為q(x)=(x-1)f(x),故研究滿足定理2條件的f(x)只需研究q(x),進(jìn)一步研究該字典積圖的平均首達(dá)時間。[6]

下面字典積圖G[H]中任意兩點(diǎn)的電阻距離可由任意兩點(diǎn)間的平均首達(dá)時間給出。

定理3[12]設(shè)G是連通圖,邊數(shù)為m,則對?i,j∈V(G),有

對于連通圖G,考慮N(G)=顯然它是實(shí)對稱矩陣,該連通圖的度積基爾霍夫指數(shù)可由N(G)的特征值表示,其中D(G)=diag(d1,d2,…,dn),A(G)是圖G的鄰接矩陣,其第i行第j列的元素為1當(dāng)且僅當(dāng)點(diǎn)i與點(diǎn)j相鄰,否則為0;di是頂點(diǎn)i在圖G中的度[6]。

定理4[13]設(shè)G是一個階數(shù)為n且邊數(shù)為m的連通圖,則Kf*(G)=其中λi表示N(G)的特征值,λ1≥λ2≥λ3≥…≥λn。

由于字典積G[H]為3mn-8m-1正則圖,故D(G[H])=diag(3mn-8m-1,3mn-8m-1,

…,3mn-8m-1),從而N(G[H])=A(G[H])。又 由A(G[H]) 的特征值可知N(G[H])的特征值為

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

定理6[15]設(shè)G是一個具有m條邊n個點(diǎn)的連通圖,則(1 -λk)=2mτ(G),其中λi是N(G)的特征值且滿足λ1≥λ2≥λ3≥…≥λn,τ(G)是G的生成樹數(shù)目。

2 主要結(jié)果

當(dāng)無向圖是連通且非二部的,我們也可以應(yīng)用定理2 來計算平均首達(dá)時間[2]。J(n,3)是一類Johnson圖,它是一種距離傳遞圖,具有多種良好的性質(zhì)。很顯然Johnson 圖J(n,3)(非二部)與完全圖的字典積上的簡單隨機(jī)游走是不可約非周期的馬爾科夫鏈,下面我們給出的J(n,3),都默認(rèn)它是非二部的。

下面給出Johnson 圖J(n,3)與完全圖的字典積中任意兩點(diǎn)間的平均首達(dá)時間。設(shè)G是特征為n的Johnson 圖J(n,3),A是G的鄰接矩陣。設(shè)H是Km,則G[H]是一個3mn-8m-1 正則連通圖,階為。由文獻(xiàn)[5]可知,G[H]的鄰接矩陣表達(dá)式為A(G[H])=A(G)?J+I?A(H),其中J表示全1 矩陣,?表示張量積。根據(jù)定理1,G[H]僅有五個不同的特征值:3mn-8m-1,2mn-8m-1,mn-6m-1,-2m-1,-1,極小多項式為(x-3mn+8m+1)(x-2mn+8m+1)(x-mn+6m+1)(x+2m+1)(x+1)。

因為H是Km,所以對于?v1,v2∈V(H),v1和v2相鄰,于是只需對u1,u2進(jìn)行分類討論。根據(jù)定理2,可以得到如下結(jié)論。

定理7對G[H]上的簡單隨機(jī)游走,對?i=u1v1,j=u2v2∈V(G[H]),有

(1)若u1與u2鄰接,i與j鄰接,則

(2)若u1與u2不鄰接且d(u1,u2)=2,i與j不鄰接,則

(3)若u1與u2不鄰接且d(u1,u2)=3,i與j不鄰接,則

(4)若u1=u2,i與j鄰接,則

證明設(shè)P是G[H]上簡單隨機(jī)游走的概率轉(zhuǎn)移矩陣,則P=A,極小多項式為

由于q(x)=f(x)(x-1),因此

經(jīng)過計算可得

而A3(G[H])的對角線子矩陣為

其非對角線子矩陣為

下面，對i,j分情況討論:

(1)若u1與u2鄰接,i與j鄰接,則由上面的式子及(1)、(2)和(3)

因此,

(2)若u1與u2不鄰接且d(u1,u2)=2,i與j不鄰接,則

(3)若u1與u2不鄰接且d(u1,u2)=3,i與j不鄰接,則

(4)若u1=u2,i與j鄰接,則

因為該字典積圖為無向圖,所以EiTj=EjTi。對任意i,j∈V(G[H]),可以得到兩點(diǎn)間的電阻距離公式

接下來,利用計算出的G[H]的特征值,推導(dǎo)出與[G[H]有關(guān)的一些圖不變量:度積基爾霍夫指數(shù)、凱梅尼常數(shù)以及生成樹個數(shù)。此外,基于G[H]上任意兩點(diǎn)間的平均首達(dá)時間,給出G[H]上任意兩點(diǎn)間的電阻距離。圖G和圖H的參數(shù)確定了這些圖不變量。文獻(xiàn)[12]刻畫了度積基爾霍夫指數(shù)與N(G)特征值之間的關(guān)系。

定理8設(shè)G是具有特征n的Johnson圖J(n,3),H為m階完全圖,其字典積G[H]的度積基爾霍夫指數(shù)為

又由A(G[H])的特征值可知N(G[H])的特征值為

對應(yīng)重數(shù)分別為

則由定理4可得

由上可知,對于凱梅尼常數(shù),利用定理5和定理8可以直接推出。

定理9設(shè)G是具有特征n的Johnson圖J(n,3),H為m階完全圖,其字典積G[H]的凱梅尼常數(shù)為

定理10設(shè)G是具有特征n的Johnson圖J(n,3),H為m階完全圖,其字典積G[H]的生成樹數(shù)目是

其中τ(G[H])是字典積G[H]的生成樹的數(shù)目,k1=n-1,k2=。

2 結(jié)束語

本文通過研究文獻(xiàn)[2]中賦權(quán)有向圖上隨機(jī)游走平均首達(dá)時間的表達(dá)式以及文獻(xiàn)[5]中兩個簡單圖的特征值與其字典積的特征值的關(guān)系,在文獻(xiàn)[6]研究具有三個不同特征值的強(qiáng)正則圖(非二部)與完全圖的字典積的基礎(chǔ)之上,根據(jù)Hoffman 多項式進(jìn)一步去研究具有四個不同特征值的Johnson 圖J(n,3)和完全圖字典積的鄰接矩陣及其特征值,再利用多項式方法推導(dǎo)出所生成的字典積上兩點(diǎn)間的平均首達(dá)時間、電阻距離以及一些重要的圖參數(shù)。