The Number of Paths and Cycles in a Digraph

Publisher Website
Google Scholar
Abstract
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 vi to a point vj; the diagonal entry i, i gives the number of cycles of length n containing vi. 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.

This publication has 4 references indexed in Scilit: