The Number of Paths and Cycles in a Digraph

An algorithm is presented for constructing from the adjacency matrix of a digraph the matrix of its simple n -sequences. In this matrix, the i, j entry, i ≠ j , gives the number of paths of length n from a point v i to a point v j ; the diagonal entry i, i gives the number of cycles of length n containing v i . The method is then generalized to networks—that is, digraphs in which some value is assigned to each line. With this generalized algorithm it is possible, for a variety of value systems, to calculate the values of the paths and cycles of length n in a network and to construct its value matrix of simple n -sequences. The procedures for obtaining the two algorithms make use of properties of a line digraph—that is, a derived digraph whose points and lines represent the lines and adjacency of lines of the given digraph.