圖的結(jié)構(gòu)參數(shù)與特征值.pdf

1、圖譜理論是圖論研究的一個(gè)非?；钴S而又重要的研究領(lǐng)域，它在量子化學(xué)、統(tǒng)計(jì)力學(xué)、計(jì)算機(jī)科學(xué)、通信網(wǎng)絡(luò)以及信息科學(xué)中均有著廣泛的應(yīng)用。在圖譜理論中，為了研究圖的性質(zhì)，人們引入了各種各樣的矩陣，諸如圖的鄰接矩陣、拉普拉斯矩陣、關(guān)聯(lián)矩陣、距離矩陣等等，這些矩陣與圖的結(jié)構(gòu)都有著密切的聯(lián)系。圖譜理論的一個(gè)主要問題就是研究圖的性質(zhì)能否以及如何由這些矩陣的代數(shù)性質(zhì)反映出來。這里所指的矩陣的代數(shù)性質(zhì)，主要是指矩陣的特征值性質(zhì)，例如譜半徑，譜唯一性，譜展，能

2、量等等。在上面所提及的矩陣中，最重要的兩個(gè)就是圖的鄰接矩陣和拉普拉斯矩陣。本文主要對(duì)圖的鄰接矩陣和拉普拉斯矩陣的譜半徑以及譜展進(jìn)行研究，試圖建立它們與圖的結(jié)構(gòu)參數(shù)之間的一些關(guān)系。主要內(nèi)容如下：
　　 ⑴第一章，首先回顧了圖論的演變，接著介紹了本文所研究的一些圖譜理論問題的背景和進(jìn)展．最后引入了相關(guān)問題的一些基本概念和記號(hào)。
　　 ⑵第二章，討論了圖的鄰接譜半徑與圖的結(jié)構(gòu)參數(shù)之間的關(guān)系．在文獻(xiàn)[119]中，E. R. va

3、n Dam刻畫了直徑給定的連通圖中最大鄰接譜半徑的極圖．這里，我們刻畫了直徑給定的二部圖中最大鄰接譜半徑的極圖以及圍長(zhǎng)給定的雙圈圖中最大鄰接譜半徑的極圖。
　　 ⑶第三章，首先給出了關(guān)于拉普拉斯譜半徑的一個(gè)邊嫁接定理，作為它的一個(gè)應(yīng)用，我們刻畫了圍長(zhǎng)給定的雙圈圖中最大拉普拉斯譜半徑的唯一極圖。此外，我們獲得了圖的拉普拉斯譜半徑關(guān)于直徑的一個(gè)上界并刻畫了直徑給定的圖中最大拉普拉斯譜半徑的極圖。
　　 ⑷第四章，研究圖的譜展