樹的譜矩研究

李星宇

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

【關(guān)鍵詞】樹 星樹 樹的譜矩

【中圖分類號】G64 【文獻(xiàn)標(biāo)識碼】A 【文章編號】2095-3089（2018）50-0147-02

引言

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

1.預(yù)備知識

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

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

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

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

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

2.主要結(jié)果

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

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左右兩點(diǎn)分別標(biāo)記為a、b，從兩個頂點(diǎn)出發(fā)各有1條長為10的閉途徑：ababcbabcba abcbababcba 所以共有2條閉途徑。

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

[1]West D B.圖論導(dǎo)引：英文版[M].2版.北京：機(jī)械工業(yè)出版社，2004.

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

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

[4]吳亞平，呂康南，付捷.樹的譜矩研究.江漢大學(xué)學(xué)報（自然科學(xué)版），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.