淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0707201115065200
中文論文名稱 圖的特徵多項式之探討
英文論文名稱 The study of the characteristic polynomial of graphs
校院名稱 淡江大學
系所名稱(中) 中等學校教師在職進修數學教學碩士學位班
系所名稱(英) Executive Master's Program In Mathematics for Teachers
學年度 99
學期 2
出版年 100
研究生中文姓名 李明峯
研究生英文姓名 Ming-Feng Li
學號 798190095
學位類別 碩士
語文別 中文
口試日期 2011-06-18
論文頁數 40頁
口試委員 指導教授-高金美
委員-周兆智
委員-傅睎M
中文關鍵字 鄰接矩陣  行列式  遞迴關係  特徵多項式 
英文關鍵字 adjacency matrix  determinant  recursive relation  characteristic polynomial 
學科別分類
中文摘要 假設A是n階方陣,A的特徵多項式為p(A,x)=det(xI-A),其中I是n階單位方陣。令G為一含有n個點的簡單圖且A(G)為圖G的鄰接矩陣, 我們稱A(G)的特徵多項式為G的特徵多項式,記為p(G,x)=det(xI-A(G)),其中I是n階單位方陣。
在本論文中我們直接計算出完全圖與星圖的特徵多項式,對於路徑與迴圈我們可得其遞迴關係式;由前面的計算我們得到行列式的化簡與圖之間的關係,推導出圖中含有degree 1的點或含有degree 2的點及含有一個橋的特徵多項式,可經由子圖的特徵多項式而獲得。我們利用已經獲得的結果,推得一些特殊圖的特徵多項式或其遞迴關係式。
英文摘要 Let A be a matrix of order n. The characteristic polynomial of A is p(A)=det(xI-A) where I is the identity matrix of order n. Let G be a simple graph and A(G) is the adjacency matrix of G. We call the characteristic polynomial of A(G) is the characteristic polynomial of G, denoted by p(G)=det(xI-A(G)), where I is the identity matrix of order n.
In this thesis, we directly calculate the characteristic polynomial of complete graphs and star graphs. For paths and cycles, we get the recurrence relation of their characteristic polynomial. From the above calculation, we obtain the relation between the simplification of determinants and their subgraphs. We get the characteristic polynomials of the graph with a vertex of degree 1, a vertex of degree 2, or a bridge by the characteristic polynomial of their subgraphs. We use these results to get the characteristic polynomial of some special graphs directly or from the recurrence relation.
論文目次 目錄
第一章 簡介……………………………………………………………1
第二章 預備知識………………………………………………………3
第三章 主要內容………………………………………………………10
第一節 特殊圖的特徵多項式………………………………………10
第二節 圖的特徵多項式……………………………………………19
參考文獻 ………………………………………………………………40
圖目錄
圖1 ……………………………………………………………………3
圖2 ……………………………………………………………………4
圖3 ……………………………………………………………………4
圖4 ……………………………………………………………………5
圖5 ……………………………………………………………………5
圖6 ……………………………………………………………………6
圖7 ……………………………………………………………………6
圖8 ……………………………………………………………………11
圖9 ……………………………………………………………………13
圖10 ……………………………………………………………………14
圖11 ……………………………………………………………………16
圖12 ……………………………………………………………………19
圖13 ……………………………………………………………………21
圖14 ……………………………………………………………………24
圖15 ……………………………………………………………………26
圖16 ……………………………………………………………………28
圖17 ……………………………………………………………………31
圖18 ……………………………………………………………………33
圖19 ……………………………………………………………………35
圖20 ……………………………………………………………………37
圖21 ……………………………………………………………………37
圖22 ……………………………………………………………………37
圖23 ……………………………………………………………………38
參考文獻 參考文獻:
[1] D. Cvetković, M. Doob, and H. Sachs, Spectra of Graph, Academic Press, New York, 1980.
[2] D.B. West, Graph Theory, 2001.
[3] Shang-wang Tan, Jiming Guo, The largest eigenvalue on tree,Journal of the University of Petrolum(Edition of Natural Science) , China, 2002, 26(6) : 113-117.
[4] Shang-wang Tan, On formulas calculating the characteristic polynomial of matrices in graph theory, Pure and AppliedMathematics, 2009, 25(2).
[5] Shang-wang Tan, Jian Qi, Jiming Guo, TECHNIQUES ON
COMPUTING CHARACTERISTIC POLYNOMIALS ABOUTDIGRAPHS AND COMPLEMENTS OF WEAKLY REGULAR DIGRAPHS, Pure and Applied Mathematics, 2000, 20(4).

論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2013-07-18公開。
  • 同意授權瀏覽/列印電子全文服務,於2013-07-18起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信