【正文】 本 科 畢 業(yè) 論 文 題 目 重組圖的拉普拉斯譜 作 者 ： 唐 晶 專 業(yè) ： 數(shù)學(xué)與應(yīng)用數(shù)學(xué)（師范） 指導(dǎo)教師 ： 呂 大 梅 完成日期 ： 20xx 年 5 月 南 通 大 學(xué) 本 科 畢 業(yè) 論 文 題目： 重組圖的拉普拉斯譜 姓 名： 唐 晶 指導(dǎo)教師： 呂 大 梅 專 業(yè)： 數(shù)學(xué)與應(yīng)用數(shù)學(xué)（師范） 南通大學(xué)理學(xué)院 20xx 年 5 月 南通大學(xué)畢業(yè)論文 I 摘 要 設(shè) ? ?EVG ,? 是一個(gè)頂點(diǎn)集為 },{ 21 nvvvV ?? ，邊集為 ??GE 的 n 階簡(jiǎn)單圖。用 ija 表示 G 中 iv 與 jv 之間的邊數(shù)，稱 ? ? nnijaGA ?? )( 為 G 的鄰接矩陣，矩陣 ??GA 的特征值就稱為G 的鄰接譜，度矩陣 ? ?GD 為 G 的頂點(diǎn)度數(shù)構(gòu)成的對(duì)角矩陣。圖 G 的拉普拉斯矩陣定義為：? ? ? ? ? ?GAGDGL ?? 。 Laplace 矩陣的研究是代數(shù)圖論的重要組成部分 。 本文著重研究了兩個(gè)完全圖的重組圖的 Laplace 譜，然后研究了兩個(gè)完全圖的重組圖刪去一條邊所得的圖的 Laplace 譜，通過譜之間的比較得出相應(yīng)的結(jié)論，同時(shí)推廣研究了p 個(gè)完全圖的重組圖的情形。 關(guān)鍵詞： Laplace 譜，重組圖，完全圖 南通大學(xué)畢業(yè)論文 II ABSTRACT Let ),( EVG? be a simple graph with the vertex set },{ 21 nvvvV ?? and the edge set )(GE . We use ija to express the number of edges between vertex iv and jv of G , and call nnijaGA ?? )()( as the adjacency matrix of G , view the eigenvalues of )(GA as the adjacency spectrum of G . The degree matrix )(GD is the diagonal matrix whose ith diagonal entry is the degree of vertex i in G . The Laplace matrix of G is given by )()()( GAGDGL ?? . The research on the characteristics value of Laplace matrix )(GL , is an important part of algebraic graph theory. In this paper, we study the Laplace spectrum of the rebinant graph of two plete graphs, and the Laplace spectrum of the rebinant graph of two plete graphs, furthermore, we obtain some results by parison. Furthermore, we study the Laplace spectrum of the rebinant graph of p plete graphs. Key words: Laplace spectrum, rebinant graph, plete graph 南通大學(xué)畢業(yè)論文 III 目錄 摘 要 ............................................... I ABSTRACT .............................................. II 目錄 .................................................. III 第一章 緒 論 ........................................... 4 引 言 ........................................... 4 基本概念及已有結(jié)果 ................................. 4 本文主要結(jié)果 ...................................... 6 第二章 重組圖的 Laplace 譜 ................................ 7 兩個(gè)完全圖的重組圖的 Laplace 譜 ....................... 7 去掉兩個(gè)完全圖的重組圖中 Kk內(nèi)一條邊的情況 .............. 9 去掉兩個(gè)完全圖的重組圖中 kn KK ?1內(nèi)一條邊的情況 ......... 12 去掉兩個(gè)完全圖的重組圖中 kK 與 kn KK ?1之間的一條邊的情況 .. 14 p 個(gè)完全圖的重組圖的情形 ........................... 18 第三章 歸 納 .......................................... 19 參考文獻(xiàn) .................................. 錯(cuò)誤 !未定義書簽。 致 謝 ................................................ 21 南通大學(xué)畢業(yè)論文 4 第一章 緒 論 引 言 圖譜 理論的主要目標(biāo)是把圖的重 要結(jié)構(gòu)性質(zhì)和它的特征值聯(lián)系起來，它 在圖劃分 、 排名 、網(wǎng)絡(luò)病毒傳播和聚集等方面 都有一些 應(yīng)用 [1]。 圖的特征值的研究是組合數(shù)學(xué)的一個(gè)重要組成部分 。 從歷史觀點(diǎn)上來說 ， 圖的譜和結(jié)構(gòu)之間的第一個(gè)關(guān)系是在 1876 年基爾霍夫證明了他著名的矩陣 樹定理時(shí)發(fā)現(xiàn)的 [2]。圖 譜 理論的主要原理是把圖的重要不變量和圖譜聯(lián)系起來。通常，像色數(shù)和獨(dú)立數(shù)這樣難以計(jì)算的不變量，用含特征值的表達(dá)式比較它們是很有效的。在 [1 ]中， 也 給出一些圖譜和它的結(jié)構(gòu)的關(guān)系以及這些關(guān)系在圖劃分、排名、網(wǎng)絡(luò)病毒傳播和聚集等領(lǐng)域的一些實(shí)際應(yīng)用。對(duì)于圖的特征值的 其他應(yīng)用， 可參見 [1， 3， 4， 5]。更多圖的特征值的 結(jié)果 ，可以看 Cevtkovic et 著 [6， 7](鄰接矩陣的特征值 )， Mohar 的綜述 [8]（拉普拉斯矩陣 的特征值）， Godsil 和 Royle的專著 [9]（鄰接矩陣和拉普拉斯 矩陣 的特征值）或者是 Chung 的書 [10]（標(biāo)準(zhǔn)拉普拉斯矩陣的特征值） 。 基本概念及已有結(jié)果 下面是一些相關(guān)定義： 定義 ： 既無環(huán)邊也無重邊的圖稱為 簡(jiǎn)單圖 。 定義 ： 任意 兩點(diǎn)間都有一條邊的簡(jiǎn)單圖稱為 完全圖 ， n 階完全 圖記為 nK 。 定義 ： 設(shè)簡(jiǎn)單圖 )2(, 21 ?pGGG p? 都包含一個(gè)子圖與圖 0G 同構(gòu)，把 pGGG , 21 ? 的頂點(diǎn)看 成是 一樣 的， 所得 的簡(jiǎn) 單圖 G 稱為 pGGG , 21 ? 基于 0G 的 重組圖 ， 記為),。( 210 pGGGGAG ?? 。 定義 ： 由一個(gè)圖刪去其頂點(diǎn) 的子集 ,同時(shí)刪去他們關(guān)聯(lián)的邊所得的圖，稱為這個(gè)圖 的誘導(dǎo)子圖 。 定義 ： 設(shè)圖 ),( EVG? 為簡(jiǎn)單圖 ， 即圖 G 不包含重邊與環(huán)， G 的 頂點(diǎn)集為 },{ 1 nvvV ?? ，頂點(diǎn)的度為 nddd , 21 ? ， G 的 鄰接矩陣 為 nnijaGA ?? )()( 是一個(gè)實(shí)對(duì)稱矩陣，定義如下：0?iia ),2,1( ni ?? ，當(dāng) ji? 時(shí)，如果頂點(diǎn) iv 與 jv 相鄰，則 1?ija ，否則 0?ija 。 定義 ： 圖 G 的 Laplace 矩陣 定義為： )()()( GAGDGL ?? ,其中 (GD 為 G 的頂點(diǎn)度南通大學(xué)畢業(yè)論文 5 數(shù)構(gòu)成的對(duì)角矩陣 ，稱為 度矩陣 。 定義 ： 矩陣 A 的特征值是 使得 XAX ?? 存在一個(gè)非零向量解 為 ? 。每一個(gè)非零解稱為對(duì)應(yīng)特征值 ? 的特征向量。 Laplace 矩陣 )(GL 的所有特征值稱為圖 G 的 拉普拉斯（ Laplace）譜。 下給出幾個(gè)簡(jiǎn)單圖的拉普拉斯譜 [11]。 ? 完全圖的拉普拉斯譜 ： 一個(gè) n1， n1 個(gè) 1； ? 完全 二部 圖的拉普拉斯譜 ：一個(gè) 0， n1 個(gè) m， m1 個(gè) n，一個(gè) m+n； ? 圈 的拉普拉斯譜 ： 22 1,1,0,2c o s ?? n