English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 58274/91817 (63%)
造訪人次 : 13793817      線上人數 : 38
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
搜尋範圍 查詢小技巧:
  • 您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
  • 進階搜尋
    請使用永久網址來引用或連結此文件: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/102961

    題名: 圖的傳遞數之研究
    其他題名: The Study of Routing Numbers of Graphs.
    作者: 潘志實
    貢獻者: 淡江大學數學學系
    關鍵詞: 傳遞數;傳遞排列;平行演算法;routing number;routing permutation;parallel algorithm
    日期: 2012-08
    上傳時間: 2015-05-12 15:20:30 (UTC+8)
    摘要: 在一個圖上將每個點的資源傳遞到其他點的問題在很多不同的領域都會用到[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.
    顯示於類別:[數學學系暨研究所] 研究報告





    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library & TKU Library IR teams. Copyright ©   - 回饋