圖的幾類譜及其與圖的變換的關(guān)系.pdf

1、圖譜理論是圖論研究的一個非?；钴S的重要領(lǐng)域,它以代數(shù)理論、分析理論、矩陣?yán)碚摰葹榛A(chǔ)研究圖論問題.圖譜理論的發(fā)展不僅促進(jìn)和豐富了圖論、組合學(xué)以及相關(guān)學(xué)科的研究,而且在化學(xué)、物理、計算機科學(xué)、通信網(wǎng)絡(luò)以及信息技術(shù)、集成電路設(shè)計等領(lǐng)域中均有廣泛的應(yīng)用.
　　 為了研究圖的性質(zhì)人們引入了很多矩陣,如:鄰接矩陣、拉普拉斯矩陣、規(guī)范拉普拉斯矩陣等等,這些矩陣與圖的結(jié)構(gòu)有著非常密切的聯(lián)系,它們的特征值都是圖的同構(gòu)不變量.圖譜理論的研究對象包

2、括圖的鄰接譜、拉普拉斯譜、規(guī)范拉普拉斯譜等等,它們是特定組合結(jié)構(gòu)的特有屬性,往往能給出一些深刻的結(jié)論,在圖論研究中扮演著越來越重要的角色.
　　 關(guān)于圖的鄰接譜和拉普拉斯譜的研究已有相當(dāng)長的歷史,前者是圖論、特別是代數(shù)圖論的一個基本研究課題,已形成相當(dāng)成熟的理論.后者的研究目前仍然非?；钴S,和圖的鄰接矩陣相比,由于在拉普拉斯矩陣的定義中融合了頂點的度信息,正如Mohar所說,拉普拉斯特征值更能反映圖的結(jié)構(gòu)性質(zhì),所以拉普拉斯譜的研

3、究也正越來越受到國內(nèi)外學(xué)者的關(guān)注.
　　 圖的規(guī)范拉普拉斯譜是由Fan R.K.Chung首先引入并研究的,是相對比較新的一個研究方向.規(guī)范拉普拉斯矩陣形式上也許沒有拉普拉斯矩陣簡潔,但它可視為Riemann流形上拉普拉斯算子的離散情形,其特征值與譜黎曼幾何以及隨機過程中的特征值有某種一致性,這就使得它的特征值和圖的不變量有著更自然的聯(lián)系.
　　 考慮圖在各種變換或運算下圖的特征值的變化一直是圖譜研究的一個重要內(nèi)容,它為

4、比較許多圖之間的特征值的大小提供了有力的工具,如在給定的圖類中尋找譜半徑達(dá)到最大或最小的極圖.所以繼續(xù)研究圖的變換或運算,尤其是引入新的變換是非常有意義的.
　　 眾所周知,實對稱矩陣的特征值與它主子矩陣的特征值兩者之間存在著緊密的插值關(guān)系,特征值的插值不等式在界定圖的一些不變量中所起的作用是不容忽視的,它們往往能夠方便地給出諸多不變量的估計.
　　 本文圍繞著圖的變換、譜以及插值展開,討論了各種變換對鄰接譜、拉普拉斯譜

5、和規(guī)范拉普拉斯譜(或譜半徑)的影響,如刪點集、賦權(quán)圖降權(quán)變換等,得到了變換后新圖與原圖譜之間的一些插值結(jié)果.特別地,本文重點研究了近年來被頻繁使用的一種變換--“移鄰”變換和它的推廣形式:“重分鄰”變換.主要內(nèi)容如下:
　　 第一章,綜述了移鄰變換已有的相關(guān)結(jié)果,并將圖的移鄰變換推廣,提出了重分鄰變換(見p.9).
　　 第二章,首先推廣了柯西插值的形式,提出了(k1,k1)-嵌入、k-相互嵌入(見p.14)等新概念,并

6、給出了k-相互嵌入的一些性質(zhì).其次,由于圖的鄰接矩陣、拉普拉斯矩陣和規(guī)范拉普拉斯矩陣都是實對稱矩陣,所以本章考慮這樣的問題:兩個同階的實對稱矩陣,在什么樣的條件下它們的特征值具有插值(嵌入)關(guān)系?本章得到了基于實對稱矩陣的若干新的插值(嵌入)結(jié)果,這些結(jié)果可以很自然地推廣到圖的有關(guān)矩陣,這為得到后面的圖的特征值的插值關(guān)系提供了強有力的工具.
　　 第三章,重點研究圖的變換,如移鄰變換、重分鄰變換、刪點集等對圖的譜的影響.首先得到

7、了圖經(jīng)過移鄰或重分鄰變換后,新圖與原圖的譜之間存在著一種插值(嵌入)關(guān)系,即k-相互嵌入,這里的譜可以是鄰接譜、拉普拉斯譜或規(guī)范拉普拉斯譜,同時給出了這種插值關(guān)系的若干應(yīng)用,這些應(yīng)用涉及樹的譜當(dāng)中特征值0或1的重數(shù)；隨后,考慮移鄰變換的一種特殊情況,即移懸鄰對規(guī)范拉普拉斯譜半徑的影響,得到:從v到u的移懸鄰變換中,若u所對應(yīng)的調(diào)和特征向量的分量其絕對值大于v的,則變換后規(guī)范拉普拉斯譜半徑是嚴(yán)格變大的.然后,研究了圖的刪點集變換,刪點集是

8、圖的一種很常見的變換,本章得到了變換后新圖與原圖的拉普拉斯譜之間的一種插值關(guān)系,以及這種插值關(guān)系的若干應(yīng)用,這些應(yīng)用涉及圖的代數(shù)連通度、點連通度及拉普拉斯特征值的上下界,等等.
　　 第四章,研究邊賦權(quán)圖.首先將前面提到的各種插值結(jié)果從簡單圖推廣到邊賦權(quán)圖；其次,研究了邊賦權(quán)圖的降權(quán)變換,得到:對于鄰接譜,變換后新圖與原圖的譜呈k-相互嵌入形式；對于拉普拉斯譜,變換后新圖與原圖的譜呈柯西插值的形式.
　　 第五章,利用柯