最小切割樹群聚演算法極端情形之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：241

、訪客IP：3.134.102.182

姓名

李鴻聰(Hong-Chung Lee) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

最小切割樹群聚演算法極端情形之研究
(A Study on Extreme Conditions of Minimum Cut Tree Clustering Algorithm)

相關論文

★ 一種減輕LEO衛星網路干擾的方案	★ 萃取駕駛人在不同環境之駕駛行為方法
★ 非地面網路中基於位置的隨機接入分配方法	★ TrustFADE: 針對可程式化邏輯區塊之安全認證方法
★ 捷徑問題在特殊圖形上之演算研究	★ 行動電腦教室與其管理系統的設計與建置
★ 蛋白質體視覺化系統之實作	★ 教室內應用無線科技之一對一數位學習模式
★ 蛋白質交互作用網路之視覺化系統	★ 以賓果式遊戲輔助技巧熟練之數位學習環境設計與實作
★ 蛋白質註解的三維視覺化工具	★ Joyce 2：一個在一對一數位教室環境下之小組競爭遊戲
★ 同儕計算網路上內文散佈演算法之實作與效能評估	★ 在直角多邊形上使用基因演算法畫樹之研究
★ 經由潛在語義的線索從蛋白質交互作用網路進行蛋白質功能的預測	★ 從生物文件中萃取出蛋白質或基因之名稱

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

群聚分析對於分析檢視資料之間的複雜結構是一種非常有效的工具，其應用領域相當廣泛，含蓋了生物資訊、影像處理和商業交易等範圍。群聚分析根據某些法則，比如最短距離或最小切割，來對資料作分群，使得同一群內的元素間關聯性強而群與群之間的關聯弱。
在此篇論文中，我們特別探討由G.W. Flake等人所提出的群聚演算法──最小切割樹演算法，並分析出此演算法對某些圖形無法作分群，亦即分群的結果就只有兩種可能：一群或群，其中為圖形的點數。我們得到一滿足此現像的充分必要條件，並且發現某些圖形滿足這個條件。

摘要(英)

Clustering algorithms are effective tools for exploring the structure of complex data sets. There are a lot of applications for clustering algorithms, including bioinformatics, image recognition, business transactions, etc.
The minimum cut tree clustering algorithm is using maximum flow techniques to cluster the data (graphs). We prove that two kinds of graph, i.e. graph with edge connectivity and a graph with a vertex connected to every other vertex, are the extreme conditions in the algorithm.

關鍵字(中)

★ 政治圖形
★ 正規圖形
★ 群聚演算法
★ 最小切割樹
★ 極端情形
★ 邊連通

關鍵字(英)

★ extreme conditions
★ politician graph
★ regular graph
★ clustering
★ Minimum cut tree
★ edge-connectivity

論文目次

Contents
1 Introduction 1
2 Related Works 2
2.1 Maximum Flows and Minimum Cuts 2
2.1.1 Maximum Flows 2
2.1.2 Minimum Cuts 3
2.2 Flow Equivalent Trees and Minimum Cut Trees 4
2.2.1 Flow Equivalent Trees 4
2.2.2 Minimum Cut Trees 5
2.3 Two Algorithms for Constructing Minimum Cut Trees 8
2.3.1 Gomory and Hu’s Agorithm 8
2.3.2 Gusfield’s Agorithm 13
2.4 The Minimum Cut Tree Clustering Algorithm 14
2.5 Some Properties of Parametric Networks and Minimum Cut Tree Clustering Algorithm 16
2.5.1 Breakpoints 16
2.5.2 Critical Points 19
2.6 Extreme Graphs and Super Extreme Graphs 20
2.6.1 Extreme Graphs 20
2.6.2 Super Extreme Graphs 21
3 Main Results 23
3.1 A Criterion for Extreme Graphs 23
3.2 Politician Graphs 24
3.3 Regular Graphs 26
3.3.1 Cages 27
3.3.2 Connected Symmetric Graphs 27
4 Conclusions 29
5 Biliography 30
List of Figures
Figure 2.1: An undirected network and three of its flow equivalent trees. (a) An undirected network. (b)-(d) Flow equivalent trees. 5
Figure 2.2: An undirected network and two of its minimum cut tree. (a) An undirected network. (b) A minimum cut tree. (c) A minimum cut tree. 7
Figure 2.3: Construction of a minimum cut tree of . Find a corresponding minimum cut on the left, and build up the minimum cut tree on the right. 12
Figure 2.4: The minimum cuts which do not cross each other. 12
Figure 2.5: A minimum cut tree and its corresponding MCT partition of when . (a) An undirected network . (b) A new network . (c) A minimum cut tree . (d) A MCT partition of . 15
Figure 2.6: Weights and Breakpoints. (a) Weight of cut. (b) Weight of minimum cut. 17
Figure 2.7: Graph with 5 vertices and unit weight on each edge. 20
Figure 2.8: Cycle graph . 22

參考文獻

Bibliography
[1] J. W. Han and M. Kamber, Data Mining: Concepts and Techniques, Morgan Kaufmann, 2000.
[2] A. K. Jain and R. C. Dubes, Algorithms for Clustering Data, Prentice Hall, 1988.
[3] B. Stein and O. Niggemann, "On the Nature of Structure and its Identification," Springer, pp. 122-134, 1999.
[4] E. Hartuv and R. Shamir, "A Clustering Algorithm based on Graph Connectivity," Information Processing Letters, pp. 175-181, 2000.
[5] An Algorithm for Partitioning the Nodes of a Graph," Journal of Society for Industrial and Applied Mathematics, Vol. 3, No. 4, pp. 541-550, 1982.
[6] B. W. Kernighan and S. Lin, "An Efficient Heuristic Procesure for Partitioning Graphs," The Bell System Technical Journal, pp. 291-307, 1970.
[7] G. W. Flake, K. Tsioutsiouliklis, and R. E. Tarjan, "Graph Clustering Techniques based on Minimum Cut Trees," Technical Report 2002-06, 2002.
[8] Peng, D. R., "Implementation of Visualization System for Proteomics." 2003.
[9] T. C. Hu, Combinatorial Algorithms, Addison-Wesley, 1982.
[10] L. R. Ford and D. R. Fulkerson, "Maximum Flow Through a Network," Canadian Journal of Mathematics, Vol. 8, No. 3, pp. 399-404, 1956.
[11] R. E. Gomory and T. C. Hu, "Multi-terminal network flows," Journal of Society for Industrial and Applied Mathematics, Vol. 35, No. 4, pp. 921-940, 1961.
[12] G. Gallo, M. D. Grigoriadis, and R. E. Tarjan, "A Fast Parametric Maximum Flow Algorithm and Applications," Siam Journal of Computing, Vol. 18, No. 1, pp. 30-55, 1989.
[13] L. Sunil Chandran and L. Shanker Ram, "On the Number of Minimum Cuts in a Graph," Springer, 220-229, 2002.
[14] H. L. Fu, K. C. Huang, and C. A. Rodger, "Connectivity of Cages," Journal of Graph Theory, Vol. 24, No. 2, pp. 187-191, 1997.
[15] P. Wang, B. G. Xu, and J. F. Wang, "A note on the edge-connectivity of cages," The Electronics Journal of Combinatorics, Vol. 10, No. 2, 2003.
[16] W. T. Tutte, Graph Theory, Addison-Wesley, 1984.

指導教授

何錦文(Chin-Wen Ho)

審核日期

2004-1-29

推文