(data structure)
Definition: A graph whose edges are ordered pairs of vertices. That is, each edge can be followed from one vertex to another vertex.
Formal Definition: A graph G is a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E ⊆ {(u,v) | u, v ∈ V}. If the graph does not allow self-loops, adjacency is irreflexive, that is E ⊆ {(u,v) | u, v ∈ V ∧ u ≠ v}.
Also known as digraph, oriented graph.
Generalization (I am a kind of ...)
graph.
Specialization (... is a kind of me.)
directed acyclic graph, weighted, directed graph, strongly connected graph, arborescence.
Aggregate child (... is a part of or used in me.)
source, sink, in-degree, out-degree.
See also undirected graph, hypergraph, multigraph, Schorr-Waite graph marking algorithm.
Note: In contrast, undirected graphs merely connect the vertices, without any consideration for direction. For example, a map of streets in a neighborhood is an undirected graph, but a map that shows the postman's route through that neighborhood is a directed graph. A directed graph may be thought of as a neighborhood of one-way streets: the map must show the allowed direction of travel on each street. A regular two-way street may be thought of as two one-way streets.
Author: PEB
Historical Note
John N. Warfield <Jnwarfield@aol.com> provides the following history of digraphs.
In the Harvard-Oxford books on Aristotle, one of the translators suggests that Aristotle actually used something akin to digraphs in his teachings, but this was pure speculation.
Augustus De Morgan invented the Theory of Relations and published the key work in 1847---the same year in which Boole published his key book in which he credited De Morgan for essentially teaching Boole about logic.
Since the Theory of Relations offers essentially the algebraic form of the digraph, it is unlikely that there was any formal use before 1847.
Charles Sanders Peirce made clear the use of structural patterns in doing basic work, but his own graphics were not very useful in extended form, though some modern enthusiasts have extolled his "existential graphs".
The earliest actual drawing of a digraph as connected to De Morgan that I have been able to find occurs in the 1919 book by Bertrand Russell titled "Introduction to Mathematical Philosophy".
If you find an earlier digraph, please contact me, John N. Warfield.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 20 November 2008.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "directed graph", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 November 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/directedGraph.html