- Digraph (mathematics)
A directed graph or digraph is an
ordered pair with
* is a set, whose elements are called vertices or nodes,
* 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 is considered to be directed from to ; is called the head and is called the tail of the arc; is said to be a direct successor of , and is said to be a direct predecessor of . If a path leads from to , then is said to be a successor of , and is said to be a predecessor of . The arc is called the arc 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 and are vertices, a directed graph allows both and 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 is the number of arcs from node "i" to node "j", and the diagonal entry 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 and the outdegree as A vertex with is called a source, as it is the origin of each of its incident edges. Similarly, a vertex with is called a sink.
The degree sum formula states that, for a directed graph:
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.