廣義Bethe樹(shù)的譜.pdf

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

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

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

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