Acyclic Digraph

Author

Eric W. Weisstein
May 20, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/AcyclicDigraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/AcyclicDigraph.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Enumeration

Unlabeled

Count[#,_?AcyclicQ]&/@Digraphs/@Range[5]//Timing

Labeled

a[0]:=1
a[n_]:=a[n]=Sum[-(-1)^k Binomial[n,k]2^(k(n-k))a[n-k],{k,n}]

a/@Range[10]

Plots

ShowGraphArray[Select[#,AcyclicQ]&/@Digraphs/@Range[3],GraphicsSpacing->.4]