Directed Graph

A graph in which each graph edge is replaced by a directed graph edge, also called a digraph. A directed graph having no multiple edges or loops (corresponding to a binary adjacency matrix with 0s on the diagonal) is called a simple directed graph. 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.

If G is an undirected connected graph, then one can always direct the circuit graph edges of G and leave the separating edges undirected so that there is a directed path from any node to another. Such a graph is said to be transitive if the adjacency relation is transitive.

A graph may be tested in the Wolfram Language to see if it is a directed graph using DirectedGraphQ [g].

See also

Acyclic Digraph, Arborescence, Cayley Graph, Digraph Sink, Digraph Topology, Graph, Indegree, Mixed Graph, Multigraph, Network, Oriented Graph, Outdegree, Source, Strongly Connected Digraph, Tournament, Undirected Graph, Weakly Connected Digraph Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Chartrand, G. "Directed Graphs as Mathematical Models." §1.5 in Introductory Graph Theory. New York: Dover, pp. 16-19, 1985.Harary, F. and Palmer, E. M. "Digraphs." Ch. 5 in Graphical Enumeration. New York: Academic Press, pp. 120-134, 1973.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 122, 1986.

Referenced on Wolfram|Alpha

Directed Graph

Cite this as:

Weisstein, Eric W. "Directed Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/DirectedGraph.html

Subject classifications