計算特殊圖類的凱梅尼常數;Resolving Kemeny’s constant of special family of graphs

NCU Institutional Repository > 理學院 > 數學研究所 > 博碩士論文 > Item 987654321/95720

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/95720

題名:	計算特殊圖類的凱梅尼常數;Resolving Kemeny’s constant of special family of graphs
作者:	彭偉豪;Peng, Wei-Hao
貢獻者:	數學系
關鍵詞:	凱梅尼常數;Kemeny′s constant
日期:	2024-06-18
上傳時間:	2024-10-09 17:11:41 (UTC+8)
出版者:	國立中央大學
摘要:	1981年，Kemeny[4]考慮在連通圖G上做簡單隨機漫步，且有轉移機率矩陣P與平穩分佈π = (π_1,...,π_n)。Kemeny得到的第一個主要結果是:數值∑_(j=1)^n H_(ij)π_j與i無關，其中H_(ij)代表從點i出發第一次到點j的平均步數。這個數值在後來的文獻中被稱為Kemeny常數，並以K(P)表示。在[4]的第二個主要結果中，作者證明:可以透過選擇適當的g向量和β向量，經由n×n矩陣(I−P+gβ^T)^(−1)導出G的Kemeny常數。在本文中，我們首先提供這兩個結果更簡潔的證明。然後我們用這兩個結果來計算一些特殊圖的Kemeny常數，包括完全圖、完全二分圖、路徑圖和超立方體圖。;In [4] Kemeny consider a simple random walk on a connected graph G with transition probability matrix P and stationary distribution π = (π_1, . . . , π_n). The first key result of [4] is that Kemeny proved the value ∑_(j=1)^n H_(ij)π_j is independent of i, where H_(ij) is the mean hitting time to node j starting from i. This value was later called the Kemeny’s constant in the literature and denoted by K(P). The second key result of [4] is that Kemeny proved that K(P) can be derived via an n×n matrix matrix (I−P+gβ^T)^(−1) by choosing appropriate vectors g and β. In this thesis, first we give these two results a more condensed proof. We then use them to compute Kemeny’s constants of some special graphs, including complete graphs, complete bipartite graphs, paths and hypercubes.
顯示於類別:	[數學研究所] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	39	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....