博碩士論文 92221008 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:20 、訪客IP:52.204.98.217
姓名 彭勝鴻(Sheng-Hueng Peng)  查詢紙本館藏   畢業系所 數學系
論文名稱
(On the Steiner medians of a block graph)
相關論文
★ 圓環面網路上的病毒散播★ 以2D HP 模型對蛋白質摺疊問題之研究
★ On Steiner centers of graphs★ 圖形列表著色
★ 秩為5的圖形★ Some results on distance-two labeling of a graph
★ 關於非奇異線圖的樹★ On Minimum Strictly Fundamental Cycle Basis
★ 目標集選擇問題★ 路徑圖與格子圖上的目標集問題
★ 超立方體圖與格子圖上的目標集問題★ 圖形環著色數的若干等價定義
★ 網格圖上有效電阻計算方法的比較★ d 維立方體圖上有效電阻與首達時間的計算方法
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 在圖論中,若有某一點屬於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   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明