Directed Graph - Classes of Digraphs

Classes of Digraphs

A directed graph G is called symmetric if, for every arc that belongs to G, the corresponding reversed arc also belongs to G. A symmetric, loopless directed graph is equivalent to an undirected graph with the edges replaced by pairs of inverse arcs; thus the number of edges is equal to the number of arcs halved.

An acyclic directed graph, acyclic digraph, or directed acyclic graph is a directed graph with no directed cycles. Special cases of acyclic directed graphs include multitrees (graphs in which no two directed paths from a single starting node meet back at the same ending node), oriented trees or polytrees (digraphs formed by orienting the edges of undirected acyclic graphs), and rooted trees (oriented trees in which all edges of the underlying undirected tree are directed away from the roots).

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_KF(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.