跳到主要內容

臺灣博碩士論文加值系統

(44.222.218.145) 您好!臺灣時間:2024/03/02 10:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:吳致中
研究生(外文):Chih-Chung Wu
論文名稱:通路圖形及通路數值之探討
論文名稱(外文):The Rearrangeable graphs and Rearrangeability Numbers
指導教授:王有禮
指導教授(外文):Yue-Li Wang
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:48
中文關鍵詞:edge-disjointrealizablerearrangeable graphsrearrangeability numbercomplete bipartite graphscomplete n-partite graphstorusbutterfly graphs
外文關鍵詞:edge-disjointrealizablerearrangeable graphsrearrangeability numbercomplete bipartite graphscomplete n-partite graphstorusbutterfly graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:218
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
一directed graph G(V,E),V={1,2,3,…,n},對於G之一permutation π,若在G中存在n條從i到π(i),1≦i≦n,兩兩皆為edge-disjoint之paths,則稱π為realizable。若所有n!個permutations皆為realizable,則稱G為一個rearrangeable graph。另一方面,要使G為一rearrangeable graph其每條邊所需複製的最少次數,稱為G的rearrangeability number。在本篇論文中,將證complete bipartite graphs和complete n-partite graphs為rearrangeable graphs。並證明torus和butterfly graphs其rearrangeability number的上、下限。

Given a directed graph G(V,E), where V={1,2,3,…,n}, a permutation π is said to be realizable on G if there exist n edge-disjoint paths in G that connect vertex i to vertex π(i),1≦i≦n. G is said to be rearrangeable if all n! permutations are realizable on G. Moreover, the rearrangeability number of G is the minimal multiplicity that every edge needs to be duplicated in order for G to become rearrangeable. In this paper, first we prove that complete bipartite graphs and complete n-partite graphs are rearrangeable graphs. Then we prove the upper and lower bounds of the rearrangeability number of torus and butterfly graphs.

中文摘要…………………………………………………………………….…..I
英文摘要…………………………………………………………………….….II
誌謝…………………………………………………………………………….III
目錄……………………………….……………………………………………IV
圖表索引…………………………………………………………………...…..VI
第一章 簡介…………………………………………………………….……1
1.1基本圖論名詞…..………………...……………………………….……1
1.2Permutations……………………………………………………….……3
1.3Realizable Permutations………………………………………….……..4
1.4Rearrangeable Graphs…………………………………………….…….4
1.5Rearrangeability number(ψ)……………………………………...……5
第二章 相關的研究結果…………………………………………….……....7
2.1 Lower bounds on the size of rearrangeable graphs…………….……...7
2.2 Some rearrangeable graphs…………………………………….……...8
2.2.1 Complete graphs and star graphs……….……………….……….8
2.2.2 2.2.2 Hypercubes(Qn),n≦3…………………………...………..9
2.3 The rearrangeable number of some graphs………………..………….11
2.3.1 Ring graphs…………………………………………..………….11
2.3.2 Trees、Paths、Connected graphs…………………..…………..11
2.3.3 Meshes……………………………………………..……………13
2.3.4 A counter-example for the conjecture in [26]…..………………14
2.3.5 ψ(Qn)≦2 for all n…….……………….……………………….18
第三章 本篇論文之結果…………………………………………………...18
3.1 Complete Bipartite Graphs………………………………………..18
3.2 Torus……………………………….……………………………...27
3.3 Butterfly Graphs…………………………………………………..29
3.4ψ(Q4)、ψ(Q5)≦2 with every path being shortest……………….34
第四章 結論及未來研究方向……………………………………………...38
參考文獻……………………………………………………………………….40

[1] D. Barth and A. Raspaud, Two edge-disjoint Hamiltonian cycles in the butterfly graph, Information Processing Letters 51 (1994), 175-179.
[2] V.E. Benes, The Mathematical Theory of Connecting Networks and Telephone Traffic, Academic Press, New York, 1965.
[3] S.N. Bhatt, F.R.K. Chung, J.W. Hong, F.T. Leighton, B. Obrenic, A.L. Rosenbeerg, and E.J. Schwabe, Optimal emulations by butterfly-like networks, Journal of the Association for Computing Machinery 43 (1996), 293-330.
[4] Gary Chartrand, Ortrud R. Oellermann, Applied and algorithmic graph theory New York :McGraw-Hill, 1993.
[5] E. Choi et al., Hyperswitch network for the hypercube computer, in : Proceedings of Annual Symposium on Computer Architecture (1988), 90-99.
[6] R. Cole, B.Maggs, and R. Sitaraman, Routing on butterfly networks with random faults, Proceedings of IEEE Annual Symposium on Foundations of Computer Science (1995), 558-570.
[7] T.-Y. Feng, A survey of interconnection networks, IEEE Computer December (1981), 12-27.
[8] M.R. Garey, D.S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, CA, 1979.
[9] D.S. Greenberg, L.S. Heath, and A.L. Rosenberg, Optimal embeddings of butterfly-like graphs in he hypercube, Mathematical Systems Theory 23 (1990), 61-77.
[10] Ralph P. Grimaldi, Discrete and combinatorial mathematics, An applied introduction, 3th, 1994.
[11] M.C. Heydemann, J.G. Peters, and D. Sotteau, Spanners of hypercube-derived networks, The Society for Industrial and Applied Mathematics of Journal on Discrete Mathematical Analysis 9 (1996), 37-54.
[12] Q. Hu, Y. Ahang, X. Shen, Rearrangeable graphs, Information Processing Letters 71 (1999), 23-27.
[13] Q. Hu, Y. Zhang, X. Shen, Rearrangeable graphs, in: 3rd Annual International Conference, COCOON’97, Shanghai, China, August 20-22, Lecture Notes in Computer Science 1276, Springer, Berlin, 1997, 441-449.
[14] K. Hwang, F.A. Briggs, Computer Architecture and Parallel Processing, McGraw-Hill, New York, 1984.
[15] S.C. Hwang, G.H. Chen, Cycles in Butterfly Graphs, Networks, 35(2) (2000), 161-171.
[16] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, SanMateo, CA, 1992.
[17] F.T. Leighton, B.M. Maggs, and R.K. Sitaraman, On the fault tolerance of some popular bounded-degree networks, The Society for Industrial and Applied Mathematics of Journal on Computing 27(1998), 1303-1333.
[18] A. Lubiw, A counter-example to a conjecture by Szymanski on hypercube routing, Information Processing Letters 35 (1990), 57-61.
[19] G.M. Masson, G.C. Ginger and S. Makamura, A sampler of circuit switching networks, IEEE Computer June (1979), 32-48.
[20] K.R. Parthasarathy, Basic Graph Theory, 1994 2.Algotithmic Graph Theory / James A. McHugh, 1990.
[21] A.L. Rosenberg, Cycles in networks, Technical Report UM-CS-1991-020, Department of Computer and Information Science, University of Massachusetts, Amherst, MA, May 14, 1993.
[22] Y.Saad and M.H. Schultz, Topological properties of hypercubes, IEEE Transactions on Computers 37 (1998), 867-872.
[23] X. Shen, Q. HU, Realizability of an arbitrary permutation on a circuit-switched hypercube, Information Processing Letters 51 (1994), 237-243.
[24] X. Shen, Q. Hu, H. Dai, X. Wang, Optimal routing of permutations on rings, in: Lecture Notes in Computer Science 834, Springer, Berlin, 1994, 360-368.
[25] H.J. Siegel, Interconnection Networks for Large-Scale Parallel Processing, McGraw-Hill, New York, 1990.
[26] T. Szymanski, On the permutation capability of a circuit-switched hypercube, in: Proceedings of International Conference On Parallel Processing, (1989), 103-110.
[27] S.A. Wong, Hamilton cycles and paths in butterfly graphs, Networks 26 (1995), 145-150.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top