【正文】 ........................ 6 第二章 重組圖的 Laplace 譜 ................................ 7 兩個完全圖的重組圖的 Laplace 譜 ....................... 7 去掉兩個完全圖的重組圖中 Kk內(nèi)一條邊的情況 .............. 9 去掉兩個完全圖的重組圖中 kn KK ?1內(nèi)一條邊的情況 ......... 12 去掉兩個完全圖的重組圖中 kK 與 kn KK ?1之間的一條邊的情況 .. 14 p 個完全圖的重組圖的情形 ........................... 18 第三章 歸 納 .......................................... 19 參考文獻 .................................. 錯誤 !未定義書簽。圖 G 的拉普拉斯矩陣定義為：? ? ? ? ? ?GAGDGL ?? 。通常，像色數(shù)和獨立數(shù)這樣難以計算的不變量，用含特征值的表達式比較它們是很有效的。 定義 ： 由一個圖刪去其頂點 的子集 ,同時刪去他們關聯(lián)的邊所得的圖，稱為這個圖 的誘導子圖 。 拉普拉斯算子矩陣 )(GL 的特征值按遞增順序列出： )()()( 21 GGG n??? ??? ?。 )(ii G 的拉普拉斯算子的最小特征值 )(1G? 等于 0，它的重數(shù)等于 G 的連通分支數(shù)目。設 nG 表示完全圖1nK和2nK在 Kk 基礎上的重組圖，即 nG =（1nK，2nK； Kk），其中： knnn ??? 21 。,(21 knnn KKKG ?去掉 kK 與 kn KK ?1之間 一條邊所得到的圖，其 Laplace 譜為 n??? ?, 21 ，則 重組圖 nH 的 Laplace 譜為 ： 1 個 0， )1( ?k 個 n ， )2( 1 ??kn 個1n ， )1( 2 ??kn 個 2n ， kk ??? 11 ? ， 121 2 nn ??? ? ， nn ??? 31 ? 。,(321 knnnn KKKKKG p??去掉 kn KK ?1中一條邊所得到的圖，則其 Laplace 譜 n??? ?, 21 為： 1 個 0， 1 個 k ， 1 個 21?n ， k 個 n ， )1( 1 ??kn 個 1n ， )1( 2 ??kn個 2n ， )1( 3 ??kn 個 ?,3n )1( ??knp 個 pn 。sung der Gleichungen auf welche man bei der Untersuchung der Linearen Vertheilung galvanischer Str168。在此，我向她表示我最真摯的感謝與真誠的敬意。特征值 個數(shù) 不同情況 南通大學畢業(yè)論文 20 參考文獻 [1] M. Dehmer . Structural Analysis of Complex Networks[M]. Springer Science+Business Media. [2] Kirchhoff G. U168。,(321 knnnn KKKKKG p??去掉 Kk 內(nèi) 一條邊的所得到的圖， 則 其Laplace 譜 n??? ?, 21 為：其中包括 1 個 0， 1 個 k ， 1 個 2?n ， )2( ?k 個 n ， )1( 1 ??kn 個 1n ，)1( 2 ??kn 個 2n ， )1( 3 ??kn 個 ?,3n )1( ??knp 個 pn 。,(21 knnn KKKG ?去掉 kn KK ?1中一條邊所得到的圖，其 Laplace譜為 n??? ?, 21 ，則 543541321 ,2,0 ??? ????????? kkk nnk ???????? ? 214312 111 , nn nnnn ??????? ???? ???? ?? 。 南通大學畢業(yè)論文 7 第二章 重組圖的 Laplace 譜 兩個完全圖的重組圖的 Laplace 譜 設 ? ?kvvU ,....,1? 為 Kk 的頂點集。 定理 [1] 設 G 為一個 簡單 圖。 下給出幾個簡單圖的拉普拉斯譜 [11]。 定義 ： 設簡單圖 )2(, 21 ?pGGG p? 都包含一個子圖與圖 0G 同構，把 pGGG , 21 ? 的頂點看 成是 一樣 的， 所得 的簡 單圖 G 稱為 pGGG , 21 ? 基于 0G 的 重組圖 ， 記為),。 從歷史觀點上來說 ， 圖的譜和結(jié)構之間的第一個關系是在 1876 年基爾霍夫證明了他著名的矩陣 樹定理時發(fā)現(xiàn)的 [2]。 本 科 畢 業(yè) 論 文 題 目 重組圖的拉普拉斯譜 作 者 ： 唐 晶 專 業(yè) ： 數(shù)學與應用數(shù)學（師范） 指導教師 ： 呂 大 梅 完成日期 ： 20xx 年 5 月 南 通 大 學 本 科 畢 業(yè) 論 文 題目： 重組圖的拉普拉斯譜 姓 名： 唐 晶 指導教師： 呂 大 梅 專 業(yè)： 數(shù)學與應用數(shù)學（師范） 南通大學理學院 20xx 年 5 月 南通大學畢業(yè)論文 I 摘 要 設 ? ?EVG ,? 是一個頂點集為 },{ 21 nvvvV ?? ，邊集為 ??GE 的 n 階簡單圖。 圖的特征值的研究是組合數(shù)學的一個重要組成部分 。 定義 ： 任意 兩點間都有一條邊的簡單圖稱為 完全圖 ， n 階完全 圖記為 nK 。 Laplace 矩陣 )(GL 的所有特征值稱為圖 G 的 拉普拉斯（ Laplace）譜。 現(xiàn)在我們列出圖的拉普拉斯矩陣的特征值的一些簡單性質(zhì) 5[1，第 14 章 ]。 本文主要結(jié)果 本文著重研究了兩個完全圖的重組圖的 Laplace 譜，然后研究了兩個完全圖的重組圖刪去一條邊所得的圖的 Laplace 譜 ，通過譜之間的比較得出相應的結(jié)論，同時推廣研究了 p 個完全圖的重組圖的情形。 證明： 圖 nH 的鄰接矩陣為?????????????knknknAAAHA2101 0111)( ,其中： 南通大學畢業(yè)論文 10 iiiA??????????????????????????0110111111111111011111111110110111111111111110110???????????????， knkni ??? 21 , ，?????????????????0111101111001100?????????kA 度矩陣為 )( nHD =????????????knknkDDD2100 0000 ,其中： iiinnnnnnnD???????????????????????????????????1000000010000000100000001000000010000000100000001???????????????， knkni ??? 21 , ?????????????????????1000010000200002nnnnD k????????? Laplace 矩陣為 ????????????????????????????????????????????????????????????????