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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1907201620253000
中文論文名稱 刻劃路徑圖的傳遞數
英文論文名稱 Characterize the routing number of paths
校院名稱 淡江大學
系所名稱(中) 數學學系碩士班
系所名稱(英) Department of Mathematics
學年度 104
學期 2
出版年 105
研究生中文姓名 韓鳴展
研究生英文姓名 Ming-Jhan Han
學號 603190025
學位類別 碩士
語文別 中文
口試日期 2016-06-17
論文頁數 29頁
口試委員 指導教授-潘志實
委員-高金美
委員-李渭天
中文關鍵字 傳遞數  傳遞排列  路徑 
英文關鍵字 Routing number  permutation 
學科別分類 學科別自然科學數學
中文摘要 給定任意圖G=(V,E),|V(G)|=n,對圖形上每個點標註{v_1,v_2,…,v_n},每個點上有一個棋子,棋子上標有數字1~n,且每個棋子上的數字皆不重複,目標為對所有的i=1,2,…,n,將棋子i移動到頂點v_i上。當每個棋子皆移動到對應的位置上時,我們稱其為排好。這些棋子的移動必須遵守下列規則:在每個步驟中,在圖形G中取邊的不相交子集,這些邊的端點可以做交換,重複以上述步驟直到排好。
設π為{1,2,…,n}的排列,分別對應到{ v_1,v_2,…,v_n}上棋子的數字,定義rt(G,π)為將π排好的最少步數。而圖G的傳遞數是指對任意排列π都能排好所需要的最少步數,記作rt(G)=max┬π〖rt(G,π)〗。
在本文中我們想要刻劃出在路徑圖P_n上,具備哪些特性的棋子排列π,會使得rt(P_n,π)=n。
考慮一個由1~n所組成的排列其首k項為n-k+1到n之任意排列,則稱此排列有逆序。若k為奇數,則稱為奇逆序;若k為偶數,則稱為偶逆序。我們證明了若π為P_n=[v_1,v_2,…,v_n]上棋子的排列,則滿足rt(P_n,π)=n的充分必要條件為π同時擁有奇逆序與偶逆序。
英文摘要 Let G=(V,E) be a connected graph with vertices {v_1,v_2,…,v_n} and π be a permutation on [n]. Initially, each vertex v_i of G is occupied by a “pebble”. The pebble on v_i will be labeled as j 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 i to its destination v_i. 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,π)〗.
In this paper,we want to characterize the property of π such that rt(P_n,π)=n. If the first k terms of π is any permutation from n-k+1 to n, then π is called has a reverse. If k is odd, then such reverse is called odd-reverse, if k is even, then such reverse is called even-reverse.We prove that for path P_n=[v_1,v_2,…,v_n], π is a permutation on [n], rt(P_n,π)=n if and only if π has odd-reverse and even-reverse.
論文目次 目錄
目錄 …………………………………………………………I
圖表目錄 ……………………………………………………II
第一章基本定義 ……………………………………………1
第二章 傳遞數簡介…………………………………………4
第三章 路徑圖的傳遞數……………………………………13
參考文獻 ……………………………………………………28

圖表目錄
圖1.1(圖)……………………………………………………2
圖1.2(簡單圖)………………………………………………2
圖1.3(路徑)…………………………………………………2
圖1.4(迴圈)…………………………………………………3
圖2.1(圖上旗子的傳遞)……………………………………5
圖2.2(路徑圖的奇偶置換)…………………………………9
圖2.3(數列的奇偶置換)……………………………………9
參考文獻 [1] NogaAloni,F.R.K.Chungt,AndR.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.
[8]Tomas Worsch And Hidenosuke Nishio,REAL-TIME SORTING OF BINARY NUMBERS ON ONE-DIMENSIONAL CA,Journees Automates Cellulaires 2010(Turku),pp.214-225.
[9]虞凱文,對路徑圖及路徑圖上加一條邊的傳遞數之研究,淡江大學覺生紀念圖書館2015.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2016-07-21公開。
  • 同意授權瀏覽/列印電子全文服務,於2016-07-21起公開。


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