刻劃路徑圖的傳遞數

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

並列關鍵字

Routing number ； permutation

參考文獻

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

[9]虞凱文,對路徑圖及路徑圖上加一條邊的傳遞數之研究,淡江大學覺生紀念圖書館2015.

[1] NogaAloni,F.R.K.Chungt,AndR.L.Graham,Routing Permutations On Graphs,Via Matchings,1994.