Graph Theory

  Graph theory is a branch of topology which, although going back to L. Euler, has received particular interest only in recent years, as its applications in electrical engineering and operations research lend themselves readily to algorithmic formulation and solutions on digital computers. Also, computer science itself finds numerous applications of graph theory, like in computer networking and the structuring of data [Deo74].

Graph theory formalizes the relations of entities called graphs, which consist of two sets of objects called nodes (or vertices) and edges, each edge connecting two nodes. A vertex has the degree d, if it has d incident edges. Two vertices are adjacent if they have a common edge. A walk is a sequence of connected vertices and edges; a trail is a walk in which no vertex is included more than once.

An important graph is the tree, which is a graph containing no loops, and for which therefore the relation holds. Given a metric (a distance function for nodes), edges can be assigned a numerical value, e.g. the Euclidean distance between its two end-points (graphs are in n-space). It is then possible to define a minimum spanning tree which is that tree for a given set of nodes, for which is minimal, where e_ij is the value associated to the edge connecting the nodes i and j, and the sum is over all edges.

It is comparatively easy to write an algorithm for the minimum spanning tree [Zahn71], and the concept has been applied in the recognition of tracks from digitizings ([Zahn73], [Cassel80]) and for cluster recognition in multi-dimensional space.

Another application of a graph-theoretical notion, the compatibility graph, is useful in pattern recognition, for deciding between conflicting candidates using the same raw data. The problem to be solved there arises when low-level information (e.g. digitizings or track segments) can be connected to give a higher-level result (track) in several conflicting ways. The decision as to which of the possible sets of tracks compatible with each other is to be chosen, makes use of criteria like , the amount of unused information, etc. The compatibility graph is simply an aid in picking all possible non-conflicting sets. For more on graph theory, see [Chartrand85] or [Skiena90].