English  |  正體中文  |  简体中文  |  Items with full text/Total items : 49942/85107 (59%)
Visitors : 7782782      Online Users : 54
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library & TKU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version
    Please use this identifier to cite or link to this item: http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/102961


    Title: 圖的傳遞數之研究
    Other Titles: The Study of Routing Numbers of Graphs.
    Authors: 潘志實
    Contributors: 淡江大學數學學系
    Keywords: 傳遞數;傳遞排列;平行演算法;routing number;routing permutation;parallel algorithm
    Date: 2012-08
    Issue Date: 2015-05-12 15:20:30 (UTC+8)
    Abstract: 在一個圖上將每個點的資源傳遞到其他點的問題在很多不同的領域都會用到[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.
    Appears in Collections:[數學學系暨研究所] 研究報告

    Files in This Item:

    There are no files associated with this item.

    All items in 機構典藏 are protected by copyright, with all rights reserved.


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