淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0309201511091500
中文論文名稱 對路徑圖及路徑圖加上一條邊的傳遞數之研究
英文論文名稱 A study of the routing number of paths and path plus an edge
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 103
學期 2
出版年 104
研究生中文姓名 虞凱文
研究生英文姓名 Kai-Wen Yu
學號 601190126
學位類別 碩士
語文別 中文
口試日期 2015-06-23
論文頁數 37頁
口試委員 指導教授-潘志實
委員-李渭天
委員-高金美
中文關鍵字 傳遞數  傳遞排列  路徑 
英文關鍵字 routing number  permutation 
學科別分類 學科別自然科學數學
中文摘要 將一個物品從某地點透過交換的方式傳遞的其他的地點,這樣的問題在很多不同的領域都會用到,像網路之間的聯繫的研究,平行運算上的資料傳遞等等。這樣的問題可以如此被描述:給定任意圖形G=(V,E),|V(G)|=n,其頂點集為{v_1,v_2,……,v_n},給定一個n-排列π=p_1 p_2…p_n,每個頂點v_i將會被標記一個旗子p_j,這些旗子是可移動的,但必須遵守下列規則:在每個步驟中,在圖形𝐺中選取邊的不相交子集,這些邊的端點的旗子可以做交換。最後的目標在於將所有的旗子p_i交換到對應的點位v_i上。對於任意排列π,定義rt(𝐺,π)為最少的步驟完成此次傳遞。而圖G的傳遞數記為rt(𝐺)=max┬π〖rt(G,π)〗。
英文摘要 The problem of routing permutations over graphs arose in different fields , such as the study of communicating processes on networks, the data flow on parallel computation, and the analysis of routing algorithms on VLSI chips. This problem can be described as follows: Let G = (V,E) be a connected graph with vertices {v1, v2 ...vn} and π be a permutation on [n]. Initially, each vertex vi of G is occupied by a “pebble.” The pebble on vi will be labeled as pj if π(i) = j. Pebbles can be moved around by the following rule. At each step a disjoint collection of edges of G is selected, and the pebbles at each edge’s two endpoints are interchanged. The goal is to move/route each pebble pi to its destination vi. Define rt(G, π) to be the minimum number of steps to route the permutation π. Finally, define rt(G) the routing number of G by rt(G) = max π rt(G, π).
論文目次 目錄
目錄………………………………………………I
圖表目錄…………………………………………II
第一章 基本定義 ………………………………1
第二章 傳遞數簡介……………………………8
第三章 路徑圖的傳遞數………………………15
第四章 路徑圖加一條邊的傳遞數……………23
參考文獻 ………………………………………34

圖表目錄
圖1.1(圖)……………………………………………………………… 1
圖1.2(簡單圖)………………………………………………………… 1
圖1.3(路徑)…………………………………………………………… 2
圖1.4(迴圈)…………………………………………………………… 2
圖1.5(連通圖)………………………………………………………… 3
圖1.6(子圖與生成子圖)……………………………………………… 4
圖1.7(距離)…………………………………………………………… 5
圖1.8(樹)……………………………………………………………… 6
圖2.1(奇偶置換)………………………………………………………10
圖2.2(G=P_10^2,7)……………………………………………………… 13
圖2.3(G=P_10^6)……………………………………………………… 13
圖4.1(C_6=P_6^6)……………………………………………………… 23
圖4.2(特殊圖形的傳遞方法)…………………………………………24
圖4.3(G=P_8^4)……………………………………………………… 27
圖4.4(G=P_9^4)……………………………………………………… 28
圖4.5(G=P_n^k,n為偶數)……………………………………………30
圖4.6(G=P_n^k,n為奇數) ……………………………………………31
圖4.7(G=P_6^5) ……………………………………………………… 32
圖4.8(G=P_7^6) ……………………………………………………… 32
參考文獻 [1] NogaAloni, F. R. K. Chungt, And R. L. Graham, Routing Permutations On Graphs Via Matchings, 1994.

[2]F. K. Chung, Spectral Graph Theory, AMS Publications, Providence, RI, 1997

[3] D. E. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, Readin𝐺, MA, 1973,p. 241.

[4] Wei-Tian Li, Linyuan Lu, And YitingYang,RoutingNumbers Of Cycles, Complete Bipartite Graphs, And Hypercubes, SIAM J. Discrete Math. Vol.24 (2010), No.4, pp.1482-1494.

[5]M. Ramras, Routing permutations on a Graph, Networks, 23 (1993), pp. 391–398.

[6] L. Valiant, A scheme for fast parallel communication, SIAM J. Comput., 11 (1982), pp. 350–361.

[7]L. Zhan𝐺, Optimal bounds for matchin𝐺routin𝐺 on trees, SIAM J. Discrete Math., 12 (1999),pp. 64–77.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2015-09-08公開。
  • 同意授權瀏覽/列印電子全文服務,於2015-09-08起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2486 或 來信