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 of unordered pairs 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-valued matrix 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 no directed cycles.

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 groups, a quiver "Q" is a directed graph serving as the domain of, and thus characterizing the shape of, a representation "V" defined as a functor, specifically an object of the functor 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 dimensional vector spaces 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