圖與混合圖的特征值問題研究.pdf

1、Master’SThesis，ZhengzhouUniversityNo201012141490TheInvestigationontheEigenvaluesofGraphsandMixedGraphsCandidate：Haixia№Supervisor：ProfJinjiangYuanDrRuifangLiuSpeciality：OperationsResearchandCyberneticsSchoolofMathematics

2、andStatistics，ZhengzhouUniversityZhengzhou，450001，PRChinaApril，2013摘要圖譜理論是圖論研究的一個(gè)非?；钴S而又重要的研究領(lǐng)域它在量子化學(xué)、統(tǒng)計(jì)力學(xué)、計(jì)算機(jī)科學(xué)以及信息科學(xué)中均有著廣泛的應(yīng)用在圖論理論中，為了研究圖的性質(zhì)，人們引入各種各樣的矩陣，諸如圖的鄰接矩陣、關(guān)聯(lián)矩陣、拉普拉斯矩陣等，這些矩陣與圖的結(jié)構(gòu)性質(zhì)都有著密切的聯(lián)系圖譜理論的研究主要是利用成熟的代數(shù)理論和技巧，并結(jié)

3、合圖論和組合數(shù)學(xué)的理論來研究圖譜、圖的結(jié)構(gòu)性質(zhì)以及與圖的其它不變量(如色數(shù)、度序列、圍長、連通度等)之間的關(guān)系，它將圖與網(wǎng)絡(luò)的代數(shù)性質(zhì)與其拓?fù)湫再|(zhì)緊密地結(jié)合在一起本文主要研究圖與混合圖的特征值問題首先，確定了懸掛點(diǎn)數(shù)固定的非二部單圈圖中無符號拉普拉斯最小特征值達(dá)到最小的極圖；其次，刻畫了懸掛點(diǎn)數(shù)固定的非奇異單圈混合圖第一特征值達(dá)到最小的極圖本文主要內(nèi)容如下：在第二章中我們研究非二部單圈圖的無符號拉普拉斯最小特征值記u(n，k)是具有n個(gè)

4、頂點(diǎn)和k個(gè)懸掛點(diǎn)的非二部單圈圖的集合我們確定了u(n，k)中無符號拉普拉斯最小特征值達(dá)到最小的極圖，并且說明這個(gè)極圖是唯一的進(jìn)一步，我們還證明出最小的無符號拉普拉斯最小特征值是關(guān)于k的遞增函數(shù)，并給出這一結(jié)果的一個(gè)應(yīng)用，直接確定出前人關(guān)于非二部單圈圖的無符號拉普拉斯最小特征值達(dá)到最小的極圖J在第三章中我們研究非奇異單圈混合圖的第一特征值記巧(n，七)是具有n個(gè)頂點(diǎn)和k個(gè)懸掛點(diǎn)的非奇異單圈混合圖的集合我們研究了當(dāng)一個(gè)全定向樹分支從非奇異單