跳到主要內容

臺灣博碩士論文加值系統

(44.211.24.175) 您好!臺灣時間:2024/11/10 16:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:陳冠穎
研究生(外文):Guan-Ying Chen
論文名稱:拉普拉斯矩陣上的特徵值重數
論文名稱(外文):Eigenvalue multiplicities of Laplacian matrices
指導教授:林晉宏
指導教授(外文):Jephian C.-H. Lin
學位類別:碩士
校院名稱:國立中山大學
系所名稱:應用數學系研究所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2021
畢業學年度:109
語文別:英文
論文頁數:26
中文關鍵詞:拉普拉斯矩陣重根數第二小特徵值補可約圖笛卡兒合成王冠合成單點聯集
外文關鍵詞:Laplacian matrixmultiplicitysecond smallest eigenvaluescographcartesian productCorona productuni-join
相關次數:
  • 被引用被引用:0
  • 點閱點閱:113
  • 評分評分:
  • 下載下載:10
  • 收藏至我的研究室書目清單書目收藏:0
我們可以將圖上的點做標記,並將其轉換成相對應拉普拉斯矩陣,藉此取得它的特徵值。我們聚焦在圖的代數連通度,也就是圖的拉普拉斯矩陣的第二小的特徵值。代數連通度的特徵向量可以用來將圖嵌入到空間中、分割、以及將資料分群。由於特徵值的重數會影響特徵向量的選取,此篇論文試著了解代數連通度的重根數。
我們發覺有許多圖的第二小特徵值重數大於1;我們也考慮圖的合成,並由小圖的特徵值重數來計算合成圖的特徵值重數。我們考慮的合成方式包含交集、聯集、笛卡兒合成、王冠合成、與單點聯集。
For a labeled graph, we may transform it into a matrix called the Laplacian matrix and study the relations between graphs and their Laplacian eigenvalues.
We focus on the second smallest Laplacian eigenvalue λ2, which is also known as the algebraic connectivity. The eigenvector of λ2 can be used for graph drawing, graph partitioning, and spectral clustering. Since the choices of the eigenvector can vary when the eigenvalue has a high multiplicity, this thesis studies the multiplicity of λ2, aiming to understand the robustness of these applications.
We notice that the multiplicity of λ2 is more than one for many graphs. We also study how to use the eigenvalue multiplicities of small graphs to obtain the eigenvalue multiplicities of their graph products. The graph operations we have considered include the disjoint union, the cartesian product, the corona product, and uni-join.
論文審定書 i
摘要 ii
Abstract iii
1 Introduction 1
2 Preliminaries 2
2.1 Basic properties of a Laplacian matrix . . . . . . . . . 3
2.2 Graph products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3 Laplacian eigenvalues and its multiplicity . . . . . . . 9
3.1 Cograph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 Cartesian product . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Corona product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.4 Uni-join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 References 20
References
[1] Charles J. Alpert, Andrew B. Kahng, and So-Zen Yao. “Spectral partitioning with
multiple eigenvectors”. In: Discrete Applied Mathematics 90.1-3 (1999), pp. 3–26.
[2] Turker Biyikoglu, Josef Leydold, and Peter F. Stadler. Laplacian Eigenvectors of
Graphs: Perron–Frobenius and Faber–Krahn Type Theorems. Springer Berlin Heidelberg,
2007.
[3] Andries E. Brouwer and Willem H. Haemers. Spectra of graphs. Springer Science
& Business Media, 2011.
[4] Bobbi J. Broxson. The Kronecker product. 2006.
[5] Meifeng Dai et al. “Generalized adjacency and Laplacian spectra of the weighted
corona graphs”. In: Physica A: Statistical Mechanics and its Applications 528
(2019), p. 121285.
[6] Robert Grone, Russell Merris, and Vaikalathur S. Sunder. “The Laplacian spectrum
of a graph”. In: SIAM Journal on matrix analysis and applications 11.2 (1990),
pp. 218–238.
[7] Peter L. Hammer and Alexander K. Kelmans. “Laplacian spectra and spanning
trees of threshold graphs”. In: Discrete Applied Mathematics 65.1-3 (1996), pp. 255–
273.
[8] Steve Kirkland, Michael Neumann, and Bryan L. Shader. “Characteristic vertices
of weighted trees via Perron values”. In: Linear and Multilinear Algebra 40.4
(1996), pp. 311–325.
[9] Bojan Mohar. “Some applications of Laplace eigenvalues of graphs”. In: Graph
symmetry. Springer, 1997, pp. 225–275.
[10] Ulrike V. Luxburg. “A tutorial on spectral clustering”. In: Statistics and computing
17.4 (2007), pp. 395–416.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top