有關(guān)組合矩陣論中圖譜與符號模式矩陣的研究.pdf

1、組合矩陣論是一個近20余年來興起并迅速發(fā)展的一個數(shù)學(xué)分支.它用矩陣論和線性代數(shù)來證明組合定理及對組合結(jié)構(gòu)進(jìn)行描述和分類.同時，也把組合論的思想和論證方法用于矩陣的精細(xì)分析及揭示陣列的內(nèi)在組合性質(zhì).對圖譜理論和符號模式矩陣的研究是組合矩陣論的重要組成部分.圖譜理論是圖論研究的一個非?；钴S而又重要的研究領(lǐng)域，它在量子化學(xué)、統(tǒng)計力學(xué)、計算機(jī)科學(xué)、通信網(wǎng)絡(luò)以及信息科學(xué)中均有著廣泛的應(yīng)用.在圖譜理論中，為了研究圖的性質(zhì)，人們引入了各種各樣的矩陣，

2、諸如圖的鄰接矩陣、關(guān)聯(lián)矩陣、拉普拉斯矩陣、無符號拉普拉斯矩陣、距離矩陣等等.這些矩陣與圖的結(jié)構(gòu)都有著密切的聯(lián)系.圖譜理論的一個主要問題就是研究圖的性質(zhì)能否以及如何由這些矩陣的代數(shù)性質(zhì)(例如譜半徑，譜唯一性，譜展，能量等等)反映出來.符號模式矩陣的研究在經(jīng)濟(jì)學(xué)、生物學(xué)、化學(xué)和社會學(xué)以及理論計算機(jī)科學(xué)中具有廣泛的實際應(yīng)用背景.對符號模式矩陣的研究包括符號模式矩陣的冪序列性質(zhì)，可解性問題，穩(wěn)定性問題等.本論文主要涉及的是對符號模式矩陣的冪序列

3、性質(zhì)的研究.
　　 在圖譜理論方面，本論文主要研究了圖的鄰接譜、無符號拉普拉斯譜(Q-譜)、距離譜.主要對圖的鄰接矩陣、無符號拉普拉斯矩陣(Q-矩陣)、距離矩陣的譜半徑、最小根以及譜展進(jìn)行研究，試圖建立它們與圖的結(jié)構(gòu)參數(shù)之間的一些關(guān)系；在符號模式矩陣方面，我們刻畫了一些特殊圖類的Iewin指數(shù)極圖，刻畫了一些本原非可冪符號模式矩陣的基集和達(dá)到基的上界的極圖，繼邵嘉裕老師、柳柏濂、尤利華和苗正科老師等對一般的本原非可冪符號模式矩陣

4、的基集的研究成果和研究工作以及本人在碩士論文中的一些工作，給出一些關(guān)于基的界，同時證明了在基集中有一些新的間隔(“gaps”).本論文的主要內(nèi)容如下：
　　 (一)在第一章中，我們首先回顧介紹了圖論研究的背景和進(jìn)展；接著介紹了一些圖譜理論問題的研究背景和進(jìn)展；最后介紹了符號模式矩陣的一些研究背景和進(jìn)展.
　　 (二)在第二章中，我們研究n階圖的鄰接譜.我們先介紹了一些基本概念、記號和一些引理.接著在第二、三節(jié)，我們探討圖

5、子式(Minor)與圖的譜之間的關(guān)系，尋找圖的拓?fù)湫再|(zhì)與代數(shù)性質(zhì)的內(nèi)在聯(lián)系，對禁用子圖K2，3的圖類和邊數(shù)最多的外平面二部圖圖的給出了一些結(jié)構(gòu)性的刻畫，通過已有工具對這些圖類的鄰接譜半徑進(jìn)行研究，給出了一些比較好的上、下界，甚至刻畫達(dá)到一些界的極圖.在本章最后，我們討論了直徑給定的雙圈圖中最小根，并對達(dá)到最小根的極圖給出了一些結(jié)構(gòu)刻畫.
　　 (三)在第三章中，我們研究n階圖的無符號拉普拉斯譜.我們在第一節(jié)中介紹了一些基本概念、

6、記號和一些引理.在第二節(jié)中討論一般圖的Q-譜半徑的界，給出了一些上、下界并刻畫了達(dá)到下界的極圖.我們接著在第三、四節(jié)中討論一些特殊圖類的Q-譜半徑的界，刻畫了色數(shù)給定的圖和θ-圖類中達(dá)到Q-譜半徑的上、界的極圖.最后我們在第五節(jié)中考慮圖的Q-譜的第二大根q2.刻畫了q2=2的圖；對n≥9階連通非二部圖，刻畫了q2≤3的圖；對n≥7階連通二部圖，刻畫了q2≤3的圖.我們證明了(i)如果n≥2，不存在n階圖G使得q2(G)∈((1，2)∪(

7、3+√5/2，2.7))；(ⅱ)如果n≥9，不存在n階圖G使得q2(G)∈((1，3+√5/2)∪(3+√5/2，2.7))，并確定了3是q2的最小極限點.
　　 (四)在第四章中，我們研究n階圖的距離譜.在第一節(jié)中我們給出了幾個增大或減小距離譜半徑的移接變形定理，利用這些移接變形定理，對具有給定懸掛點數(shù)k的n階簡單連通圖類，證明了具有最小距離譜半徑的圖是在一個n-k階完全圖的一點接k條懸掛邊得到的圖，具有最大距離譜半徑的圖是一

8、個啞鈴圖.第二節(jié)中我們也給出了幾個增大或減小距離譜半徑的移接變形定理，利用這些移接變形定理，我們證明了S’n(通過在星Sn的兩個懸掛點之間加一條邊得到)在所有的n階單圈圖中具有最小的距離譜半徑；而P'n(通過在K3的一點接一條懸掛路Pn-3得到)在所有的n階單圈圖中具有最大的距離譜半徑.在本章最后，我們對一般圖的距離譜半徑給出了較好的上、下界并刻畫了達(dá)到該上、下界的極圖；研究了一般圖的距離譜展(即距離矩陣的譜半徑與最小特征值之差)的下界

9、，證明了完全圖Kn是n階圖中達(dá)到距離譜展下界的唯一極圖，完全二部圖K()，()是n階二部圖中達(dá)到距離譜展下界的唯一極圖.
　　 (五)在第五章中，我們研究n階符號模式矩陣的冪序列性質(zhì).我們在第一節(jié)中介紹了一些基本概念、記號和一些引理；在第二節(jié)中刻畫了圍長為2或3達(dá)到Lewin數(shù)上界的極圖；在第三節(jié)中刻畫了恰好具有d個非零對角元的本原非可冪符號模式矩陣的基集和達(dá)到基集上界的弧最少的極圖；在第四節(jié)中刻畫了對角元全為零的零對稱本原非可