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  is an undirected connected graph, then one can always direct the circuit graph edges of  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].

---

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.

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

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