Difference between revisions of "Directed graph"
Karl Jones (Talk | contribs) (Created page with "In mathematics, and more specifically in graph theory, a '''directed graph''' (or '''digraph''') is a graph (discrete mathematics), or set of vertices connected by...") |
(No difference)
|
Revision as of 08:58, 10 March 2016
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph (discrete mathematics), or set of vertices connected by edges, where the edges have a direction associated with them.
Definition
In formal terms, a directed graph is an ordered pair G = (V, A) (sometimes G = (V, E)) where:
- V is a set whose elements are called vertices, nodes, or points;
- A is a set of ordered pairs of vertices, called arrows, directed edges (sometimes simply edges with the corresponding set named E instead of A), directed arcs, or directed lines.
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, arcs, or lines.
A directed graph is called a simple digraph if it has no multiple arrows (two or more edges that connect the same two vertices in the same direction) and no loops (edges that connect vertices to themselves).
A directed graph is called a directed multigraph or multidigraph if it may have multiple arrows (and sometimes loops).
In the latter case the arrow set forms a multiset, rather than a set, of ordered pairs of vertices.
See also
External links
- Directed graph @ Wikipedia
