樹的譜矩研究

李星宇

【摘要】譜矩序列作為圖的一個非常不可或缺的重要特征，在重構猜想研究中，及尋求圖中的不變量的完全組，起到了事關重要的作用。譜矩序列與通過研究樹的結構特征，首先確定能生成長為8的閉途徑的所有樹子圖，然后給出樹的前8階譜矩計算公式。

【關鍵詞】樹 星樹 樹的譜矩

【中圖分類號】G64 【文獻標識碼】A 【文章編號】2095-3089（2018）50-0147-02

引言

1942年Kelly和Ulam提出重構猜想。重構猜想至今為止依然是三大著名圖論里的難題之一。至今為止關于重構猜想是否是NP-C問題仍無定論。找出圖中的不變量的完全組和一組特征或參數，是在重構猜想的研究中非常關鍵的一個步驟，從而可以準確確定一個圖。目前圖論里還存在了許多相關參數，如：連通度、最大匹配的邊數、階、度序列、最小度、 最大度等等。但關于圖里的不變量的完全組的確定現在仍然有很多問題還在探索之中。由于圖的k階譜矩等于圖中長為 k 的閉途徑的條數，從而可知在譜矩序列中確定圖的閉途徑。因此圖的譜矩序列的確定圖的閉途徑的條數，對研究重構猜想也是起到事關重要的意義的。（重構猜想）如果G是至少有3個頂點的簡單圖，則G由它的頂點刪除子圖序列唯一確定。20世紀以來圖的排序問題成為代數圖論中比較有趣的問題之一。在1987年，Cvetkovíc和Rowlinson分別給出圖的前4階譜矩的計算公式，同時給出樹和單圈圖依譜矩序排在最前和最后的圖。2009年范瓊等2010年吳亞平等分別給出圖的第5階和第6階譜。2011年Pan X F等給出了最大度的樹譜矩序排序。2012年Pan X F等偽樹圖譜矩序排序。本文將給出樹的前10階譜矩的計算公式。

1.預備知識

通常的我們將一個圖定義為G=（V（G），E（G））其中我們一般令V（G）為圖G的定點的個數，E（G）為圖的邊的個數，然而僅僅依靠定點和邊的個數還不足以確定一個圖的形狀，其存在的不同形式類似于化學中的同分異構，如果能找出點和邊的一般規律就可以很大程度上的去解決相關問題。然后是對于閉途徑W的定義，閉途徑為圖的點邊交替形成的一串序列，形如v0，e0，v1，e2，…ek ，vk其中v為不同的定點e為不同的邊點邊交替可以唯一確定一條路徑如果此時v0=vk即圖的首尾是相同的定點，那么該途徑稱之為圖的閉途徑。當此時如果其中所有閉途徑的點都沒有重復，那么形成的圖可以稱之圈。無論是對于途徑圈亦或是路的長度都是指其中邊的條數，列如v0、e0、v1、e0、v1就為一條閉途徑。通常我們將圈和路分別令為Ck，Pk+1其長度均為k。我們又通常將連通且不成圈的圖稱之為樹。其中又存在一種極為特殊的情況，當其存在一中心定點與其它所有定點均相鄰的圖我們稱之為星樹，并將中心點稱之為星樹的中心點n個頂點的星樹稱之為K1，n-1。

引理1 圖的k階譜矩為圖的G的n個特征值的k次冪之和，其中特征值為圖G的鄰接矩陣A（G）=[aij]n*n其中若兩定點相鄰的話aij=1，反之若不相鄰則aij=0，圖的特征值就是圖G的特征值，因此圖的特征值為（G），由此可得知圖的譜矩序列S=（S0（G），S1（G），…，Sn（G））。

引理2 圖G的第k階譜矩等于G中長為k的閉途徑的個數

引理3 設G是n階圖，則S0（G）=n S1（G）=l S2（G）=2m S3（G）=6t S4（G）=2m+4p+8q，其中l，m，t分別表示圖中環、邊、三角形的個數，p、q分別表示相鄰邊對和四邊形的個數。

引理4 設G是n階圖，則S6（G）=2p2+12p3+6p4+12k1，3+24c4+12c1+12c6+24a3，3+26b3，3其中c表示G中圈的個數，p則表示G中路的個數，k代表圖中的星樹個數，上下角標表示帶有懸掛點的圈子圖的個數。

2.主要結果

根據引理1-5可知，n 階樹 T 的任意奇數階譜矩皆為0，前 8階偶數階譜矩為：

S0（T）=n

S2（T）=2（n-1）

S4（T）=2（n-1）+4p3

S6（T）=2（n-1）+12p3+6p4+12k1，4

S8（T）=2p2+28p3+32p4+8p5+16p14+72k1，3+48k1，4

下面給出樹第10階譜矩計算公式

S10（T）=2p2+60p3+114p4+60p6+10p6+120p14+18p15+288k1，3+480k1，4+240k1，5+40m1+60m2+24m3

p2左右兩點分別標記為a、b，從兩個頂點出發各有1條長為10的閉途徑：ababcbabcba abcbababcba 所以共有2條閉途徑。

p3從左到右依次標記為a、b、c，從a點出發的閉途徑：ababababcba 等共計15條，同樣從c點出發也有15條的閉途徑。從b點出發長為10的閉途徑：bababababcb等共計30條。共有60條長為10的閉途徑。

p4從左到右依次標記為a、b、c、d，從a點出發的閉途徑：abababcdcba a等共計18條，同理從d出發也有18條長為10的閉途徑。從b出發長為10的閉途徑：babababcdcb等共計39條，同理從c出發也有39條長為10的閉途徑。共有114條閉途徑。 p5從左到右依次標記為a、b、c、d、e，從a點出發長為10的閉途徑：ababcdedcba 等共計7條，同理從e出發也有7條長為10的閉途徑。從b出發長為10的閉途徑：bababcdedcb等共計15條，同理從d出發也有15條長為10的閉途徑。從c出發重復ab和bc的分別有長為10的閉途徑分別是：cbababcdedc 等2條和cbcbabcdedc等共計6條，同理重復cd和de的也分別有2種和6種，所有從c出發共有16條長為10的閉途徑。所以共有60條長為10的閉途徑。

p6從左到右依次標記為a、b、c、d、e、f，從a出發有1條長為10的閉途徑abcdefedcba，同理從f出發也只有1條長為10的閉途徑。從b出發有2條長為10的閉途徑babcdefedcb等2條，同理從e出發也只有2條長為10的閉途徑。從c出發有2條長為10的閉途徑cbabcdefedc等，同理從d出發也只有2條長為10的閉途徑。所以共有10條長為10的閉途徑。

p51從左到右從上到下依次標記為a、b、c、d、e、f，從a出發有2條長為10的閉途徑。從b出發長為10的閉途徑babcdedfdcb等共計4條。從c出發長為10的閉途徑cbabcdedfdc等共計4條。從d出發長為10的閉途徑dcbabcdedfd等共計4條。從e出發有2條長為10的閉途徑，同理從f出發也有2條長為10的閉途徑，所以共有18條長為10的閉途徑。

p41從左到右從上到下依次標記為a、b、c、d、e，從a出發長為10的閉途徑：ababcdcecba 等共計14條，從b出發長為10的閉途徑bababcdcecb等共計28條，從c出發長為10的閉途徑：cdcdcecbabc等共計48條，從d出發長為10的閉途徑：dcdcecbabcd等共計15條，同理從e出發有15條長為10的閉途徑。所以共有120條長為10的閉途徑。

k1，3的中心點標記為a，其它的點從左到右從上到下依次標記為b、c、d，因為k1，3是樹圖，每條邊必須走兩次，那么令邊ab、ac、ad分別為BCD，從a出發的長為10的閉途徑，相當于BCD分別重復3次3A55/A33=60，分別重復2次BBCCD BBCDD BCCDD 3A55/A22×A22=90種，所以從a出發有150條長為10的閉途徑。從b出發首先第一條和最后一條為確定值，所以只需考慮剩下四條邊，若除這兩次以外不走，ab這條邊則分為CCCD CDDD CCDD 3種情況2A44/2A33+ A44/A22×A22=10種，若重復ab分為BCCD BCDD BBCD 3A44/A22=36種，所以從b出發有46條長為10的閉途徑。同理從c、e出發有46條長為10的閉途徑。所以共有288條長為10的閉途徑。

k1，4的中心點為a，同理命名bcde，因為k1，4是樹圖，每條邊必須走兩次，那么令邊分別為BCDE從a點出發的長為10的閉途徑為四種情況全排列，根據排列組合原理4A55/A22=120種，從b點出發的長為10的閉途徑為BCDE全排列A44=24種，如果重復走的為CDE任意一條則為CCDE CDDE CDEE全排列36種。共60種同理從c、d、e出發也有60條長為10的閉途徑，所以共有480條。

k1，5的中心點標記為a同理命名bcdef，因為k1，5是樹圖，每條邊必須走兩次，根據排列組合原理從a點出發的長為10的閉途徑有C51×C41×C31×C21=120種，從b點出發同樣根據排列組合原理有C41×C31×C21=24種，從c、d、e、f出發同樣有24條，所以共有240條。

m1從左到右從上到下依次標記為a、b、c、d、e、f，從a出發長為10的閉途徑：acbcdedfdca等共計4條。同理從b、e、f出發也有4條長為10的閉途徑。從c出發12長為10的閉途徑：cacbcdedfdc等共計12條，同理從d出發也有12條長為10的閉途徑。所以共有40條。

m2同理標記為a、b、c、d、e、f，從a出發長為10的閉途徑：abcdcecfcba等共計6條。從b出發0的閉途徑：babcdcecfcb等共計12條，從c出發長的閉途徑：cdcecfcbabc等共計24條，從d出發長為10的閉途徑：dcecfcbabcd等共計6條，同理從e、f出發也有6條長為10的閉途徑。所以共有60條。

m3同理標記為a、b、c、d、e，從a出發有2條長為10的閉途徑，從b出發有2條長為10的閉途徑，同理從f出發有2條長為10的閉途徑。從c出發長為10的閉途徑：cbcdefedadc等共計4條。同理從e出發有4條長為10的閉途徑，從d出發長為10的閉途徑：dcbcdadefed等共計6條，所以共有24條閉途徑。

參考文獻：

[1]West D B.圖論導引：英文版[M].2版.北京：機械工業出版社，2004.

[2]Cvetkovíc D，Rowlinson P.Spectra of unicyclic graphs[J].Graph and Combinatorics，1987（3）：7-23.

[3]范瓊，吳亞平.圖的譜矩序列與圖的排序[J].武漢大學學報：理學版，2009（6）：1-4.

[4]吳亞平，呂康南，付捷.樹的譜矩研究.江漢大學學報（自然科學版），2012（6）

[5]Wu Y P，Liu H Q.Lexicographical ordering by spectral moments of trees with a prescribed diameter[J].Linear Algebra and Its Application，2010（11/12）：1707-1713.