計算特殊圖類的凱梅尼常數

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：31

、訪客IP：18.217.161.27

姓名

彭偉豪(Wei-Hao Peng) 查詢紙本館藏

畢業系所

數學系

論文名稱

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

相關論文

★ 圓環面網路上的病毒散播	★ 以2D HP 模型對蛋白質摺疊問題之研究
★ On Steiner centers of graphs	★ On the Steiner medians of a block graph
★ 圖形列表著色	★ 秩為5的圖形
★ Some results on distance-two labeling of a graph	★ 關於非奇異線圖的樹
★ On Minimum Strictly Fundamental Cycle Basis	★ 目標集選擇問題
★ 路徑圖與格子圖上的目標集問題	★ 超立方體圖與格子圖上的目標集問題
★ 圖形環著色數的若干等價定義	★ 網格圖上有效電阻計算方法的比較
★ 數樹：方法綜述	★ 拉普拉斯居中度研究概述

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

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.

關鍵字(中)

★ 凱梅尼常數

關鍵字(英)

★ Kemeny′s constant

論文目次

Contents
1 Introduction and preliminaries 1
2 Results 2
2.1 The derivation of Kemeny’s constant 2
2.2 Kemeny’s constant for special family of graphs 5
References 12

參考文獻

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, The Macmillan Press Ltd,
London, 1976.
[2] Haiyan Chen and Fuji Zhang, The expected hitting times for graphs with cutpoints,
Statistics & Probability Letters, 66 (2004) 9-17.
[3] Charles M. Grinstead and J. Laurie Snell, Introduction to Probability, 2nd edition, American
Mathematical Society, 2003.
[4] John G. Kemeny, Generalization of a fundamental matrix, Linear Algebra and its Applications,
38 (1981) 193-206.
[5] John G. Kemeny and J. Laurie Snell, Finite Markov Chains, Springer, 1976.
[6] Robert E. Kooij and Johan L.A. Dubbeldam, Kemeny’s constant for several families of
graphs and real-world networks, Discrete Applied Mathematics, 285 (2020) 96-107.
[7] L. Lovász, Random walks on graphs: a survey, Combinatorics, Paul Erdős is Eighty, vol.2,
Bolyai Society, Mathematical Studies, Keszthely, Hungary, 1993.
[8] Christopher Zhang, Formulas for Hitting Times and Cover Times for Random Walks
on Groups, arXiv preprint arXiv:2302.01963, 2023.
[9] Hong-Gwa Yeh, Class Notes for Seminar, Fall 2022 and Spring 2023, National Central University,
Taiwan.

指導教授

葉鴻國(Hong-Gwa Yeh)

審核日期

2024-6-18

推文