張鎮華臺灣大學：數學研究所陳建燁Chen, Chien-YehChien-YehChen2007-11-282018-06-282007-11-282018-06-282006http://ntur.lib.ntu.edu.tw//handle/246246/59504Robbins 研究單行道問題時，證明了一個連通圖有強定向的充分必要條件是此圖中沒有橋。除了強定向的存在性之外，一個有趣且實際的問題是，這些強定向的最小直徑的長度為何? 更精確地說，對於一個給定的圖 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.Acknowledgements i Abstract in Chinese ii Abstract in English iii 1 Introduction 1 2 Preliminary 4 3 The value of d(K(p1, p2, p3)) 7 4 Graphs K(p1, . . . , pn) with d(K(p1, . . . , pn)) = 2, for n > = 4 16 References 26435763 bytesapplication/pdfen-US賦向完全多部圖直徑diameterorientationcomplete multipartite graphthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/59504/1/ntu-95-R93221001-1.pdf