# 臺灣博碩士論文加值系統

(100.27.249.103) 您好！臺灣時間：2024/08/08 09:30

:::

### 詳目顯示

:

• 被引用:0
• 點閱:187
• 評分:
• 下載:15
• 書目收藏:0
 對於許多科學研究領域，複雜網路的研究變得重要和流行。在科學中，為複雜網路建模的時候，隨機圖扮演了關鍵的角色。因此，如何在隨機圖中有效率地找到哈密頓圈是一項重要的研究。在1997年，Palmer [5] 揭示了以確定性多項式時間可能找到哈密頓圈的演算法。我們採用Palmer演算法在1,000個隨機圖中找到哈密頓圈的機率來評估Palmer演算法的效能。我們的實驗結果顯示如果選擇 n=10000 和 M≥1500000，Palmer演算法可以為接近百分之九十九的Erdős–Rényi隨機圖G(n,M)找到哈密頓圈。另外，如果選擇 n=3333 和 p≥0.048，Palmer演算法可以為接近百分之九十九的三分隨機圖K_(n,n,n) (p)找到哈密頓圈。所以，若p≥0.048，我們的實驗結果顯示K_(n,n,n) (p)很有可能存在哈密頓圈。在我們的研究之前，對於p<3⁄4，K_(n,n,n) (p)存在哈密頓圈的機率是完全未知的。
 The study of complex networks has become important and popular in many areas of scientific researches. In science, random graphs play critical roles in modeling complex networks. Therefore, it is a significant study of how to find Hamiltonian cycles efficiently in random graphs. In 1997, Palmer [5] revealed a deterministic polynomial-time algorithm that probably finds Hamiltonian cycles. We evaluate the performance of the algorithm with the probability that the algorithm finds Hamiltonian cycles in 1,000 random graphs. Our experiments show that the algorithm can find Hamiltonian cycles for almost 99 percent of Erdős–Rényi random graphs G(n,M) with n=10000 and M≥1500000. Moreover, the algorithm can find Hamiltonian cycles for almost 99 percent of tripartite random graphs K_(n,n,n) (p) with n=3333 and p≥0.048. As a result, our experiments indicate that K_(n,n,n) (p) has a Hamiltonian cycle with high probability when p≥0.048. Prior to our research, the probability that K_(n,n,n) (p) has a Hamiltonian cycle with p<3⁄4 is completely unknown.
 Title PageAbstract of Chinese...iiiAbstract of English...ivAcknowledgements...vTable of Contents...viList of Tables...viiList of Figures...viiiChapter 1 Introduction...1Chapter 2 Experiments...4Chapter 3 Conclusions...21References...22
 [1] P. Erdős and A. Rényi (1959), "On Random Graphs I", Publicationes Mathematicae Debrecen, vol. 6, no. 26, pp. 290–297.[2] Ralph P. Grimaldi (2003). DISCRETE AND COMBINATORIAL MATHEMATICS An Applied Introduction (5th Edition). Pearson Addison-Wesley. ISBN 0201726343.[3] Øystein Ore (1960), "Note on Hamilton circuits", American Mathematical Monthly, vol. 67, no. 1, p. 55.[4] L. Pósa (1976), "Hamiltonian circuits in random graphs", Discrete Mathematics, vol. 14, no. 4, pp. 359–364.[5] E. M. Palmer (1997), "The hidden algorithm of Ore’s theorem on Hamiltonian cycles", Computers & Mathematics with Applications, vol. 34, no. 11, pp. 113–119.[6] J. Komlós and E. Szemerédi (1983), "Limit distributions for the existence of Hamilton circuits in a random graph", Discrete Mathematics, vol. 43, pp. 55–63.[7] G. Chen, R. Faudree, R. Gould, M. Jacobson, and L. Lesniak (1995), "Hamiltonicity in balanced k-partite graphs", Graphs and Combinatorics, vol. 11, no. 3, pp. 221–231.[8] Douglas B. West (2001). INTRODUCTION TO GRAPH THEORY (2nd Edition). Pearson Prentice-Hall. ISBN 0130144002.[9] J. A. Bondy and U. S. R. Murty (2008). GRAPH THEORY. Springer. ISBN 9781846289699.[10] Reinhard Diestel (2017). GRAPH THEORY (5th Edition). Springer. ISBN 9783662536216.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 隨機確定有限狀態自動機的最小化 2 表示均勻隨機群狀結構的元素的短乘積 3 常見賦距空間中的確定單一中位數選擇 4 論最佳化問題上和與積之一般性轉換 5 賦距空間的最大化與最小化問題關聯性 6 在隨機集合集中尋得向日葵 7 比較近似中心度的困難性 8 基於大規模基因組和蛋白質組數據的 抗菌肽分析與快速檢測 9 論加權ER圖其唯一最短路徑之存在性 10 在賦距空間中尋找與每個點距離最遠之點 11 尋找Erdős–Rényi 隨機圖的獨立集合 12 具隱私性之公開資料湖泊系統 13 開發以巴特勒矩陣為饋入網路之軌道角動量天線陣列 14 開發以羅德曼透鏡為饋入網路之軌道角動量天線陣列 15 元智大學之PM2.5預測

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室