加權冠圖的無符號拉普拉斯譜和正規拉普拉斯譜

魏 斌，王維忠

蘭州交通大學 數理學院，蘭州 730070

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

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

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

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

圖1 圖G1，G2及其加權冠積圖G1°G2

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

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

(1)

定理1設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)對應的特征向量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)的重數為n.

2 G1°G2的正規拉普拉斯譜

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

(15)

設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)

有關正規拉普拉斯譜的詳細信息可參見文獻[11].

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

(17)

(18)

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

從而

(19)

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

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

(20)

(21)

因此，若兩個實數pi和a滿足

(22)

(23)

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

由(23)式得

(24)

由(22)式和(24)式得

(25)

其中

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

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

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

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

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

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

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

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

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

定理4設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))的重數為n(n+1)m-j-1，0≤j≤m-1；fm(θi)∈σ(G(m))的重數為1.

證用數學歸納法進行證明.

其中

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

定理5設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 結 語

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