(18.210.22.132) 您好!臺灣時間:2019/10/14 21:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
本論文永久網址: 
line
研究生:彭勝鴻
研究生(外文):Sheng-Hueng Peng
論文名稱(外文):On the Steiner medians of a block graph
指導教授:葉鴻國
指導教授(外文):Hong-Gwa Yeh
學位類別:碩士
校院名稱:國立中央大學
系所名稱:數學研究所
學門:數學及統計學門
學類:數學學類
論文出版年:2005
畢業學年度:93
語文別:中文
論文頁數:19
外文關鍵詞:block graphthe Steiner n-medianthe Steiner n-distance
相關次數:
  • 被引用被引用:0
  • 點閱點閱:122
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
  在圖論中,若有某一點屬於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 �d 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.
摘要...........................................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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔