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

(44.222.218.145) 您好！臺灣時間：2024/03/02 10:40

:::

### 詳目顯示

:

• 被引用: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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 關於中央點及中心點一致性之研究 2 關於弦環圖形中獨立擴張樹高度之研究 3 結合規則挖掘與行為預測來強化網路資訊查詢處理 4 現行點對點資源分享技術的改進與實作 5 高壓下烷基卡必醇與二氧化碳混合物之汽液平衡研究 6 應用網際探勘於網頁及商品自動化推薦系統之研究 7 金字塔形網路上使用最低層最短繞徑法的容錯繞徑演算法 8 知識管理與ISO認證整合之研究 9 架構在PNN基礎的快速適應性門檻值演算法 10 結合電子商務與供應鏈管理之整合研究-電子化供應鏈管理的實務應用 11 TCP在無線區域網路上公平性之探討 12 以文件為基礎的資訊擷取系統 13 位元重組在階層式智慧型封包分類策略之研究 14 利用改良的兩階段動態規劃之方法已獲得稠密的視差估測 15 實作一個具協同與整合功能的Biztalk流程引擎

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