Simple Directed Graph
المؤلف:
Harary, F
المصدر:
"Digraphs." Ch. 16 in Graph Theory. Reading, MA: Addison-Wesley,
الجزء والصفحة:
...
13-3-2022
2374
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 
nodes for 
, 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 
nodes can be enumerated as ListGraphs[n, Directed] in the Wolfram Language package Combinatorica` .
A simple directed graph on 
nodes may have between 0 and 
edges. The number of simple directed graphs on 
nodes with 
edges can be given by NumberOfDirectedGraphs[n, m] in the Wolfram Language package Combinatorica` . The triangles of graphs counts on 
nodes (rows) with 
edges (columns) is given below (OEIS A052283).
 |
 , 1, 2, ... |
| 1 |
1 |
| 2 |
1, 1, 1 |
| 3 |
1, 1, 4, 4, 4, 1, 1 |
| 4 |
1, 1, 5, 13, 27, 38, 48, 38, 27, 13, 5, 1, 1 |
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
 |
(1)
|
that enumerates the number of distinct simple directed graphs with 
nodes (where 
is the number of directed graphs on 
nodes with 
edges) can be found by application of the Pólya enumeration theorem. This gives the counting polynomial for the number of directed graphs with 
points as
![d_p(x)=Z(S_p^([2]),1+x),](https://mathworld.wolfram.com/images/equations/SimpleDirectedGraph/NumberedEquation2.svg) |
(2)
|
where ![S_p^([2])](https://mathworld.wolfram.com/images/equations/SimpleDirectedGraph/Inline17.svg)
is the reduced ordered pair group which acts on the 2-subsets of ![<span style=]()
{1,2,...,p}" src="https://mathworld.wolfram.com/images/equations/SimpleDirectedGraph/Inline18.svg" style="height:22px; width:95px" />, 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))](https://mathworld.wolfram.com/images/equations/SimpleDirectedGraph/NumberedEquation3.svg) |
(3)
|
(Harary 1994, p. 186). Here, 
is the floor function, 
is a binomial coefficient, LCM is the least common multiple, GCD is the greatest common divisor, the sum 
is over all exponent vectors of the cycle index, and 
is the coefficient of the term with exponent vector 
in ![Z(S_p^([2]))](https://mathworld.wolfram.com/images/equations/SimpleDirectedGraph/Inline24.svg)
. The first few cycle indices ![Z(S_p^([2]))](https://mathworld.wolfram.com/images/equations/SimpleDirectedGraph/Inline25.svg)
are
Setting 
gives the generating functions for the number of directed graphs on 
nodes with 
edges,
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."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
