顏嗣鈞臺灣大學：電機工程學研究所林淑棻Lin, Shu-FenShu-FenLin2007-11-262018-07-062007-11-262018-07-062007http://ntur.lib.ntu.edu.tw//handle/246246/53332在資訊科學研究中，圖形切割問題廣泛出現在多種領域內，其中也包括圖形繪製。在圖形繪製中，一個好的呈現在於是否將各節點間的相互關係表現出來。而區分的方式便是利用圖形切割演算法。 在本篇論文中，我們提出一個與過去不同的切割方法，先在樹上做切割，再對應到圖形上，藉以區分不同群集，進行一連串調整的動作找出最佳解，而最後利用force-directed placement的方法將圖形繪製出來。 過去在找尋k-partition的方法，最典型的是將原圖切割成兩份，再將其中一份切成兩份，以此類推，最後再稍作調整，而在本篇論文中，我們亦提出了一個方法，直接將原圖切成k份，但仍保留過去的方法以提供選擇。我們也分析何時採用何種方法較好，利用test graph 來測試兩者間的差異。 此篇論文最主要的貢獻在於：第一、提出與過去不同的方式來解決圖形切割的問題，第二、可利用此演算法來找出大概的群集數，第三、利用force-directed placement繪製圖形時，若將原圖分群可加速圖形達到穩定狀態。The graph partitioning problem arises in many areas of computer science, including the application to graph drawing. In graph drawing, a good layout explicitly shows the relationship between all nodes. We present a graph partitioning algorithm based on tree partitioning to clearly separate one cluster from another, make some adjustments on clusters and find the best partition. Finally, we use force-directed placement algorithm to demonstrate the result in a visual form. The traditional solution to k-way partition is to find bisection recursively and generalize it into k partitions. We demonstrate another algorithm to divide the graph into k parts directly with some adjustments. These two ways for the k-way partition problems are compared empirically later. Our contributions lie in providing a graph partitioning algorithm from different perspectives with lower complexity than before. In addition, we can find the number of clusters approximately using the algorithm presented in this thesis. While applied in graph drawing, this algorithm could reduce the number of steps in a force-directed placement algorithm.Acknowledgement…………………………………………………………………… i Abstract (Chinese) …………………………………………………………….. ……ii Abstract (English) ……………………………………………………………... ……iii Contents……………………………………………………………………………… iv List of Figures………………………………………………………………….. ……vi List of Tables………………………………………………………………………… viii Chapter 1 Introduction …………………………………………………………1 Chapter 2 Preliminaries …………………………………………………………5 2.1 Tree Partition with Shifting Techniques ………………………………5 2.2 Famous Approaches for Graph Partitioning …………………………8 2.2.1 Kernighan-Lin Graph Bisection Algorithm ……………………… 8 2.2.2 Simulated Annealing ………………………………………………10 2.2.3 Genetic Algorithm ………………………………………………10 Chapter 3 Algorithms for Most Uniform Tree Partitioning Problem …………11 3.1 Exhaustive Procedure ……………………………………………………12 3.2 UTP_R ……………………………………………………………………13 3.3 UTP_H ……………………………………………………………………15 Chapter 4 Unbalanced Graph Partitioning ……………………………………19 4.1 Initial Graph Partitioning ………………………………………………19 4.2 Local Improvement ……………………………………………………21 4.2.1 An Example …………………………………………………………22 4.2.2 Algorithm of Adjustments …………………………………………26 4.2.3 Algorithm of Graph Partitioning ………………………………32 Chapter 5 Application in Graph Drawing ……………………………………36 Chapter 6 Conclusions and Future Works ……………………………………46 References …………………………………………………………………………49893801 bytesapplication/pdfen-US多層次非均衡圖形切割樹切割移動演算法圖形繪製multilevel unbalanced graph partitioningtree partitioningshifting algorithmgraph drawingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53332/1/ntu-96-R94921090-1.pdf