Acyclic digraph

To conclude this section, we note quickly a few other asymptotic enumerations. In [PalE70] Palmer found an asymptotic estimate for the number of self-complementary graphs and digraphs. Robinson [RobR76] and Stanley [StaR73] enumerated acyclic digraphs, and obtained the asymptotic estimate... 

C. The asymptotic number of acyclic digraphs. To appear in Combinatorica. 

RobR70 Robinson, R. W. Enumeration of acyclic digraphs. Combinatorial Mathematics and Its Applications (R. C. Bose, et. al. eds.) Univ. of North Carolina, Chapel Hill (1970) 391-399. 

RobR73 Robinson, R. W. Counting labeled acyclic digraphs. New Directions in the Theory of Graphs (F. Harary, ed.)... 

RobR76 Robinson, R. W. Counting unlabeled acyclic digraphs. 

A MCDD can be characterized as an acyclic digraph whose starting node, S, has a nil predecessor [i.e., F (S) = 0] labeled with the name of the system the model is intended to represent. The successor nodes of S, F (S), are labeled with the names of the first-level components of the model. Each of these first-level constituent entities may itself be decomposed into second-level entities, which will be represented by new successor nodes in the digraph, i.e., F [r (S)]. Thus, the model of any node, jc, is the... 

Since fi ti) = tj fi 2)+ is a non-decreasing function in t., the optimal solution to the above is clearly to set f, as small as possible, subject to satisfying all the constraints. This is the dual version of the classical longest path problem in an acyclic digraph, and can be solved easily using a simple dynamic program. The for die source node is set to the smallest possible value (i.e. r-), and for a non-source node j, if S is the set of predecessors in Gj, then... 

---