廣義Bethe樹的譜.pdf

1、譜圖理論主要研究圖的(Laplace譜或鄰接)特征值與圖的結(jié)構(gòu)聯(lián)系．本文所研究的廣義Bethe樹來源于理論計算機科學(xué)中的二叉樹以及Bethe樹．這兩類圖在計算機科學(xué)中的數(shù)據(jù)搜索等發(fā)揮著重要的作用．廣義Bethe樹視為上述兩類圖的推廣，在未來計算機科學(xué)中有著潛在的應(yīng)用價值。
　　2005年，Rojo和Soto引入廣義Bethe樹Bk，并對其Laplace譜和鄰接譜展開討論，用蘊含度信息的三對角矩陣的譜來描述廣義Bethe樹的譜．而度

2、信息是廣義Bethe樹的關(guān)鍵信息．因此Rojo和Soto建立了該類圖的結(jié)構(gòu)與譜的聯(lián)系．2006年，Rojo把原來廣義Bethe樹推廣到一種新的圖類B(2)k，即是由BK的兩個拷貝圖在它們根節(jié)點之間連一條邊而獲得．2007年，Rojo討論了另一類圖的B(r)k它是由由一個圈Tr和Bk的r個拷貝圖通過粘貼Tr的點和Bk的根節(jié)點而得．Rojo對上述兩類圖獲得了以度表示的譜．
　　受Rojo等人研究工作的啟發(fā)，我們的工作分為兩個階段：

3、r>　　(1)引入圖Bk.Kr并討論它的譜，其中Bk.Kr是由一個完全圖Kr和Bk的r個拷貝圖通過粘貼Kr的點和Bk的根節(jié)點而得；
　　(2)考慮到K2(一條邊)，Tr，Kr都是可遷圖，討論更一般的圖Bk.Jr,其中Bk.Jr是由一個可遷圖Jr和Bk的r個拷貝圖通過粘貼Kr的點和Bk的根節(jié)點而得．所以，Rojo等人所討論的圖都是本類圖的特殊情形．故我們的工作推廣了已有的相關(guān)工作．
　　本文討論了所引入的兩類圖的Laplace

4、譜和鄰接譜，用蘊含Bk的度及Kr(和Jr)的譜的三對角矩陣的譜，來表示Bk.Kr(和Bk.Jr)的鄰接譜和Laplace譜，并對一些極端特征值重數(shù)進行討論，特別地，對一些極端特征向量(如鄰接矩陣的Perron向量，Laplace矩陣的Fiedler向量)的組合結(jié)構(gòu)性質(zhì)進行了探討，獲得一些有意義的結(jié)論．
　　本文的結(jié)構(gòu)如下：第一章介紹譜圖理論的研究背景，本文所用的概念和記號，研究問題的進展及本文的主要結(jié)論．第二章引入基于廣義Beth