Strongly Connected Digraph

 

A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point. The nodes in a strongly connected digraph therefore must all have indegree of at least 1. The numbers of nonisomorphic simple strongly connected digraphs on , 2, ... nodes are 1, 1, 5, 83, 5048, 1047008, ... (OEIS A035512).

A directed graph can be tested to see if it is strongly connected using ConnectedGraphQ[g].

---

REFERENCES

Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 218, 1973.

Liskovec, V. A. "A Contribution to the Enumeration of Strongly Connected Digraphs." Dokl. AN BSSR 17, 1077-1080, 1973.

Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.

Skiena, S. "Strong and Weak Connectivity." §5.1.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 94 and 172-174, 1990.

Sloane, N. J. A. Sequence A035512 in "The On-Line Encyclopedia of Integer Sequences."

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength