【正文】 定義 ： 由一個(gè)圖刪去其頂點(diǎn) 的子集 ,同時(shí)刪去他們關(guān)聯(lián)的邊所得的圖，稱為這個(gè)圖 的誘導(dǎo)子圖 。 基本概念及已有結(jié)果 下面是一些相關(guān)定義： 定義 ： 既無(wú)環(huán)邊也無(wú)重邊的圖稱為 簡(jiǎn)單圖 。通常，像色數(shù)和獨(dú)立數(shù)這樣難以計(jì)算的不變量，用含特征值的表達(dá)式比較它們是很有效的。 致 謝 ................................................ 21 南通大學(xué)畢業(yè)論文 4 第一章 緒 論 引 言 圖譜 理論的主要目標(biāo)是把圖的重 要結(jié)構(gòu)性質(zhì)和它的特征值聯(lián)系起來(lái)，它 在圖劃分 、 排名 、網(wǎng)絡(luò)病毒傳播和聚集等方面 都有一些 應(yīng)用 [1]。圖 G 的拉普拉斯矩陣定義為：? ? ? ? ? ?GAGDGL ?? 。用 ija 表示 G 中 iv 與 jv 之間的邊數(shù)，稱 ? ? nnijaGA ?? )( 為 G 的鄰接矩陣，矩陣 ??GA 的特征值就稱為G 的鄰接譜，度矩陣 ? ?GD 為 G 的頂點(diǎn)度數(shù)構(gòu)成的對(duì)角矩陣。 關(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ò)誤 !未定義書(shū)簽。圖 譜 理論的主要原理是把圖的重要不變量和圖譜聯(lián)系起來(lái)。更多圖的特征值的 結(jié)果 ，可以看 Cevtkovic et 著 [6， 7](鄰接矩陣的特征值 )， Mohar 的綜述 [8]（拉普拉斯矩陣 的特征值）， Godsil 和 Royle的專(zhuān)著 [9]（鄰接矩陣和拉普拉斯 矩陣 的特征值）或者是 Chung 的書(shū) [10]（標(biāo)準(zhǔn)拉普拉斯矩陣的特征值） 。( 210 pGGGGAG ?? 。 定義 ： 矩陣 A 的特征值是 使得 XAX ?? 存在一個(gè)非零向量解 為 ? 。 ? 完全圖的拉普拉斯譜 ： 一個(gè) n1， n1 個(gè) 1； ? 完全 二部 圖的拉普拉斯譜 ：一個(gè) 0， n1 個(gè) m， m1 個(gè) n，一個(gè) m+n； ? 圈 的拉普拉斯譜 ： 22 1,1,0,2c o s ?? njn j ?? ； 路 的拉普拉斯譜 ： 22 1,1,0,c o s ?? njnj ?? 。另外， G 的生成樹(shù)的數(shù)目等于 n n???2 。則 )(i G 的拉普拉斯矩陣為半正定矩陣。 R． Merris 給 出圖與其補(bǔ)圖 Laplace 譜之間的關(guān)系如下： 定理 [1] 若 G 的 Laplace 譜為 0)()()()( 121 ????? ? GGGG nn ???? ?，則 nGG cini ?? ? )()( ?? ， 1,2,1 ?? ni ? 。1nK為連同 kvvv ,......, 21 共有 1n 個(gè)點(diǎn)的完全圖，其頂點(diǎn)集記為 1U ，2nK為連同 kvvv ,......, 21 共有 2n 個(gè)點(diǎn)的完全圖，其頂點(diǎn)集記為 2U 。 度矩陣 )( nGD =????????????knknkDDD2100 0000 ,其中： iiinnnnnnnD???????????????????????????????????1000000010000000100000001000000010000000100000001???????????????， knknki ??? 21 , Laplace 矩陣 南通大學(xué)畢業(yè)論文 8 ???????????????????????????????????????????????111101011111111111)()()(2211nnnnnnGAGDGLnnn??????????????? )( nGL 的特征多項(xiàng)式為 111111111010111111111111111111111)(222111???????????????????nnnnnnnnnGLn???????????????????????????????111122221 1 1 1 1 1 1 1 10 0 0 0 0 0 00 0 0 0 0 0 0 01 1 1 1 1 1 0 0 00 0 0 0 0 0 0=0 0 0 0 0 0 0 01 1 1 0 0 0 1 1 10 0 0 0 0 0 00 0 0 0 0 0 0 0nnnnn