| 摘要: | 生成樹雍塞度問題是由Ostrovkii於2004年提出，其定義如下：給定一個連結 圖形G以及G的一棵生成樹r。對於r上的一個邊e而言，我們令A和及表示圖形G\e 的兩個子圖之個別點集合。邊e的壅塞度被定義為ec〔G ： T) = |{(u, v)\u E Ae,vEBe}\，而r的壅塞度是指所有屬於r的邊之邊壅塞度中之最大值，而G的生成 樹壅塞度係指所有G的生成樹r之樹壅塞度中之最小值。 生成樹壅塞度問題被熱烈討論，並有多種有趣的衍生問題，近來，學者Otachi 等人則提出大量有關生成樹壅塞度數之研究成果。儘管多位圖論領域的知名學者 提出其相關研究結果，但是針對多層式金字塔型網路上求解生成樹壅塞度數之相 關文獻，據我們所知仍相當有限。 本計畫將試圖在生成樹壅塞度問題剛開始為國際學者注視時，提出一系列研 究。我們的研究團隊預計先針對一些多層式金字塔型網路，包括金字塔網路、網 格金字塔網路、WK金字塔網路、加強型金字塔網路、萬用金字塔網路、星狀金 字塔網路等等網路圖形，進行深入探討。在計畫的第一年，我們將先行審視評估 多層式金字塔型網路本身的一些特性，預期在其中發現一些有關求解生成樹壅塞 度問題的數學性質。實際上，我們將探討多層式金字塔型網路的生成樹壅塞度， 與其他一些圖形參數，例如樹寬以及安全數等圖形參數之間的關係，藉以來定位 生成樹壅塞度的上、下限值。植基於計畫第一年的研究結果，我們將於計畫的第 二年再擴大研究成果，期望將建立對於先前擇訂之多層式金字塔型網路上有關生 成樹壅塞度研究之重要觀點（目前文獻尚未呈現者），以提供一些關鍵性質，這將 有助於發展更精確的研究，預期將用以設計出求解此問題在一些多層式金字塔型 網路上的演算法。此外，對於難以求解的多層式金字塔型網路，我們將運用確切 演算法的一些技巧，尋求此問題的逼近演算法。
Spanning tree congestion was first introduced by Ostrovkii in 2004. Let G be a finite connected graph and T be a spanning tree of G. For any edge e of T, Ae and Be be the vertex sets of the components of T\e. The edge congestion of e in T is defined as ec(G ： T)= and the congestion of T is the maximum of over all edges of T. Then the spanning tree congestion of G is the minimum of congestion over all spanning trees of G. The study of spanning tree congestion as a graph-theoretic concept has recently attracted a great deal of attention. Several bounds on different types of spanning tree congestion were obtained of a graph. Lately, Otachi et al. boost up the research related to spanning tree congestion of graphs. The investigation into the spanning tree congestion problem was carried out by researchers while the results for solving the spanning tree congestion on multi-layered pyramid networks, to the best of our known, are poor. This project will seek to promote the line of research in the theory of spanning tree congestion problem in the early beginning. Several multi-layered pyramid networks will be discussed. Multi-layered pyramid networks consist of pyramid networks, grid-pyramids, WK-pyramids, enhanced pyramid networks, versatile pyramid networks, star-pyramid networks, etc. During the first year of this project, we shall survey the characteristics of the multi-layered pyramid networks for the purpose of exploring the mathematical properties of the spanning tree congestion in such graphs. Actually, we would like to determine bounds on spanning tree congestion for the multi-layered pyramid networks in terms of other graph parameters, e.g. treewidth and security number. Based on the results obtained during the first year of the study, our research wants to further establish relevant aspects of the spanning tree congestion of multi-layered pyramid networks, (not currently available in the literature), to provide essential properties which is needed for the development of a concise investigation. In the second year of the project, we shall develop algorithms for solving spanning tree congestion on some multi-layered pyramid networks. In addition, we shall use the techniques of exact algorithms for the problem on difficult graphs. |
