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,EG=(V,E) consists of a finite set of vertices VG=v1,v2,,vnV(G)=\{ v_{1},v_{2},\cdots,v_{n}\} and a finite set of edges EG=e1,e2,,enE(G)=\{ e_{1},e_{2},\cdots,e_{n}\}.

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

A labeling (or ordering) of the graph GG is a mapping of the set 1,2,,V\left\{ 1,2,\cdots,\left|V\right|\right\} onto VGV(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.

Graph Nomenclature Topics