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

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

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

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