跳到主要內容

臺灣博碩士論文加值系統

(44.200.140.218) 您好!臺灣時間:2024/07/19 01:44
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:于立斌
研究生(外文):Li-ping Yu
論文名稱:在煎餅圖上的延伸連通性
論文名稱(外文):On The Spanning Connectivity of the Burnt Pancake Graphs
指導教授:徐力行徐力行引用關係
指導教授(外文):Lih-hsing Hsu
學位類別:碩士
校院名稱:靜宜大學
系所名稱:資訊工程學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2009
畢業學年度:98
語文別:英文
論文頁數:47
中文關鍵詞:container漢彌爾頓connected漢彌爾頓圈互聯網路
外文關鍵詞:containerHamiltonian cyclesHamiltonian connectedinterconnection networks
相關次數:
  • 被引用被引用:0
  • 點閱點閱:225
  • 評分評分:
  • 下載下載:16
  • 收藏至我的研究室書目清單書目收藏:0
令u和v為在無向圖G中兩個不一樣的點,且為k-connected。一個在k-connected圖G中的w-container C(u,v)是從u到v的w-disjoint路徑的一個集合,且1≦w≦k。一個在圖G 中的w-container C(u,v)若它包含了在圖G 中所有的點則為一個w*-container。一個圖G若在任何兩個不一樣的點之間它都存在著一個w-container則為w*-connected。令κ(G)為圖的連通性。一個圖G若為i*-connected則為超級延伸連通,i的範圍1<=i<=κ(G)。在本研究裡,我們所要證明的是一個n維的煎餅圖Bn是超級延伸連通若且為若n≠2。
Let u and v be any two distinct vertices of an undirected graph G, which is k-connected. For 1w k, a w-container C(u,v) of a k-connected graph G is a set of w-disjoint paths joining u and v. A w-container C(u,v) of G is a w*-container if it contains all the vertices of G. A graph G is w*-connected if there exists a w*-container between any two distinct vertices. Let κ(G) be the connectivity of G. A graph G is super spanning connected if G is i*-connected for 1iκ(G).In this thesis, we prove that the n-dimensional burnt pancake graph Bn is super spanning connected if and only if n≠2.
Chinese Abstract i
English Abstract ii
Acknowledgements iii
List of Figures v
Chapter 1: Introduction . . . . . . . . . . . . . . . . . 1
Chapter 2: The Burnt Pancake Graph and its Properties . . 5
Chapter 3: Basic Lemmas . . . . . . . . . . . . . . . . 11
Chapter 4: Main Result . . . . . . . . . . . . . . . . . 31
Chapter 5: Conclusion . . . . . . . . . . . . . . . . . 34
References . . . . .. . . . . . . . . . . . . . . . . . 35
Appendix . . . . . . . . . . . . . . . . . . . . . . . 38
[1] S. Akers and B. Krishnameuthy, A group-theoretic model for symmetric interconnection networks, IEEE Transaction on Computers, 38, 555, (1989).
[2] C. H. Chang, C. K. Lin, H. M. Huang, and L. H. Hsu, The super lace-ability of the hypercubes, Information Processing Letters, 92, 15–21,(2004).
[3] C.H. Chang, C.K. Lin, J.M. Tan, H.M. Huang, and L.H. Hsu, 「The Super Spanning Connectivity and Super Spanning Laceability of the Enhanced Hypercubes」, The journal of supercomputing, vol. 48 pp. 66–87, (2009).
[4] C.H. Chang, C.M. Sun, H.M. Huang, and L.H. Hsu, On the equitable k*-laceability of hypercubes」, Journal of Combinatorial Optimization, 14, 349–364, (2007).
[5] D.S. Cohen and M. Blum, On the problem of sorting burnt pancakes. Discrete Appl. Math. 61, 105–120, (1995).
[6] W.H. Gates and C.H. Papadimitriou, Bounds for sorting by prefix re-versal, Discrete Math., 27, 47–57, (1979).
[7] Q.-P. Gu, S. Peng, and I.H. Sudborough, A 2-approximation algorithm for genome rearrangements by reversals and transpositions, Theoretical Computer Science, 210, 327–339, (1999).
[8] P. Hall, On representation of subsets, J. Lond. Mat. Sc., 10, 26–30, (1935).
[9] M.H. Heydari and I.H. Sudborough, On the diameter of the pancake network, J. Algorithms 25, 67–94, (1997),
[10] H.C. Hsu, C.K. Lin, H.M. Hung, and L.H. Hsu, The spanning connectivity of the (n, k)-star graphs」, International Journal of Foundations of Computer Science, 17, 415–434, (2006).
[11] L.H. Hsu and C.K. Lin, Graph Theory and Interconnection Networks, CRC Press, 2008.
[12] K. Kaneko, An algorithm for node-to-set disjoint paths problem in burnt pancake graphs, IEICE Transactions on Information and Systems, E86-D(12) , 2588–2594, (2003).
[13] K. Kaneko, Hamiltonian cycles and hamiltonian paths in faulty burnt pancake graphs, IEICE Transactions on Information and Systems, E90-D(4), 716–721, (2007).
[14] S. S. Kao and L. H. Hsu, The globally bi-3* and the hyper bi-3* connectedness of the spider web networks, Applied Mathematics and Computation, 170, 597–610, (2005).
[15] C. K. Lin, H. M. Huang, and L. H. Hsu, The super connectivity of the pancake graphs and the super laceability of the star graphs, Theoretical Computer Science 339, 257–271, (2005).
[16] C.K. Lin, H.M. Huang, and L.H. Hsu, On the spanning connectivity of graphs, Discrete Mathematics, 307, 285–289, (2007).
[17] C. K. Lin, H. M. Huang, J.M. Tan, and L. H. Hsu, On spanning connected graphs, On spanning connected graphs, Discrete Mathematics, 308, 1330–1333, (2008).
[18] C.K. Lin, T.Y. Ho, J.M. Tan, and L.H. Hsu, Super spanning connectivity of augmented cubes, accepted by Ars Combinatorica.
[19] C.K. Lin, H.M. Huang, D. F. Hsu, and L.H. Hsu, The spanning diameter of the star graph, Networks, 48, 235–249, (2006).
[20] C.K. Lin, J.M. Tan, D.F. Hsu, and L.H. Hsu, On the spanning connectivity and spanning laceability of hypercube-like networks, Theoretical Computer Science, 381, 218–229, (2007).
[21] K. Menger, Zur allgemeinen Kurventheorie, Fund. Math., 10, 95–115, (1927).
[22] Y. H. Teng, J.M. Tan, and L. H. Hsu, The globally bi-3*-connected property of the honeycomb rectangular torus, Information Sciences, 177, 5573–5589, (2007).
[23] C.H. Tsai, J.M. Tan, and L.H. Hsu, The super connected property of recursive circulant graphs, Information Processing Letters, 91, 293–298, (2004).
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top