### 博碩士論文 92221008 完整後設資料紀錄

 DC 欄位 值 語言 DC.contributor 數學系 zh_TW DC.creator 彭勝鴻 zh_TW DC.creator Sheng-Hueng Peng en_US dc.date.accessioned 2005-6-21T07:39:07Z dc.date.available 2005-6-21T07:39:07Z dc.date.issued 2005 dc.identifier.uri http://ir.lib.ncu.edu.tw:88/thesis/view_etd.asp?URN=92221008 dc.contributor.department 數學系 zh_TW DC.description 國立中央大學 zh_TW DC.description National Central University en_US dc.description.abstract 在圖論中，若有某一點屬於median，則代表的是此點到其他所有的點之平均距離是最短的。事實上，一般圖論上所定義的median即是Steiner n – median中n = 2的特殊型態。但是，除了樹以外，到目前為止我們仍然無法很快速的找出任意圖形的Steiner n – median。 　　本篇論文主要把圖形著重在block graph上，從其找出一個只需多項式時間就能找出Steiner n – median的演算法，並推導出一個找出所有Steiner n – distance的值的方法。 　　最後一個部份則是舉無窮多個同類的圖來說明對於任意正整數ｎ，並不是所有的圖形的n – median都有包含的關係；以及一個簡單的n – median值下界。 zh_TW dc.description.abstract The Steiner distance of an nonempty 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. en_US DC.subject block graph en_US DC.subject the Steiner n-median en_US DC.subject the Steiner n-distance en_US DC.title On the Steiner medians of a block graph en_US dc.language.iso en_US en_US DC.type 博碩士論文 zh_TW DC.type thesis en_US DC.publisher National Central University en_US