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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0607201116300000
中文論文名稱 樹的特徵值譜的探討
英文論文名稱 The study of the spectrum for eigenvalues of trees
校院名稱 淡江大學
系所名稱(中) 中等學校教師在職進修數學教學碩士學位班
系所名稱(英) Executive Master's Program In Mathematics for Teachers
學年度 99
學期 2
出版年 100
研究生中文姓名 莊銘宏
研究生英文姓名 Ming-Hung Chuang
學號 798190046
學位類別 碩士
語文別 中文
口試日期 2011-06-18
論文頁數 43頁
口試委員 指導教授-高金美
委員-傅恒霖
委員-黃文中
委員-高金美
中文關鍵字 匹配  最大匹配  完美匹配  幾乎完美匹配 
英文關鍵字 matching  maximum matching  perfect matching  nearly perfect matching 
學科別分類
中文摘要 在圖G=(V,E)中,由E中不共用頂點的邊所成的集合稱為G的一個匹配,含有邊數最多的匹配稱為G的最大匹配。一個最大匹配的個數稱為G的匹配數。令M是G的一個最大匹配。如果G的每個頂點都可以在M中找到一個以其為端點的邊,則稱M是G的一個完美匹配,此時2|M|=|V(G)|。如果存在唯一一個點無法在M中找到一個以其為端點的邊,則稱M是G的一個幾乎完美匹配,此時2|M|+1=|V(G)|。一個不含迴路的連通圖,稱為樹。在本論文中我們探討具有幾乎完美匹配的所有樹的鄰接矩陣和Laplacian矩陣的最大特徵值的上界和下界,首先,我們找出8個具有幾乎完美匹配的樹,且其最大特徵值可能為最大者,經由計算它們的特徵多項式及最大特徵值,而得到了具有幾乎完美匹配的所有樹的最大特徵值的上界及下界。
英文摘要 Let G=(V,E) be a graph. A set of pairwise vertex disjoint edges of G is called a matching of G. A matching of maximum cardinality is called a maximum matching of G. The cardinality of a maximum matching of G is called the matching number of G. Let M be a maximum matching of G. If every vertex of G is saturated by M, then we call M a perfect matching of G, i.e. 2|M|=|V(G)|. If there exists only one vertex not saturated by M, then we call M a nearly perfect matching of G, i.e. 2|M|+1=|V(G)|.
In this thesis, we mainly discuss an upper bound and a lower bound of the largest adjacency eigenvalues and Laplacian eigenvalues of trees with nearly perfect matchings. First we find eight trees which may contain the maximum of the largest eigenvalue of all trees with a nearly perfect matching. We calculate the characteristic polynomials and eigenvalues of their adjacency matrices and Laplacian matrices separately. We get an upper bound and a lower bound of trees with nearly perfect matchings from there.
論文目次 目錄
第一章 簡介………………………………………………………………1
第二章 預備知識…………………………………………………………3
第三章 主要內容…………………………………………………………7
第一節 T1n,…,T6n的特徵多項式…………………………………9
第二節 T1n,…,T6n的最大特徵值……………………………….15
第三節 T7n、T8n的特徵多項式及最大特徵值…………………….20
第四節 T1n,…,T6n的Laplacian特徵多項式……………………23
第五節 T1n,…,T6n的最大Laplacian特徵值……………………34
第六節 T7n、T8n的Laplacian特徵多項式及其最大特徵值………40
參考文獻…………………………………………………………………43
圖表目錄
圖1…………………………………………………………………………3
圖2…………………………………………………………………………3
圖3…………………………………………………………………………4
圖4…………………………………………………………………………4
圖5…………………………………………………………………………5
圖6…………………………………………………………………………5
圖7…………………………………………………………………………7
圖8…………………………………………………………………………8
圖9…………………………………………………………………………9
圖10………………………………………………………………………20
圖11………………………………………………………………………21
圖12………………………………………………………………………21
圖13………………………………………………………………………24

參考文獻 參考文獻

[1] Y. Chen, Properties of spectra of graphs and line graphs, Appl. Math. J. Chinese Univ. Ser. B, 17(3):371-376, 2002.
[2] D. Cvetković, M. Doob and H. Sachs, Spectra of Graph, Academic Press, New York, 1980.
[3] Jiming Guo, On the second largest Laplacian eigenvalue of trees, Linear Algebra Appl., 2005, 404:251-261.
[4] Yaoping Hou and Jiongsheng Li, Bounds on the largest eigenvalues of trees with a given size of matching, Linear Algebra Appl.,2002,342:203-217.
[5] Shang-wang Tan and Jiming Guo, The largest eigenvalue on tree, Journal of the University of Petrolum(Edition of Natural Science), China, 2002, 26(6) : 113117 .
[6] Shang-wang Tan, On the new upper bounds of spectral radius of trees given edge independence number, Journal of Guangxi University of Technology, 2008, 19(1):13-17.
[7] Guanghui Xu, On the spectral radius of trees with perfect matchings, Combination and Graph Theory, World Scientific, Singapore, 1997.

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


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