，，

（湖南師范大學(xué) 數(shù)學(xué)系，湖南 長沙 410081）

1 研究背景

對于一個(gè)連通圖G，如果向量，則稱為G的算術(shù)結(jié)構(gòu)；如果條件

A(G)=(aij)，i～j表示i與j相鄰；d、r都為列向量，所有的元素都是正整數(shù)，rT為向量r的轉(zhuǎn)置矩陣。

給定一個(gè)簡單圖G，其拉普拉斯矩陣為

圖的算術(shù)結(jié)構(gòu)的概念，是Lorenzini研究代數(shù)幾何中退化曲線時(shí)，出現(xiàn)交矩陣而引入的[1]。近年來，關(guān)于算術(shù)結(jié)構(gòu)的研究較多，如文獻(xiàn)[2]研究了完全圖、路和圈上算術(shù)結(jié)構(gòu)的一些性質(zhì)；文獻(xiàn)[3]研究了路和圈上算術(shù)結(jié)構(gòu)的個(gè)數(shù)等。代數(shù)圖論是圖論的一大分支，它利用圖的關(guān)聯(lián)矩陣的代數(shù)性質(zhì)來研究圖。特別地，圖譜理論主要研究它的鄰接矩陣、拉普拉斯矩陣的特征值和圖的性質(zhì)之間的聯(lián)系[4]。

2 預(yù)備知識

為了證明本文將給出的有關(guān)結(jié)論，先介紹一些相關(guān)的知識和結(jié)論。

定義矩陣

因?yàn)長(G,d)是實(shí)對稱矩陣，它的特征值為實(shí)數(shù)，故可設(shè)為。

引理1[5]設(shè)A是一個(gè)n階任意矩陣，其特征值為λ1≥λ2≥…≥λn，為對應(yīng)于特征值λk的特征向量，q為任意n維的列向量，則矩陣A+vqT的特征值為

定理1設(shè)G是一個(gè)n階連通圖，則B(G)的特征值為

證明由B(G)=L(G,d)+re可得，B(G)r=L(G,d)r+rer。

因向量r中每個(gè)元素都是正整數(shù)，G連通，矩陣B(G)非負(fù)不可約，所以由Perron-Frobenius定理知，er是B(G)的譜半徑，且r是其Perron向量，即

由引理1可以得到B(G)的特征值為

推論1設(shè)G是一個(gè)n階連通圖，(d,r)為G上的一個(gè)算術(shù)結(jié)構(gòu)，則

3 算術(shù)結(jié)構(gòu)的拉普拉斯矩陣特征值更精確的上界

引理2[8]設(shè)M(G)=(mij)是一個(gè)n階非負(fù)實(shí)對稱矩陣，若有一個(gè)對應(yīng)于譜半徑的正特征向量，為M(G)的第二大特征值，則有

定理2設(shè)G是一個(gè)n階連通圖，為G上的一個(gè)算術(shù)結(jié)構(gòu)，則

證明由知，，從而r是對應(yīng)的正特征向量。

設(shè)

當(dāng)i～j時(shí)，則

由式（6）和式（7）可得，

由引理2可知，

定理3設(shè)G是一個(gè)n階連通圖，(d,r)為G上的一個(gè)算術(shù)結(jié)構(gòu)，則

證明令R=diag(r1,r2,…,rn)，定義矩陣，則C(G)的元素為

因?yàn)榫仃嘋(G)與L(G,d)相似，所以它們有相同的特征值，令x是矩陣C(G)對應(yīng)于特征值的特征向量。

由上述2個(gè)等式可得

因?yàn)閤j≤xk，xk≤xi，所以由式（10）得

設(shè)

其中

所以

因?yàn)長(G,d)r=0，所以C(G)eT=0，C(G)的秩等于L(G,d)的秩。因eT、x是C(G)不同特征值的特征向量，所以向量x與eT正交。而xi＞xj，因此

即L(G,d)最大特征值的上界為

推論2設(shè)G是一個(gè)n階連通圖，(d,r)為G上的一個(gè)算術(shù)結(jié)構(gòu)，則

證明事實(shí)上

類似地可得

將上述兩式子代入

可得

即

所以，由式（8）可知

相比較而言，式（11）沒有（8）精確，但計(jì)算簡便一些，也可以作為判斷特征值上界的一個(gè)依據(jù)。

4 算例

例1拆分完全圖K4的邊v3,v4得到的一個(gè)圖S4，如圖1所示。在G的算術(shù)結(jié)構(gòu)的拉普拉斯矩陣L(G,d)中，若d=(1,2,10,15,1)T，r=(15,10,3,2,5)T，試用本文的結(jié)論計(jì)算L(G,d)的最大特征值的上界。

圖1 圖S4Fig.1 Figure S4

解用式（2）（4）（8）（11）計(jì)算得到L(G,d)的最大特征值的上界分別為35,20,15.5,17，而矩陣L(G,d)的實(shí)際特征值有5個(gè)，分別為0,0.891 2,2.600 8,10.293 0,15.215 0。

顯然，由式（8）計(jì)算的結(jié)果為15.5，它與L(G,d)的實(shí)際最大特征值15.215 0相差非常小，所以式（8）更精確。

5 結(jié)語

本文得到了算術(shù)結(jié)構(gòu)拉普拉斯矩陣L(G,d)的最大特征值的4個(gè)上界，分別如式（2）（4）（8）（11）所示，其中式（8）中的上界最精確，而式（11）中的上界計(jì)算較簡便。