(18.210.22.132) 您好！臺灣時間：2019/10/14 21:22

### 詳目顯示:::

• 被引用:0
• 點閱:122
• 評分:
• 下載:8
• 書目收藏:0
 在圖論中，若有某一點屬於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 �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.
 摘要...........................................iAbstract......................................ii致謝.........................................iiiContents......................................iv1.Introduction.................................12.Finding the n-median of a block graph........33.Some notes in Steiner medians...............11Reference.....................................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 withApplications, 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.htmlO.R.Oellermann,On Steiner centers and Steiner medians ofgraphs, 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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 17.邱駿彥（1998）《日本勞工派遣法之現狀》，就業與訓練。 2 4.成之約（1998）《淺論派遣勞動及其對勞資關係的影響》，就業與訓練。 3 41.楊通軒（1999） 我國部分時間勞動法律問題之探討— 兼論德國之部分時間勞動法制，蒐錄於國立中正大學法學集刊第二期，1999.7，第290∼291 頁。 4 44.劉秀珍（2000）“人才派遣業在促進就業所扮演的角色”勞資關係月刊，第17卷第9期。

 1 2 3 G-設計上交集區塊彼此互斥的問題 4 密碼學的發展與應用 5 正立方體在多面體上的投影TheCubeProjectiononSolids 6 圖形列表著色 7 高階橢圓偏微分方程解的存在性及其行為之研究 8 三角不等式與Jensen不等式之精化 9 隨機右設限數據之風險率的貝氏估計方法 10 一些退化擬線性波動方程的解的性質. 11 對接近音速流量可壓縮尤拉方程式的柯西問題去架構區間逼近解 12 週期為r之週期點個數的平均值 13 九十四學年度高一學生三角函數之學習狀況研究 14 15 台灣與新加坡三角函數課程之教科書比較

 簡易查詢 | 進階查詢 | 論文瀏覽 | 熱門排行 | 我的研究室