| 姓名 |
彭勝鴻(Sheng-Hueng Peng)
查詢紙本館藏 |
畢業系所 |
數學系 |
| 論文名稱 |
(On the Steiner medians of a block graph)
|
| 相關論文 | |
| 檔案 |
 [Endnote RIS 格式]
[Bibtex 格式]
 [相關文章]  [文章引用]  [完整記錄]  [館藏目錄]  [檢視] [下載]- 本電子論文使用權限為同意立即開放。
- 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
- 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。
|
| 摘要(中) |
在圖論中，若有某一點屬於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 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. |
| 關鍵字(中) |
|
關鍵字(英) |
★ block graph
★ the Steiner n-median
★ the Steiner n-distance |
| 論文目次 |
摘要...........................................i
Abstract......................................ii
致謝.........................................iii
Contents......................................iv
1.Introduction.................................1
2.Finding the n-median of a block graph........3
3.Some notes in Steiner medians...............11
Reference.....................................13 |
| 參考文獻 |
L.W.Beineke, O.R.Oellermann and R.E.Pippert,On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249-258.
J.A.Bondy and U.S.R.Murty,Graph Theory with
Applications, North-Holland, New York. 1976.
G.Chartrand and O.R.Oellermann, S.Tian and H.-B.Zhou,Steiner distance in graphs, Casopis Pest. Mat. 114 (1989) 399-410.
O.R.Oellermann,Some Open Problems in Graph Theory,URL:
http://www.uwinnipeg.ca/~ooellerm/open_problems/index.html
O.R.Oellermann,On Steiner centers and Steiner medians of
graphs, Networks, 34 (1999) 258-263.
O.R.Oellermann, Private communication, 1999.
H.G.Yeh, A note on Steiner centers and Steiner medians of graphs, preprint, 2004. |
| 指導教授 |
葉鴻國(Hong-Gwa Yeh)
|
審核日期 |
2005-6-21 |
| 推文 |
 facebook  plurk  twitter  funp  google  live  udn  HD  myshare  reddit  netvibes  friend  youpush  delicious  baidu
|
| 網路書籤 |
 Google bookmarks  del.icio.us  hemidemi myshare
|
