| Line 16: | Line 16: | ||
Definitions: | Definitions: | ||
| − | * A complete graph is a graph with d(d-1)/2 edges. | + | * 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 ''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 ''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 | + | * 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 ''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 ''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 ''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 ''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 ''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. | + | * A ''minimum spanning tree'' (MST) of a graph G is tree having minimal weight among all spanning trees of G. |
Revision as of 10:37, 8 April 2008
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
- 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.
