請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33886
標題: | 論賦向完全多部圖之最小直徑 On the Minimum Diameter among Orientations of Complete Multipartite Graphs |
作者: | Chien-Yeh Chen 陳建燁 |
指導教授: | 張鎮華 |
關鍵字: | 賦向,完全多部圖,直徑, diameter,orientation,complete multipartite graph, |
出版年 : | 2006 |
學位: | 碩士 |
摘要: | Robbins 研究單行道問題時,證明了一個連通圖有強定向的充分必要條件是此圖中沒有橋。除了強定向的存在性之外,一個有趣且實際的問題是,這些強定向的最小直徑的長度為何? 更精確地說,對於一個給定的圖 G ,用 D(G) 表示圖 G 的所有強定向所成的集合。圖 G 的每一種定向都有一個直徑,其中最小的直徑其長度記為d(G), 是我們所要決定的目標參數。
關於完全多部圖的 d(G) 值,已知是 2 或 3 ,但是在許多情形下,還無法決定究竟是 2 還是 3 。在這篇論文中,我們決定了一些完全三部圖的 d(G) 值。此外,我們找到了 d(G) 值為 2 的一類部數大於三的完全多部圖。 On investigating the one-way street problem, Robbins proved that a connected graph has a strong orientation if and only if it has no bridges. An interesting and practical problem is that, besides the existence of a strong orientation, what is the minimum diameter of such an orientation. More precisely, for a given graph G, denote D(G) the family of all strong orientations of G. The object parameter then is d(G) = min{d(D) : D 2 D(G)}. Denote K(p1, p2, . . . , pn) the complete n-partite graph having pi vertices in the ith partite set. While it is known that 2< = d(K(p1,p2, . . . , pn)) < = 3 for n > = 3, there are still many ~d(K(p1, p2, . . . , pn)) remain un-determined. In this thesis, we establish some new results. We determine d(G) of some complete 3-partite graphs. Also, we find a family of complete multipartite graphs G with d(G)=2, for n>3. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33886 |
全文授權: | 有償授權 |
顯示於系所單位: | 數學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 425.55 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。