In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph, or set of nodes connected by edges, where the edges have a direction associated with them. In formal terms, a digraph is a pair (sometimes ) of:
- a set V, whose elements are called vertices or nodes,
- a set A of ordered pairs of vertices, called arcs, directed edges, or arrows (and sometimes simply edges with the corresponding set named E instead of A).
It differs from an ordinary or undirected graph, in that the latter is defined in terms of unordered pairs of vertices, which are usually called edges.
Sometimes a digraph is called a simple digraph to distinguish it from a directed multigraph, in which the arcs constitute a multiset, rather than a set, of ordered pairs of vertices. Also, in a simple digraph loops are disallowed. (A loop is an arc that pairs a vertex to itself.) On the other hand, some texts allow loops, multiple arcs, or both in a digraph.
Read more about Directed Graph: Basic Terminology, Indegree and Outdegree, Digraph Connectivity, Classes of Digraphs, See Also
Famous quotes containing the words directed and/or graph:
“What is clear is that Christianity directed increased attention to childhood. For the first time in history it seemed important to decide what the moral status of children was. In the midst of this sometimes excessive concern, a new sympathy for children was promoted. Sometimes this meant criticizing adults. . . . So far as parents were put on the defensive in this way, the beginning of the Christian era marks a revolution in the child’s status.”
—C. John Sommerville (20th century)
“In this Journal, my pen is a delicate needle point, tracing out a graph of temperament so as to show its daily fluctuations: grave and gay, up and down, lamentation and revelry, self-love and self-disgust. You get here all my thoughts and opinions, always irresponsible and often contradictory or mutually exclusive, all my moods and vapours, all the varying reactions to environment of this jelly which is I.”
—W.N.P. Barbellion (1889–1919)