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 FinVctKF(Q) where F(Q) is the free category on Q consisting of paths in Q and FinVctK 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.

Read more about this topic:  Directed Graph

Famous quotes containing the words classes of and/or classes:

    The want of education and moral training is the only real barrier that exists between the different classes of men. Nature, reason, and Christianity recognize no other. Pride may say Nay; but Pride was always a liar, and a great hater of the truth.
    Susanna Moodie (1803–1885)

    What’s the greatest enemy of Christianity to-day? Frozen meat. In the past only members of the upper classes were thoroughly sceptical, despairing, negative. Why? Among other reasons, because they were the only people who could afford to eat too much meat. Now there’s cheap Canterbury lamb and Argentine chilled beef. Even the poor can afford to poison themselves into complete scepticism and despair.
    Aldous Huxley (1894–1963)