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

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/95720

Title:	計算特殊圖類的凱梅尼常數;Resolving Kemeny’s constant of special family of graphs
Authors:	彭偉豪;Peng, Wei-Hao
Contributors:	數學系
Keywords:	凱梅尼常數;Kemeny′s constant
Date:	2024-06-18
Issue Date:	2024-10-09 17:11:41 (UTC+8)
Publisher:	國立中央大學
Abstract:	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.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	27	View/Open

社群 sharing

Loading...