| Line 17: | Line 17: | ||
* A ''subgraph'' G' of a graph G=(V,E,f) is a graph (V',E',f') such that | * 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 <math>e_i</math> is incident to <math>V_i</math> and <math>V_{i+1}</math>, for each i=1,2, | + | * 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 <math>e_i</math> is incident to <math>V_i</math> and <math>V_{i+1}</math>, for each <math>i=1,2,\dots,k-1</math>. (<math>V_1 e_1 V_2 e_2 V_3 \dots V_{k-1} e_{k-1} V_k</math>) |
* A graph is "''connected''" if a path exists between any two vertices in the graph | * A graph is "''connected''" if a path exists between any two vertices in the graph | ||
Revision as of 09:44, 8 April 2008
Graph Theory Clustering
dataset $ \{x_1, x_2, \dots , x_d\} $ no feature vector given.
given $ dist(x_i , x_j) $
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 $ e_i $ is incident to $ V_i $ and $ V_{i+1} $, for each $ i=1,2,\dots,k-1 $. ($ V_1 e_1 V_2 e_2 V_3 \dots V_{k-1} e_{k-1} V_k $)
- A graph is "connected" if a path exists between any two vertices in the graph
- A component is a maximal connected graph. (i.e. includes as many nodes as possible)
- A maximal complete subgraph of a graph G is a complete subgraph of G that is not a proper subgraph of any other complete subgraph of G.
- A cycle is a path of non-trivial length k that comes back to the node where it started
- A tree is a connected graph with no cycles. The weight of a tree is the sum of all edge weights in the tree.
- A spanning tree is a tree containing all vertices of a graph.
- A minimum spanning tree (MST) of a graph G is tree having minimal weight among all spanning trees of G.
