English  |  正體中文  |  简体中文  |  Items with full text/Total items : 78111/78111 (100%) Visitors : 30541211      Online Users : 281
 Scope All of NCUIR 理學院    數學研究所       --博碩士論文 Tips: please add "double quotation mark" for query phrases to get precise resultsplease goto advance search for comprehansive author search Adv. Search
 NCU Institutional Repository > 理學院 > 數學研究所 > 博碩士論文 >  Item 987654321/7865

 Please use this identifier to cite or link to this item: `http://ir.lib.ncu.edu.tw/handle/987654321/7865`

 Title: On the Steiner medians of a block graph Authors: 彭勝鴻;Sheng-Hueng Peng Contributors: 數學研究所 Keywords: block graph;the Steiner n-median;the Steiner n-distance Date: 2005-06-01 Issue Date: 2009-09-22 11:07:34 (UTC+8) Publisher: 國立中央大學圖書館 Abstract: 在圖論中，若有某一點屬於median，則代表的是此點到其他所有的點之平均距離是最短的。事實上，一般圖論上所定義的median即是Steiner n – median中n = 2的特殊型態。但是，除了樹以外，到目前為止我們仍然無法很快速的找出任意圖形的Steiner n – median。 　　本篇論文主要把圖形著重在block graph上，從其找出一個只需多項式時間就能找出Steiner n – median的演算法，並推導出一個找出所有Steiner n – distance的值的方法。 　　最後一個部份則是舉無窮多個同類的圖來說明對於任意正整數ｎ，並不是所有的圖形的n – median都有包含的關係；以及一個簡單的n – median值下界。 The Steiner distance of anmpty set of vertices S of a connected graph G is the minimum number of edges of G containing S. Let n ? 2 be an integer and suppose that G has at least n vertices. The Steiner n – distance of a vertex v of G is defined to be the sum of the Steiner distances of all sets of n vertices that include v. Then the Steiner n – median of G is the subgraph induced by the vertices of minimum Steiner n – distance. In this paper, we present a O(|V(B)| + |E(B)|) algorithm for finding the Steiner n – median of a block graph B and present an efficient algorithm for finding the Steiner n – distance of all vertices in a block graph. Finial, we given an infinite family of graphs in which each graph G has M2(G) ? M3(G). And we given a trivial lower bounded for the Steiner n – median value. Appears in Collections: [數學研究所] 博碩士論文

Files in This Item:

File SizeFormat