ISSN:
1522-9602
Source:
Springer Online Journal Archives 1860-2000
Topics:
Biology
,
Mathematics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02476692
