給定任意圖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.