重組圖的拉普拉斯譜畢業(yè)論文

1、. . . . 本科畢業(yè)論文題目重組圖的拉普拉斯譜作 者： 唐 晶 專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué)（師）指導(dǎo)教師： 呂 大 梅 完成日期： 2014年5月 南 通 大 學(xué)本 科 畢 業(yè) 論 文題目： 重組圖的拉普拉斯譜 姓 名： 唐 晶 指導(dǎo)教師： 呂 大 梅 專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué)（師） 大學(xué)理學(xué)院2014年5月19 / 22摘 要 設(shè)是一個(gè)頂點(diǎn)集為，邊集為的階簡(jiǎn)單圖。用表示中與之間的邊數(shù)，稱為的鄰接矩陣，矩陣的特征值就稱為的鄰接譜，度矩陣為的頂點(diǎn)度數(shù)構(gòu)成的對(duì)角矩陣。圖的拉普拉斯矩陣定義為：。Laplace矩陣的研究是代數(shù)圖論的重要組成部分。本文著重研究了兩個(gè)完全圖的重組圖的Laplace譜，然

2、后研究了兩個(gè)完全圖的重組圖刪去一條邊所得的圖的Laplace譜，通過(guò)譜之間的比較得出相應(yīng)的結(jié)論，同時(shí)推廣研究了個(gè)完全圖的重組圖的情形。關(guān)鍵詞： Laplace譜，重組圖，完全圖ABSTRACTLet be a simple graph with the vertex set and the edge set .We use to express the number of edges between vertex and of , and call as the adjacency matrix of , view the eigenvalues of as the adjacency spe

3、ctrum of . The degree matrix is the diagonal matrix whose i-th diagonal entry is the degree of vertex i in .The Laplace matrix of is given by . The research on the characteristics value of Laplace matrix , is an important part of algebraic graph theory. In this paper, we study the Laplace spectrum o

4、f the recombinant graph of two complete graphs, and the Laplace spectrum of the recombinant graph of two complete graphs, furthermore, we obtain some results by comparison. Furthermore, we study the Laplace spectrum of the recombinant graph of p complete graphs.Key words:Laplace spectrum, recombinan

5、t graph, complete graph目錄摘要IABSTRACTII目錄III第一章緒論41.1 引言41.2基本概念與已有結(jié)果41.3 本文主要結(jié)果6第二章重組圖的Laplace譜72.1 兩個(gè)完全圖的重組圖的Laplace譜72.2 去掉兩個(gè)完全圖的重組圖中Kk一條邊的情況92.3 去掉兩個(gè)完全圖的重組圖中一條邊的情況122.4 去掉兩個(gè)完全圖的重組圖中與之間的一條邊的情況142.5 個(gè)完全圖的重組圖的情形18第三章歸納19參考文獻(xiàn)20致21第一章 緒 論1.1 引 言圖譜理論的主要目標(biāo)是把圖的重要結(jié)構(gòu)性質(zhì)和它的特征值聯(lián)系起來(lái)，它在圖劃分、排名、網(wǎng)絡(luò)病毒傳播和聚集等方面都有一些應(yīng)用

6、1。圖的特征值的研究是組合數(shù)學(xué)的一個(gè)重要組成部分。從歷史觀點(diǎn)上來(lái)說(shuō)，圖的譜和結(jié)構(gòu)之間的第一個(gè)關(guān)系是在1876年基爾霍夫證明了他著名的矩陣-樹(shù)定理時(shí)發(fā)現(xiàn)的2。圖譜理論的主要原理是把圖的重要不變量和圖譜聯(lián)系起來(lái)。通常，像色數(shù)和獨(dú)立數(shù)這樣難以計(jì)算的不變量，用含特征值的表達(dá)式比較它們是很有效的。在1 中，也給出一些圖譜和它的結(jié)構(gòu)的關(guān)系以與這些關(guān)系在圖劃分、排名、網(wǎng)絡(luò)病毒傳播和聚集等領(lǐng)域的一些實(shí)際應(yīng)用。對(duì)于圖的特征值的其他應(yīng)用，可參見(jiàn)1，3，4，5。更多圖的特征值的結(jié)果，可以看Cevtkovic et al.的專著6，7(鄰接矩陣的特征值)，Mohar的綜述8（拉普拉斯矩陣的特征值），Godsil和Ro

7、yle的專著9（鄰接矩陣和拉普拉斯矩陣的特征值）或者是Chung的書(shū)10（標(biāo)準(zhǔn)拉普拉斯矩陣的特征值）。1.2基本概念與已有結(jié)果下面是一些相關(guān)定義：定義1.1：既無(wú)環(huán)邊也無(wú)重邊的圖稱為簡(jiǎn)單圖。定義1.2：任意兩點(diǎn)間都有一條邊的簡(jiǎn)單圖稱為完全圖，階完全圖記為。定義1.3：設(shè)簡(jiǎn)單圖都包含一個(gè)子圖與圖同構(gòu)，把的頂點(diǎn)看成是一樣的，所得的簡(jiǎn)單圖稱為基于的重組圖，記為。定義1.4：由一個(gè)圖刪去其頂點(diǎn)的子集,同時(shí)刪去他們關(guān)聯(lián)的邊所得的圖，稱為這個(gè)圖的誘導(dǎo)子圖。定義1.5：設(shè)圖為簡(jiǎn)單圖，即圖不包含重邊與環(huán)，的頂點(diǎn)集為，頂點(diǎn)的度為，的鄰接矩陣為是一個(gè)實(shí)對(duì)稱矩陣，定義如下：，當(dāng)時(shí)，如果頂點(diǎn)與相鄰，則，否則。定義1.

8、6：圖G的Laplace矩陣定義為：,其中為的頂點(diǎn)度數(shù)構(gòu)成的對(duì)角矩陣，稱為度矩陣。定義1.7：矩陣的特征值是使得存在一個(gè)非零向量解為。每一個(gè)非零解稱為對(duì)應(yīng)特征值的特征向量。Laplace矩陣的所有特征值稱為圖的拉普拉斯（Laplace）譜。下給出幾個(gè)簡(jiǎn)單圖的拉普拉斯譜11。l 完全圖的拉普拉斯譜： 一個(gè)n-1，n-1個(gè)-1；l 完全二部圖的拉普拉斯譜：一個(gè)0，n-1個(gè)m，m-1個(gè)n，一個(gè)m+n；l 圈的拉普拉斯譜：2-2； 路的拉普拉斯譜：2-2。拉普拉斯算子矩陣的特征值按遞增順序列出：。和是的兩個(gè)頂點(diǎn)且，從中刪除行和列得到矩陣。定理1.1（矩陣-樹(shù)定理）2如果和是連通圖的兩個(gè)頂點(diǎn)且，則的生成

9、樹(shù)的數(shù)目等于的絕對(duì)值。另外，的生成樹(shù)的數(shù)目等于。由矩陣-樹(shù)定理可知：當(dāng)且僅當(dāng)是連通的，據(jù)此，M.Fiedler稱為的代數(shù)連通度，記為12。現(xiàn)在我們列出圖的拉普拉斯矩陣的特征值的一些簡(jiǎn)單性質(zhì)51，第14章。定理1.21 設(shè)為一個(gè)簡(jiǎn)單圖。則的拉普拉斯矩陣為半正定矩陣。的拉普拉斯算子的最小特征值等于0，它的重?cái)?shù)等于的連通分支數(shù)目。圖是連通的當(dāng)且僅當(dāng)。定理1.31設(shè)為一任意n階圖，。RMerris給出圖與其補(bǔ)圖Laplace譜之間的關(guān)系如下：定理1.41 若的Laplace譜為，則，。定理1.5 1 若為偶圖，為的線圖，的Laplace譜為，的鄰接譜為，若，則，。1.3 本文主要結(jié)果本文著重研究了兩個(gè)

10、完全圖的重組圖的Laplace譜，然后研究了兩個(gè)完全圖的重組圖刪去一條邊所得的圖的Laplace譜，通過(guò)譜之間的比較得出相應(yīng)的結(jié)論，同時(shí)推廣研究了個(gè)完全圖的重組圖的情形。第二章 重組圖的Laplace譜2.1 兩個(gè)完全圖的重組圖的Laplace譜設(shè)為Kk的頂點(diǎn)集。為連同共有個(gè)點(diǎn)的完全圖，其頂點(diǎn)集記為，為連同共有個(gè)點(diǎn)的完全圖，其頂點(diǎn)集記為。設(shè)表示完全圖和在Kk基礎(chǔ)上的重組圖，即=（，；Kk），其中：。定理2.1.1，設(shè)重組圖=（，；Kk）的Laplace譜為,則。證明：圖的鄰接矩陣為,其中：，1代表全1矩陣，0代表全0矩陣，其中：。度矩陣=,其中：，Laplace矩陣的特征多項(xiàng)式為根據(jù)行列式的定

11、義可以得到：從而得重組圖=（，；Kk）的Laplace譜為2.2去掉兩個(gè)完全圖的重組圖中Kk一條邊的情況定理2.2.1，設(shè)重組圖為去掉Kk一條邊的所得到的圖，其Laplace譜為，則。證明：圖的鄰接矩陣為,其中：，度矩陣為=,其中：，Laplace矩陣為的特征多項(xiàng)式為根據(jù)行列式的定義可以得到從而得重組圖的Laplace譜為2.3 去掉兩個(gè)完全圖的重組圖中一條邊的情況定理2.3.1，設(shè)重組圖為去掉中一條邊所得到的圖，其Laplace譜為，則。證明：圖的鄰接矩陣為，其中：，度矩陣為其中：，Laplace矩陣為的特征多項(xiàng)式為根據(jù)行列式的定義可以得到從而得重組圖的Laplace譜為2.4 去掉兩個(gè)完全

12、圖的重組圖中與之間的一條邊的情況定理2.4.1，設(shè)重組圖為去掉與之間一條邊所得到的圖，其Laplace譜為，則重組圖的Laplace譜為：1個(gè)0，個(gè)，個(gè)，個(gè)，。證明：圖的鄰接矩陣為，其中：，度矩陣Laplace矩陣=其中：=所以令并進(jìn)行如下計(jì)算：根據(jù)根的存在性定理可知：和之間至少存在一個(gè)根，和之間至少存在一個(gè)根綜上：重組圖的Laplace譜為：1個(gè)0，個(gè)，個(gè)，個(gè)，。2.5個(gè)完全圖的重組圖的情形由兩個(gè)完全圖的重組圖Laplace譜的變化情況，我們可以推廣得到個(gè)完全圖的重組圖的情形。定理4.1，設(shè)重組圖的Laplace譜為,則譜為：1個(gè)0，1個(gè)，個(gè)，個(gè)，個(gè)，個(gè)個(gè)。定理4.2，設(shè)重組圖為去掉Kk一條

13、邊的所得到的圖，則其Laplace譜為：其中包括1個(gè)0，1個(gè)，1個(gè)，個(gè)，個(gè)，個(gè)，個(gè)個(gè)。定理4.3，設(shè)重組圖為去掉中一條邊所得到的圖，則其Laplace譜為：1個(gè)0，1個(gè)，1個(gè)，個(gè)，個(gè)，個(gè)，個(gè)個(gè)。定理4.4，設(shè)重組圖為去掉與之間一條邊所得到的圖，其Laplace譜為，則重組圖的Laplace譜為：1個(gè)0，個(gè)，個(gè)，個(gè)，個(gè)個(gè)，。第三章歸 納特征值下表是各種情況下重組圖的拉普拉斯譜個(gè)數(shù)分布的情況：不同情況個(gè)數(shù)0不去邊1100無(wú)無(wú)無(wú)去邊1110無(wú)無(wú)無(wú)去邊1101無(wú)無(wú)無(wú)與間去邊1無(wú)無(wú)無(wú)111通過(guò)上表，我們可以發(fā)現(xiàn)：1.比較定理2.1.1和定理2.2.1，去掉重組圖中一條邊，重組圖的譜半徑和代數(shù)連通度均未發(fā)

14、生改變，只是定理2.2.1比定理2.1.1增加了這個(gè)特征值，與特征值的重?cái)?shù)發(fā)生了改變。2.比較定理2.1.1和定理2.3.1，去掉重組圖中一條邊，重組圖的代數(shù)連通度未發(fā)生改變，譜半徑發(fā)生了變化，需要根據(jù)和的大小來(lái)確定。3.比較定理2.1.1和定理2.4.1，去掉重組圖中與之間的一條邊，重組圖的譜半徑不變，代數(shù)連通度發(fā)生改變，有三個(gè)特征值的大小較難確定，只能給出大概的圍。參考文獻(xiàn)1 M. Dehmer .Structural Analysis of Complex NetworksM. Springer Science+Business Media.2Kirchhoff G.U ber die

15、Auflosung der Gleichungen auf welche man bei der Untersuchungder Linearen Vertheilung galvanischer Strome gefuhrt wirdJ.Ann Phys Chem, 1847,72:497508.3Krivelevich M, Sudakov B.Pseudo-random graphsJ. More sets, graphs and numbers.Bolyai Society Mathematical Studies, 2006,vol 15: 199262.4van Dam E, Ha

16、emers W. Which graphs are determined by their spectrum?J.Lin AlgebraAppl,2003,373:241272.5 van Dam E, Haemers W. Developments on spectral characterization of graphsJ. DiscreteMath,2009,309:576586.6Cvetkovic D, Doob M, Sachs H. Spectra of graphs theory and applicationJ.Academic,New York, 3rd edn, 199

17、5.7 Cvetkovic D, Rowlinson P, Simic S. Eigenspaces of graphsM. CambridgeUniversity Press: Cambridge,1997.8 Mohar B. Some applications of Laplace eigenvalues of graphsM. Hahn G, Sabidussi G(eds) Graph symmetry: Kluwer, Dordrecht,1997,225275.9 Godsil CD, Royle G. Algebraic graph theoryM. Berlin:Springer,2001.10 ChungFRK.Spectral graph theoryM. Ameri