加權(quán)冠圖的無符號拉普拉斯譜和正規(guī)拉普拉斯譜

魏 斌，王維忠

蘭州交通大學 數(shù)理學院，蘭州 730070

眾所周知，許多復雜系統(tǒng)，如社會系統(tǒng)、生物系統(tǒng)等，均可用復雜網(wǎng)絡(luò)來描述，而任何復雜網(wǎng)絡(luò)都可用圖來表示.因此，關(guān)于復雜網(wǎng)絡(luò)的研究一直是圖論領(lǐng)域中的熱點問題.相比較無權(quán)網(wǎng)絡(luò)只考慮節(jié)點間相互作用的存在與否，加權(quán)網(wǎng)絡(luò)的權(quán)還能刻畫該網(wǎng)絡(luò)所描述實際系統(tǒng)中個體間相互作用的強度，因此加權(quán)網(wǎng)絡(luò)更能準確地描述實際網(wǎng)絡(luò)[1].例如，機場網(wǎng)絡(luò)[1]中每年在兩個機場之間旅行的乘客人數(shù)，網(wǎng)絡(luò)[2]中路由器之間單位時間內(nèi)的數(shù)據(jù)包流量，以及生態(tài)系統(tǒng)[3]中捕食者——被捕食者相互作用的強度等都可通過權(quán)來反映.雖然目前關(guān)于冠圖的成果很多[4-8]，但關(guān)于加權(quán)冠圖的研究十分鮮見.文獻[9]刻畫了G2為d-正則圖和完全二部圖時加權(quán)冠圖G1°G2的鄰接特征值，同時得到了當G2是連通圖時圖G1°G2的拉普拉斯特征值.文獻[10]中給出了G2為d-正則圖和完全二部圖時加權(quán)邊冠圖G1◇G2的鄰接特征值和(無符號)拉普拉斯特征值.

受上述研究的啟發(fā)，本文刻畫了當G2為正則圖時，加權(quán)冠積圖G1°G2的無符號拉普拉斯譜，以及G1和G2都為正則圖時，G1°G2的正規(guī)拉普拉斯譜.借助數(shù)學歸納法，把關(guān)于G1°G2的結(jié)果加以推廣，得到了加權(quán)冠圖G(m)的無符號拉普拉斯譜和正規(guī)拉普拉斯譜.下面，首先給出加權(quán)冠積圖[9]的定義.

定義1設(shè)G1和G2是階數(shù)分別為n和k的簡單連通圖，將G1復制一次且每條邊的權(quán)數(shù)為1，G2對應(yīng)于G1的頂點復制n次且每條邊的權(quán)數(shù)為r(0

例如，設(shè)G1為4個頂點的圈，G2為3個頂點的完全圖，則加權(quán)冠積圖G1°G2如圖1(c)所示.

圖1 圖G1，G2及其加權(quán)冠積圖G1°G2

1 G1°G2的無符號拉普拉斯譜

設(shè)R?S表示矩陣R和S的克羅內(nèi)克積，由G1°G2的定義，可得G1°G2的無符號拉普拉斯矩陣為

(1)

定理1設(shè)G1是n階的簡單連通圖，G2是k階的d-正則圖.σ(G1)={θ1，θ2，…，θn}，σ(G2)={νi|ν1≤ν2≤…≤νk=2d}.則Q(G1°G2)的特征值為：

Q(G1°G2)X=ξX

(2)

下面我們分兩種情形進行討論.

情形1X1為非零向量.

由(1)式和(2)式得

(Q(G1)+rkIn)X1+r(X2+X3+…+Xk+1)=ξX1

(3)

和

(4)

因為G2是d-正則圖，則Q(G2)矩陣的每行元素之和為2d.將(4)式中的所有方程相加，可得

krX1+r(2d+1)(X2+X3+…+Xk+1)=ξ(X2+X3+…+Xk+1)

(5)

移項得

krX1+((2d+1)r-ξ)(X2+X3+…+Xk+1)=0

(6)

由于X1是非零向量，我們推出(2d+1)r-ξ≠0.由(3)式和(6)式，得

(7)

即

(8)

ξ2-((2d+1)r+kr+θi)ξ-kr2+(2d+1)kr2+(2d+1)rθi=0i=1，2，…，n

(9)

解二次方程(9)，得

(10)

情形2X1為零向量.

由(1)式和(2)式得

X1+X2+…+Xk+1=0

(11)

和

r(Q(G2)+Ik)?In[X2X3…Xk+1]T=ξ[X2X3…Xk+1]T

(12)

故r(2d+1)不是Q(G1°G2)的特征值.如若不然，假定r(2d+1)是Q(G1°G2)的特征值，則r(2d+1)對應(yīng)的特征向量X=[X1X2…Xk+1]T滿足X=Jn?Jk+1.因此

X1+X2+…+Xk+1=(k+1)Jn

(13)

這與(11)式相矛盾.所以

ξ=r(νj+1)j=1，2，…，k-1

(14)

從(12)式可以看出ξ=r(νj+1)的重數(shù)為n.

2 G1°G2的正規(guī)拉普拉斯譜

正規(guī)拉普拉斯矩陣和圖G上的簡單隨機途徑與譜的幾何結(jié)構(gòu)密切相關(guān).給定一個圖G，令P(G)=D(G)-1A(G)表示G上的簡單隨機游動的概率轉(zhuǎn)移矩陣，則

(15)

設(shè)L(G)和P(G)的譜分別為λ1(G)，λ2(G)，…，λn(G)和μ1(G)，μ2(G)，…，μn(G).其中0=λ1(G)≤λ2(G)≤…≤λn(G)≤2，1=μ1(G)≥μ2(G)≥…≥μn(G)≥-1.則

λi(G)=1-μi(G)i=1，2，…，n

(16)

有關(guān)正規(guī)拉普拉斯譜的詳細信息可參見文獻[11].

設(shè)G1和G2分別為n1階和n2階正則連通圖，且正則度分別為r1和r2，則

(17)

(18)

由于G1和G2都是正則圖，故

從而

(19)

由(15)式知，在刻畫G1°G2的正規(guī)拉普拉斯譜時，首先給出概率轉(zhuǎn)移矩陣P(G1°G2)的譜.

定理2設(shè)G1和G2分別是階數(shù)為n1和n2的正則連通圖，正則度分別為r1和r2，P(G1)的譜為μ1(=1)，μ2，…，μn1，P(G2)的譜為η1(=1)，η2，…，ηn2.則P(G1°G2)的譜為：

(20)

(21)

因此，若兩個實數(shù)pi和a滿足

(22)

(23)

則P(G1°G2)的屬于特征值pi的特征向量為

由(23)式得

(24)

由(22)式和(24)式得

(25)

其中

根據(jù)定理2和(16)式，即得出G1°G2的正規(guī)拉普拉斯譜：

定理3設(shè)G1和G2分別是階數(shù)為n1和n2的正則連通圖，正則度分別為r1和r2，L(G1)的譜為λ1(=0)，λ2，…，λn1，L(G2)的譜為δ1(=0)，δ2，…，δn2.則L(G1°G2)的譜為：

3 G(m)的無符號拉普拉斯譜和正規(guī)拉普拉斯譜

本節(jié)中，我們將推廣加權(quán)冠積圖得到加權(quán)冠圖的無符號拉普拉斯譜和正規(guī)拉普拉斯譜.首先，定義加權(quán)冠圖[9]如下：

定義2設(shè)G是n階的簡單連通圖，且每條邊的權(quán)都為1，G′為G的復制圖.加權(quán)冠圖G(m)定義為G(m)=G(m-1)°G′，新生成的邊的權(quán)為rm(其中m≥1是自然數(shù)).

例如，設(shè)G=K3(3個頂點的完全圖)(圖2(a))，則加權(quán)冠圖G(1)和G(2)分別如圖2(b)和2(c)所示.

圖2 圖G及其加權(quán)冠圖G(1)和G(2)

其中j=1，2，…，且f0(x)=x+1.

接下來給出當G為d-正則圖時，加權(quán)冠圖G(m)的無符號拉普拉斯譜.

定理4設(shè)G是n階d-正則圖，σ(G)={θ1，θ2，…，θn}，則

σ(G(m))={rm-jfj(θi)|0≤j≤m-1，i=1，2，…，n-1；j=m，i=1，2，…，n}

其中：

j=1，2，…；f0(x)=x+1；rm-jfj(θi)∈σ(G(m))的重數(shù)為n(n+1)m-j-1，0≤j≤m-1；fm(θi)∈σ(G(m))的重數(shù)為1.

證用數(shù)學歸納法進行證明.

其中

最后，刻畫了G為d-正則圖時，G(m)的正規(guī)拉普拉斯譜：

定理5設(shè)G是n階d-正則圖，L(G)的譜為λ1，λ2，…，λn，則L(G(m))的譜為

{rm-jgj(λi)|0≤j≤m-1，i=1，2，…，n-1；j=m，i=1，2，…，n}

其中

證同定理4.

4 結(jié) 語

本文主要研究了加權(quán)冠圖的無符號拉普拉斯譜和正規(guī)拉普拉斯譜.具體來講，刻畫了當G2為正則圖時，加權(quán)冠積圖G1°G2的無符號拉普拉斯譜，以及G1和G2都為正則圖時，G1°G2的正規(guī)拉普拉斯譜.并借助數(shù)學歸納法將關(guān)于G1°G2的結(jié)果加以推廣，給出了加權(quán)冠圖G(m)的無符號拉普拉斯譜和正規(guī)拉普拉斯譜.所得結(jié)論進一步豐富了圖譜理論和加權(quán)網(wǎng)絡(luò)研究方面的成果.