Graph Theory Clustering
dataset {x1, x2, ... , xd} no feature vector given.
given dist(xi, xj)
Construct a graph:
node represents the objects.
edges are relations between objects.
edge weights represents distances.
Definitions:
A complete graph is a graph with d(d-1)/2 edges.
A subgraph G' of a graph G=(V,E,f) is a graph (V',E',f') such that
A path in a graph between Vi,Vk is an alternating sequence of vertices and edges containing no repeated edges and no repeated vertices and for which ei is incident to Vi and Vi+1, for each i=1,2,...,k-1. (V1 e1 V2 e2 V3 ... Vk-1 ek-1 Vk)
A graph is "connected" if a path exists between any two vertices in the graph
