On the Steiner medians of a block graph

NCU Institutional Repository > 理學院 > 數學研究所 > 博碩士論文 > Item 987654321/7865

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/7865

題名:	On the Steiner medians of a block graph
作者:	彭勝鴻;Sheng-Hueng Peng
貢獻者:	數學研究所
關鍵詞:	block graph;the Steiner n-median;the Steiner n-distance
日期:	2005-06-01
上傳時間:	2009-09-22 11:07:34 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	在圖論中，若有某一點屬於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.
顯示於類別:	[數學研究所] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....