研究報告
| 學年 | 101 |
|---|---|
| 學期 | 1 |
| 出版（發表）日期 | 2012-08-01 |
| 作品名稱 | 圖的傳遞數之研究 |
| 作品名稱（其他語言） | The Study of Routing Numbers of Graphs. |
| 著者 | 潘志實 |
| 單位 | 淡江大學數學學系 |
| 描述 | 計畫編號：NSC101-2115-M032-004
 研究期間：201208~201307
 研究經費：347,000 |
| 委託單位 | 行政院國家科學委員會 |
| 摘要 | 在一個圖上將每個點的資源傳遞到其他點的問題在很多不同的領域都會用到[2,3,6,7]，像網路之間的聯繫的研究，平行運算上的資料傳遞，在VLSI晶片上的傳遞演算法的分析等等。這樣的問題可以被這樣描述：令為一連通圖，其點集合為而),(EVG=},,,{21nvvvKπ為上的排列。一開始在的每個點上給一顆小石頭。而當][nGivji=)(π時小石頭上會被標上。而小石頭可由下列的規則移動。每次的步驟，是先在上取一獨立的邊集，而在那一步的時候，將每個邊上的兩點的小石頭互換。目標是將每個標記的小石頭傳遞到。而ivjpGipiv),(πGrt定義為最小的步驟數去傳遞排列π。最後，定義為滿足遍取所有)(Grtπ中最大的),(πGrt， ()ππ,max)(GrtGrt=。一般而言，要計算圖傳遞數是相當困難的。所以我們目前都只有比較基本的圖形或特殊圖形的傳遞數。在[4]中有介紹一些基本圖形的傳遞數。路徑圖 (, nP)3≥nnPrtn=)(; 完全圖 (,; 完全二部圖 (, ; 星圖(, nK)3≥n2)(=nKrtnnK,)3≥n4)(,=nnKrtnS)3≥n⎣⎦2)1(3)(−=nnSrt。本計劃中，我們主要想討論一般樹的傳遞樹，我們也想研究圖的傳遞數和分數傳遞數的一些關係。 The problem of routing permutations over graphs arose in differenet fields [2,3,6,7], 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 ),(EVG= be a connected graph with vertices and },,,{21nvvvKπ be a permutation on . Initially, each vertex of is occupied by a “pebble”. The pebble on will be labeled as if ][nivGivjpji=)(π. Pebbles can be moved around by the following rule. At each step a disjoint collection of edges of is selected, and the pebbles at each edge’s two endpoints are interchanged. The goal is to move/route each pebble to its destination . Define Gipiv),(πGrt to be the minimum number of steps to route the permutation π. Finally, define the routing number of by )(GrtG( ππ,max)(GrtGrt=. Determining the routing number of a graph is a quite difficult problem. For a few kinds of special graphs, the routing numbers are known in the literature [4]. For the path (, nP)3≥nnPrtn=)(; for complete graph (,; for the complete bipartite graph (, ; and for the star (, nK)3≥n2)(=nKrtnnK,)3≥n4)(,=nnKrtnS)3≥n⎣⎦2)1(3)(−=nnSrt. In this project, we consider the routing number for general tree, and the relation between the fractional routing number and routing number of graphs. |
| 關鍵字 | 傳遞數; 傳遞排列; 平行演算法; routing number; routing permutation; parallel algorithm |
| 語言 | zh_TW |
| 相關連結 |
機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/102961 ) |