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

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

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

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

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

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

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

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

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