給定任意圖 G=(V,E)，|V(G)|=n，對圖形上每個點標註 {v_1,v_2,…,v_n }，給定一 n 個數字的排列 π=p_1,p_2,…,p_n，每個頂點 v_i  上標記一個棋子 p_j，這些棋子是可以移動的，但必須遵守下列規則：在每個步驟中，在圖 G 中取邊的不相交子集，這些邊的端點之棋子可以做交換，目標為將所有棋子 p_i  交換到對應的頂點 v_i  上。定義 rt(G,π) 為將 π 排好的最少步數，而圖 G 的傳遞數是指對任意排列 π 都能排好所需要的最少步數，記作 rt(G)=(max)┬π⁡〖rt(G,π)〗。

　　給定一數列 π=p_1,p_2,…,p_n，我們看其中一個數字 p_i，在原本數列中的數字若大於等於 p_i  則改為 1，反之則改為 0，因此可以得到一(0,1)數列λ=c_1,c_2,…,c_n。已知利用(0,1)數列可以證明路徑圖傳遞數之上界，給定任意的(0,1)數列 λ=c_1,c_2,…,c_n，將其以奇偶置換方法排序的步數小於等於 n-1 步。

　　在本文中針對任意的(0,1)數列 λ=c_1,c_2,…,c_N  ,N=∑_(k=0)^n▒a_k +∑_(k=0)^n▒b_k ，
定義 S=a_0,b_n,a_1,b_(n-1),a_2,b_(n-2),…a_(n-2),b_2,a_(n-1),b_1,a_n,b_0，
a_i,b_i≥1,i=0,1…n 分別為 0和1 之個數且 a_0  ,b_0  亦可以等於 0，
則在奇偶置換排序後，將其排好的最少步數為
N-(min)┬(i∈{0,1,…,n-1} )⁡〖{∑_(j=0)^i▒a_j +∑_(j=0)^(n-i-1)▒b_j }〗-1

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.” 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 p_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 routine number of G by rt(G)=(max)┬π⁡〖rt(G,π)〗.

　　Given a sequence, π=p_1,p_2,…,p_n, we choose the number p_i, if the number of the original sequence is greater or equal to p_i then change to “1”, otherwise change to “0”, therefore we obtain a (0,1)-sequences, λ=c_1,c_2,…,c_n. It is known that using the (0,1)-sequence can prove the upper bound of the routine number of path,then given an arbitrary (0,1)-sequence λ=c_1,c_2,…,c_n, the number when it line up by odd-even transposition sort is less than or equal to n-1.

　　In this paper, in connection with arbitrary (0,1)-sequences,λ=c_1,c_2,…,c_N  ,N=∑_(k=0)^n▒a_k  ∑_(k=0)^n▒b_k , define S=a_0,b_n,a_1,b_(n-1),a_2,b_(n-2),…a_(n-2),b_2,a_(n-1),b_1,a_n,b_0, a_i,b_i≥1,i=0,1…n are quantity of 0,1 respectively and a_0,b_0≥0, after odd-even transposition sort, the number when it line up will be
N-(min)┬(i∈{0,1,…,n-1} )⁡〖{∑_(k=0)^i▒a_k +∑_(k=0)^(n-i-1)▒b_k }〗-1

目錄
目錄..............................................I
圖表目錄..........................................II
第一章 基本定義與簡介..............................1
第二章 奇偶置換方法................................6
第三章 (0,1)數列的奇偶置換排序.....................17
第四章 結論及未來工作..............................37
參考文獻..........................................38

圖表目錄
圖1.1(圖上棋子的傳遞)..............................3
圖1.2...........................................4
圖1.3(路徑圖的奇偶置換)............................4
圖1.4(數列的奇偶置換)..............................4
圖2.1...........................................14
圖2.2...........................................15
圖3.1...........................................17
圖3.2...........................................21

[1] N. Alon, F.R.K. Chung, and R.L. Graham, Routing Permutations on graphs via matchings, SIAM J. Discrete Math., 7(1994), pp.513-530

[2] M. Baumalag and F. Annexstein, A unified framework for off-line permutation routing in parallel networks, Math. Systems Theory, 24(1991), pp.233-251.

[3] V. E. Benes, Mathematical Theory of Connecting Networks, Academic Press, New York, 1965.

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

[5] Wei-Tian-Li, Linyuan Lu, and Yiting Yang, Routing Numbers of Cycles, Complete Bipartite Graphs, And Hypercubes, SIAM J. Discrete Math. Vol.24(2010), No.4, pp.1482-1494.

[6] M. Ramras, Routing permutations on a graph, Networks, 23 (1993),  pp.391-398.

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

[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.

[10] 韓鳴展，刻劃路徑圖的傳遞數，淡江大學覺生紀念圖書館2016.