將一個物品從某地點透過交換的方式傳遞的其他的地點，這樣的問題在很多不同的領域都會用到，像網路之間的聯繫的研究，平行運算上的資料傳遞等等。這樣的問題可以如此被描述：給定任意圖形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.