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