层次聚类中用到的图论知识
p层次聚类是需要一点图论的理论知识,整理了一些网上的资料。
图(Graph)是在聚类分析中有多种用途的一种数学结构。
图是由两个集合构成,顶点的集合用
多重边和环
若图G中,某个边e的两个端点相同,则称e是环,若两个点之间的边多于一条,则称这些边为多重边。一个无环,无多重边的图称为简单图,聚类中只用到简单图,不允许有环和多重边的出现。
子图(subgraph)
如果V’是V的一个子集,E’是E的一个子集,那么图H=(V’,E’,f’)就是图G=(V,E,f)的一个子图。可以看出子图H里面的顶点和边都是G中已有的。
上图的三个子图
连通图与连通分图(component)
图G中,若任何两个点之间,至少有一条链,则称G是连通图,否则称为不连通图。若G是不连通图,它的每个连通的部分称为G的一个连通分图。上面三个子图都是不连通图。下面是一个不连通图的的2个连通分图。
完全图(complete graph)
若一个图的每一对不同顶点恰有一条边相连,则称为完全图。完全图是每对顶点之间都恰连有一条边的简单图。n个顶点的完全图有n个端点及n(n − 1) / 2条边。
最大完全子图
如果图H是图G的最大完全子图(maximal complete subgraph),显然必须满足三个条件
一:H必须是G的一个子图(subgraph)
二:H必须是一个完全图(complete)
三:H不能是其它完全子图的子图,它得是最大的那个完全子图(废话)
在全连接算法里面我们会用到这个概念。
最大连接子图
最大连接子图(maximal connected subgraph),其实就是上面介绍的连通分图(component),在单连接算法中会用到。