圖譜及其在網路中的套用

《圖譜及其在網路中的套用》是依託北京交通大學，由余愛梅擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖譜及其在網路中的套用
• 項目類別：青年科學基金項目
• 項目負責人：余愛梅
• 依託單位：北京交通大學

項目摘要

圖的譜是圖的同構不變數，在圖論研究中最關心的問題是圖的譜與圖的結構之間的關係。已有的研究結果表明，許多圖類的結構可以由圖譜完全確定，圖的譜與圖的許多重要結構參數密切相關，如直徑、連通度、獨立數、色數、虧格、等周數、頻寬等等，利用它們可以給出這些結構參數簡潔漂亮的界。圖譜理論是代數圖論的重要組成部分，而且被廣泛套用於組合最佳化、網路及理論化學等領域。本項目將重點研究圖的譜（包括圖的鄰接矩陣的最大特徵值、圖的Laplacian矩陣的最大特徵值、第二小特徵值和圖的無符號Laplacian矩陣的最大特徵值等）與度量網路性能的參數（例如，直徑、（邊）連通度、限制（邊）連通度等）之間的關係及相關的極值問題。

結題摘要

按照計畫，我們對項目所列的研究內容進行了深入的研究，並已取得了部分結果和進展。在SCIE檢索雜誌上正式發表論文2篇，在國家核心期刊上發表論文1篇，另有1篇論文已投稿。依託本項目，招收碩士研究生5名，其中2人已畢業。 本項目已取得的結果和進展如下： 一、對譜半徑進行估界。 （1）利用度序列，分別給出了賦權圖的鄰接譜半徑和拉普拉斯譜半徑的一個新的下界。根據這個下界可以推出非賦權圖若干已知的下界。（2）確定了不含子圖Bk+1和K2,l+1的圖的無號拉普拉斯譜半徑的上界。利用這個結果可以確定不含4圈的圖以及圍長至少是5的圖的無號拉普拉斯譜半徑的上界。 二、刻畫給定圖類中具有最小譜半徑的圖。 確定給定圖類中具有最大或最小譜半徑的圖是圖譜理論研究的一個重要方向，其中確定具有最小譜半徑的圖相對於確定具有最大譜半徑的圖而言更困難一些。我們按照鄰接譜半徑對樹進行排序，在前人的基礎上，進一步確定了譜半徑第八、第九、第十小的樹。 三、刻畫了秩為4的符號圖的結構和秩為7的（符號）雙圈圖的結構。 圖的秩指的是圖的鄰接矩陣特徵值中非零特徵值得個數。簡單圖的秩與圖的匹配數密切相關。近年來對圖的秩的研究比較熱。我們刻畫了秩為4的符號圖的結構和秩為7的（符號）雙圈圖的結構。在研究符號圖的秩的基礎上，我們進一步研究賦權圖的秩。我們刻畫了秩為2的賦權圖和不含4階完全圖且秩為3賦權圖的結構，並且將簡單圖秩的一些結論推廣到了賦權圖上。 四、刻畫給定圖類具有較小的關聯能量的圖的結構。 圖的關聯能量指的是圖的關聯矩陣的奇異值的和。對二部圖而言，圖的關聯能量等於圖的Laplacian矩陣的特徵值的平方根的和。以前，圖譜理論的研究主要集中在圖的某個特徵值。近年來一些涉及到多個特徵值的參數逐漸受到更多的關注，比如各種定義的圖的能量。在前人的基礎上，我們進一步確定了具有第五——第七小的關聯能量的樹的結構。目前我們正在研究其他圖類的關聯能量的極值和極圖，例如給定直徑的樹的關聯能量。