Abstract
考慮在廣大的平面上有一群可以互相通訊的郵局，每一郵局具備了一個通訊發射器。此發射器的功率可以將訊息傳送到t 距離範圍內的每一角落。如果所有的郵局彼此之間的距離都在t 距離範圍之內，則所有的郵局都可以彼此的傳送訊息而無所阻礙。然而，如果有些郵局之間的距離超過t ，則吾人想知道，是否這些郵局能分成2 組，使得每一組內的郵局彼此間都能傳送訊息。為了節省能源，吾人希望能儘可能的降低發射器的功率。因此，吾人不禁要問：能將這些郵局分成2 組且使得每組內的郵局彼此間都能傳送訊息之最小的t 是多少﹖上述的問題是一大堆有關將物體群集化之問題中典型的一個。所謂〞物體群集化問題〞基本上是討論如何將n 個物體分成k 個不同的集合（稱之為〞群集〞）。將物體群集化之問題發生於很多方面，例如，資料的壓縮（data compression），圖型識別（pattern recognition），樣本選取（point sampling） ，多磁碟資料安排問題（multi- disk data allocation problem ）等問題。由於此類問題之應用層面極為廣大，因此就有許多不同變型的問題產生。而這些問題之間最大的不同點在於其目在函數（objective function）的不同。通常這些目的函數是取決於兩物體之間的相似程度而言。有時候，一個群集化之問題可以用一圖形（weighted undirected graph ）來描述。因此，物體便能用一組節點（vertex）來代表，而物體之間的相似程度也可用兩節點之間連線（edge）的成本（weight）來表示。吾人亦可以考慮在幾何平面（Euclidean plane ）上之群集化問題。在幾何平面上，物體可用一群（point ）來表示，而兩物體間的相似程度則用兩點之間的平面距離來表示。須注意的是，吾人可將在幾何平面上群集化問題用圖形來表示，此時，任意兩個節點（vertex）都存在有一連線（edge），而連線上的戶本則就是此兩點間的平面距離了。為了不同的目的，其目的函數便可以不同的定義，例如，最大最小化之群集問題（mini- max ）是要將所有群集內之最大差異程度中之最大者儘可能的最小化。群集和最小化問題（mini- sum ）則是希望將所有群集內之最大差異程度的總和最小化。除此之外，每一群集內含有物體之個數亦可以是考慮的因素。此類問題亦被前人所研究過。其動機是來自於一般化範圍資料搜尋問題（generalized rangesearch problem in data retrieval）。至於其它不同的目的函數，有興趣的讀者可參考〔Brucker 19--〕，以求得更詳盡的說明。基本上，群集化問題已被廣泛地討論過。例如，Brucker〔Brucker 19--〕及Johnson〔JOhnson1982〕分別證明當k>=3時，mini- max的群集問題在圖形模式及在平面空間上都是NP- complete.同時，這類問題之次最佳解（suboptimal solution）亦被討論。如，Gonzalez〔Gonzalez 1985〕證明對mini- max之k 群集化問題而言，即是要求到比最佳解差α倍，α<1.-32。此問題仍是NP- hard.之後，Feder及Greene〔Feder andGreene 1988〕證明此問題在α<1.969時仍是NP- hard。由以上的討論可以得知，這類問題是非常解決的。因此，吾人將重心放在k= 2之情況上。也就是說，在本論文中，吾人專門討論一些二群集問題。本論文最大結果是發現了利用最小生成樹（minimum spanning tree）及最大生成樹（maximum spanningtree）的性質，可以解決一系列之二群集問題。也就是說，吾人提出了一通用性的方法，來分割一群物體成兩個群集。而此分割是根據最小生成樹（minimun spanningtree），或最大生成樹（maximum spanning tree ）。除此之外，吾人亦發現了一些特殊之幾何性質，可以用來解決一些平面二群集之問題。而這些性質亦是根據最大生成樹（maximum spanning tree）所求得的。///////ABSTRACTConsider a set of communication posts on a large plane. Each post isequipped with a transmitter that can reach some distance t from the post.If all the posts are within distance t of each other, all can communicatewithout difficulty. Suppose, however, that some posts are further than tunits apart. We would like to know if the posts can be split into twogroups so that within each group each pair of posts may communicate. Inorder to conserve energy, we wish to reduce the power of the transmittersas much as possible. Accordingly, what is the smallest t for which such apartition into two group is possible﹖The above problem is typical of a large class of problems that have beenstudied reccntly, that concern the clustering of a set of objects. Theproblem of clustering a set of objects arises in many disciplines, forexample, data compression, pattern recognition and service siteassignment. Because of the wide range of applications, there are manyvariations of this problem. The main difference between these problems isin the objective function. Many different objective functions have beenconsidered by many researchers. These objective functions usually dependon the dissimilarity between any two objects.Generally speaking, the clustering problem is to partition a set of nobjects into k nonempty disjoint subsets, called clusters. Manycomputational complexities have been discovered for different clusteringproblems. Since many clustering problems, when k>=3 have been proved to beNP- complete, we concentrate on the clustering problems when k=2, or2- clustering problems.In this dissertation, we discuss the following 2- clustering problems: thedual satisfaction problem, the farthest pair partition problem, theconstrained farthest pair partition problem, minimum diameter partitionproblem, the specified diameter partition problem and the Euclideanmini- sum 2- clustering problem.The first three problems are defined and solved on the graph model. Wepropose a uniform approach, called the spanning tree vertex labelingapproach, to partition the input vertex set into two disjoint subsets.Essentially, we construct a minimum, or maximum spanning tree, dependingupon the problem. We then partition the vertices based upon the treeconstructed. Our approach is easier to understand and easier to implement.The last three problems are discussed on Euclidean plane. that is, theinput of the problem is a set of points in 2- dimensional plane. Wediscover some geometric properties that can be used to find the optimalsolution efficiently. The geometric properties are developtd by using theconcept of maximum spanning tree of points. We found that the reason thatwe can devise more better algorithms than others is we do not consider somany pairs of points. In fact, we only consider those pairs of points thatrelated to the maximum spanning tree of points.