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 G=(V,E) consists of a finite set of vertices V G = v 1 , v 2 , , v n V(G)=\{ v_{1},v_{2},\cdots,v_{n}\} and a finite set of edges E G = e 1 , e 2 , , e n E(G)=\{ e_{1},e_{2},\cdots,e_{n}\} .

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

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

Graph Nomenclature Topics