- Digraph (mathematics)
A directed graph or digraph G is an
ordered pair G := (V, A) with
* V is a set, whose elements are called vertices or nodes,
* A is a set of ordered pairs of vertices, called directed edges, arcs, or arrows.It differs from an ordinary,
undirected graph in that the latter one is defined in terms ofunordered pair s of vertices.Sometimes a digraph is called a simple digraph to distinguish from the case of directed multigraph, in which arcs constitute a
multiset , rather than a set, of ordered pairs of vertices. Also, in a simple digraph loops, i.e., arcs that pairs of identical elements, are disallowed. On the other hand, some texts allow both loops and multiple arcs in a digraph.Basic terminology
An arc e = (x, y) is considered to be directed from x to y; y is called the head and x is called the tail of the arc; y is said to be a direct successor of x, and x is said to be a direct predecessor of y. If a path leads from x to y, then y is said to be a successor of x, and x is said to be a predecessor of y. The arc y, x) is called the arc x, y) inverted.
A directed graph "G" is called symmetric if, for every arc that belongs to "G", the corresponding inverted arc also belongs to "G". A symmetric loopless directed graph is equivalent to an undirected graph with the pairs of inverted arcs replaced with edges; thus the number of edges is equal to the number of arcs halved.
The oriented graph, is a graph (or
multigraph ) with an orientation or direction assigned to each of its edges. A distinction between a directed graph and an oriented "simple" graph is that if x and y are vertices, a directed graph allows both x, y) and y, x) as edges, while only one is permitted in an oriented graph.A weighted digraph is a digraph with weights assigned for its arcs, similarly to the
weighted graph .The
adjacency matrix of a digraph (with loops and multiple arcs) is the integer-valuedmatrix with rows and columns corresponding to the digraph nodes, where a nondiagonal entry a_{ij} is the number of arcs from node "i" to node "j", and the diagonal entry a_{ii} is the number of loops at node "i". The adjacency matrix for a digraph is unique up to the permutations of rows and columns.Another matrix representation for a digraph is its
incidence matrix .See
Glossary of graph theory#Direction for more definitions.Indegree and outdegree
For a node, the number of head endpoints adjacent to a node is called the indegree of the node and the number of tail endpoints is its outdegree.
The indegree is denoted deg^-(v) and the outdegree as deg^+(v). A vertex with deg^-(v)=0 is called a source, as it is the origin of each of its incident edges. Similarly, a vertex with deg^+(v)=0 is called a sink.
The degree sum formula states that, for a directed graph:sum_{v in V} deg^+(v) = sum_{v in V} deg^-(v) = |E|, .
Digraph connectivity
A digraph is called weakly connected if replacing all of its directed edges with undirected edges produces a
connected graph . It is strongly connected or strong if it contains a directed path from "u" to "v" and a directed path from "v" to "u" for every pair of vertices "u","v". The strong components are the maximal strongly connected subgraphs.Classes of digraphs
A
directed acyclic graph , occasionally called a dag or DAG, is a directed graph with nodirected cycle s.A
rooted tree naturally defines a DAG, if all edges of the underlying tree are directed away from the root.A tournament is an oriented graph obtained by choosing a direction for each edge in an undirected
complete graph .In the theory of
Lie group s, a quiver "Q" is a directed graph serving as the domain of, and thus characterizing the shape of, a representation "V" defined as afunctor , specifically an object of thefunctor category FinVct"K"F("Q") where "F"("Q") is the free category on "Q" consisting of paths in "Q" and FinVct"K" is the category of finite dimensionalvector space s over a field "K". Representations of a quiver label its vertices with vector spaces and its edges (and hence paths) compatibly with linear transformations between them, and transform via natural transformations.ee also
*
Transpose graph References
Wikimedia Foundation. 2010.