姓名 |
彭勝鴻(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,並不是所有的圖形的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
|