對路徑圖及路徑圖加上一條邊的傳遞數之研究

A study of the routing number of paths and path plus an edge

虞凱文(Kai-Wen Yu)

指導教授 ： 潘志實

淡江大學/理學院/數學學系碩士班/碩士(2015年)

https://doi.org/10.6846/TKU.2015.00099

摘要

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

並列關鍵字

routing number ； permutation

參考文獻

[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

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