顏嗣鈞臺灣大學：電機工程學研究所何明彥Ho, Ming-YenMing-YenHo2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53578對於圖形繪製演算法而言，結合了多層次技巧以及力導向演算法的概念可以用來處理大型圖形。 然而對於原始大型圖形來說，由於頂點過多，所以必須要將頂點分群以便於了解。而分群不僅僅是讓使用者能輕易地對圖形了解，更是將圖形還原成原始要探討的問題時所重視的。因為對於原始問題而言，如果能夠將這些具有相同特性的實體聚集起來，可以讓使用者面對這些實體時，能一目瞭然，而簡化成易於處理的問題。 結合多層次技巧以及力導向演算法的方法雖然可以處理大型圖形，但是無法表達嵌入式叢集的概念，因為對於直線畫法而言，重視的是能快速的畫出圖形、以及較美觀的圖形。 所以在這裡提出了一個做法能夠在直線畫法中表現出嵌入式叢集的概念；而這個方法是架構在結合多層次技巧以及力導向演算法之上。由於多層次技巧的兩個步驟中，皆是為了便於力導向演算法的實作，故在其兩個步驟中，分別採用不同的做法以求達到可以利用力導向演算法在原始圖形中畫出具有嵌入式叢集的美感。利用我們提出的改良式多層次力導向演算法 ，可以在直線畫法中用來繪製大型叢集圖形。To draw large clustered graphs, a force-directed method combine with the multilevel technique is presented. As a large graph containing a huge number of vertices, a key step in drawing such a graph is to group those entities which have attributes in common to reduce the original problem size. Although the force-directed method which combines the multilevel technique can handle large graphs, it cannot express embedded clustered graphs very well. That is because straight-line drawing only cares about drawing graphs faster and nicer. We describe a method that can use straight-line drawing to show embedded clustered graphs. We alter the multilevel algorithm mentioned above to achieve the goal of aesthetic. As our experimental results indicate improved multilevel algorithm allows large clustered graphs to be drawn nicely.第一章 緒論 6 第一節 前言 6 第二節 研究動機 10 第三節 問題簡介 12 第四節 論文架構 14 第二章 理論基礎 16 第一節 彈簧演算法 (Spring Algorithm) 16 第二節 多層次演算法 (Multilevel Algorithm) 22 第三章 研究內容 27 第一節 圖形加工 (Graph Coarsening) 27 第二節 圖形回覆 (Graph Uncoarsening) 43 第四章 實驗結果 47 第五章 結論與未來展望 57 第六章 參考文獻 60665217 bytesapplication/pdfen-US圖形繪製演算法多層次演算法力導向演算法Graph drawing algorithmMultilevel algorithmForce-directed algorithmthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/53578/1/ntu-94-R92921084-1.pdf