Entropy and the complexity of graphs: II. The information content of digraphs and infinite graphs

In a previous paper (Mowshowitz, 1968), a measureI _g (X) of the structural information content of an (undirected) graphX was defined, and its properties explored. The class of graphs on whichI _g is defined is here enlarged to included directed graphs (digraphs). Most of the properties ofI _g observed in the undirected case are seen to hold for digraphs. The greater generality of digraphs allows for a construction which shows that there exists a digraph having information content equal to the entropy of an arbitrary partition of a given positive integer. The measureI _g is also extended to a measure defined on infinite (undirected) graphs. The properties of this extension are discussed, and its applicability to the problem of measuring the complexity of algorithms is considered.