圖的拉普拉斯特征值與全控制參數(shù).pdf

1、在近四十年里，隨著計算機科學(xué)的迅速發(fā)展，圖論的發(fā)展也非常迅猛，其中圖的控制數(shù)理論是圖論中發(fā)展最快的幾個領(lǐng)域之一．控制數(shù)理論能夠快速發(fā)展的主要原因是它在組合優(yōu)化、編碼理論、計算機科學(xué)、通信網(wǎng)絡(luò)、監(jiān)視系統(tǒng)和社會網(wǎng)絡(luò)等理論與實踐中有著重要的應(yīng)用．隨著研究的深入和應(yīng)用的激發(fā)，各種新的控制參數(shù)不斷涌現(xiàn)．其中圖的函數(shù)(全)控制數(shù)就是(全)控制數(shù)的一類自然推廣．由于函數(shù)的引入，致使利用函數(shù)性質(zhì)來研究控制數(shù)成為可能．目前，函數(shù)控制數(shù)已成為圖的控制理論中

2、一個嶄新而富有挑戰(zhàn)的研究方向． 在圖論中，為了研究圖的性質(zhì)，人們引進(jìn)了圖的鄰接矩陣，關(guān)聯(lián)矩陣，距離矩陣，拉普拉斯矩陣等各種矩陣．代數(shù)圖論的一個主要問題就是研究圖的性質(zhì)能否以及如何由這些矩陣的代數(shù)性質(zhì)反映出來．而各種矩陣中，很重要的就是圖的拉普拉斯矩陣．因為拉普拉斯矩陣的特征值與圖的很多不變量有著密切的聯(lián)系．正如Mohar<'[1]>所說：圖的拉普拉斯矩陣的特征值更能反映它的圖論性質(zhì)．所以，對圖的拉普拉斯矩陣的特征值的研究也越來越

3、受到人們的廣泛關(guān)注． 本文主要研究了全控制數(shù)和符號全控制數(shù)的N-G型不等式，以及圖上幾類全控制參數(shù)與拉普拉斯特征值的關(guān)系，其相應(yīng)的結(jié)果分為以下兩個部分： 第一部分，研究了圖上符號全控制數(shù)γ<'s><,t>的Nordhaus-Gaddum型不等式，給出了路與其補圖的符號全控制數(shù)和的上界，以及圖與其補圖的符號全控制數(shù)和的下界． (有關(guān)結(jié)果被《運籌學(xué)學(xué)報》錄用) 第二部分，給出了連通圖上代數(shù)連通度α(G)關(guān)于全控制數(shù)γ