| 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 |