Simple Directed Graph
A simple directed graph is a directed graph having no multiple edges or graph loops (corresponding to a binary adjacency matrix with 0s on the diagonal). The number of simple directed graphs of n nodes for n=1, 2, ... are 1, 3, 16, 218, 9608, ... (OEIS A000273), which is given by NumberOfDirectedGraphs [n] in the Wolfram Language package Combinatorica` . The directed graphs on n nodes can be enumerated as ListGraphs [n, Directed] in the Wolfram Language package Combinatorica` .
A simple directed graph on n nodes may have between 0 and n(n-1) edges. The number of simple directed graphs on n nodes with m edges can be given by NumberOfDirectedGraphs [n, m] in the Wolfram Language package Combinatorica` . The triangles of graphs counts on n nodes (rows) with m edges (columns) is given below (OEIS A052283).
A complete graph in which each edge is bidirected is called a complete directed graph. A directed graph having no symmetric pair of directed edges (i.e., no bidirected edges) is called an oriented graph. A complete oriented graph (i.e., a directed graph in which each pair of nodes is joined by a single edge having a unique direction) is called a tournament.
A polynomial
| [画像: d_p(x)=sum_(q)d_(pq)x^q ] |
(1)
|
that enumerates the number of distinct simple directed graphs with p nodes (where g_(pq) is the number of directed graphs on p nodes with q edges) can be found by application of the Pólya enumeration theorem. This gives the counting polynomial for the number of directed graphs with p points as
| d_p(x)=Z(S_p^([2]),1+x), |
(2)
|
where S_p^([2]) is the reduced ordered pair group which acts on the 2-subsets of {1,2,...,p}, given by
| Z(S_p^([2]))=1/(p!)sum_((j))(p!)/(product_(k=1)^(p)k^(j_k)j_k!)a_k^((k-1)j_k+2k(j_k; 2))product_(q=1)^pproduct_(r=q+1)^pa_(LCM(q,r))^(j_qj_rGCD(q,r)) |
(3)
|
(Harary 1994, p. 186). Here, |_x_| is the floor function, (n; m) is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, the sum (j) is over all exponent vectors of the cycle index, and h_(j) is the coefficient of the term with exponent vector j_p in Z(S_p^([2])). The first few cycle indices Z(S_p^([2])) are
Setting a_n=1+x^n gives the generating functions for the number of directed graphs on n nodes with k edges,
See also
Acyclic Digraph, Directed Graph, Oriented Graph, Simple Graph, Strongly Connected Digraph, Tournament, Weakly Connected DigraphExplore with Wolfram|Alpha
More things to try:
References
Harary, F. "Digraphs." Ch. 16 in Graph Theory. Reading, MA: Addison-Wesley, pp. 10, 186, and 198-211, 1994.Sloane, N. J. A. Sequences A000273/M3032 and A052283 in "The On-Line Encyclopedia of Integer Sequences."Referenced on Wolfram|Alpha
Simple Directed GraphCite this as:
Weisstein, Eric W. "Simple Directed Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/SimpleDirectedGraph.html