1 Graph Nomenclature

Data structures and algorithms derived from graph theory form the basis for many network analysis techniques. A brief review of the most relevant aspects of computational graph theory follows. An excellent introduction to the subject is found in Aho, Hopcroft, and Ullman(1983) [1]. Horowitz and Sahni (1978) [2] cover similar material in a more disjointed fashion. Even (1980) [3] provides a more theoretical examination of the subject.

The graph $G=(V,E)$ consists of a finite set of vertices $V(G)=\{ v_{1},v_{2},\cdots,v_{n}\}$ and a finite set of edges $E(G)=\{ e_{1},e_{2},\cdots,e_{n}\}$.

Each edge corresponds to a pair of vertices. If edge $e$ corresponds to the vertex pair $(v,w)$, then $e$ is incident upon vertices $v$ and $w$. The number of vertices in $V(G)$ is indicated by $|V|$. The number of edges in $E(G)$ is indicated by $|E|$.

A labeling (or ordering) of the graph $G$ is a mapping of the set $\left\{ 1,2,\cdots,\left|V\right|\right\}$ onto $V(G)$.

The usual convention for drawing a graph, is to represent each vertex as a dot and each edge as a line connecting two dots. If the graph is directed, an arrow is superimposed on each edge to show its orientation.