Data Clustering: A Review 5.2.2 Graph-Theoretic Clustering 発表者：吉村 裕一
Graph-theoretic divisive clustering グラフ理論的クラスタリングは最小スパニング樹(minimal spanning tree;MST) データ構造に 基づいている。 クラスタを発生させるように最も大きい長さのMST辺を削除する。
MSTによるクラスタリング例 トップダウン型
Single- link and Complete-link 最小スパニング樹のsubgraph。 Complete-linkはmaximal complete subgraph であり、 グラフのノードの着色性に関連する。 最大完全な部分グラフはクラスタの最も厳しい定義であると考えられている
階層型以外の構造への適用 非階層型構造、重複クラスタに対するグラフ指向のアプローチ 1985年 OzawaによってDelaunay graph(DG)が提案
Delaunay graph すべての組のポイントを接続し、それをvoronoi neighbors と呼ぶ。 このグラフはMSTやrelative neighborhood graph (RNG)[Toussaint 1980]の中のすべての近傍情報を含んでいる。