Reversed graph

The definition of a graph which we have employed is not the usual one to be found in the literature; technically our graphs are called digraphs (a contraction of ``directed graph''). The reasons are historical, inasmuch as the concern with a graph was the linkages between is nodes which were originally conceived as a mutual connection between the two nodes involved.

From the point of view of an algebraic treatment of the connectivity matrix, symmetrical linkages are desirable because they lead to symmetrical matrices, for which there are much more convenient estimates of eigenvalues and procedures for obtaining the eigenvectors and eigenvalues.

On the other hand, actual eigenvalues (other than the largest and possibly the second largest) do not have much direct application to graphs, nor is the decomposition according to eigenvectors particularly relevant. Consequently there is little reason to insist upon symmetrical linkages, particularly given the existence of a very complete theory of positive (asymmetrical) matrices which does include the most useful aspects of eigenvalues and eigenvectors.

Applications to automata envisage directed links, just as the development given so far supposes, and certainly encompass the symmetrical case --- just include every link twice, once in each direction. A symmetrical graph is just a special case; every graph can be symmetrized by adjoining reverse links, and one can define the reverse of any graph : merely reverse every link.

The connectivity matrix of a reversed graph is the transposed matrix, described by the reversed regular expression, in which each sequence is written backwards.

---

Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx