Directed Acyclic Graph

In mathematics and computer science, a directed acyclic graph (DAG i/ˈdæɡ/), is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of edges that eventually loops back to v again.

DAGs may be used to model several different kinds of structure in mathematics and computer science. A collection of tasks that must be ordered into a sequence, subject to constraints that certain tasks must be performed earlier than others, may be represented as a DAG with a vertex for each task and an edge for each constraint; algorithms for topological ordering may be used to generate a valid sequence. DAGs may also be used to model processes in which information flows in a consistent direction through a network of processors. The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability. Additionally, DAGs may be used as a space-efficient representation of a collection of sequences with overlapping subsequences.

The corresponding concept for undirected graphs is a forest, an undirected graph without cycles. Choosing an orientation for a forest produces a special kind of directed acyclic graph called a polytree. However there are many other kinds of directed acyclic graph that are not formed by orienting the edges of an undirected acyclic graph, and every undirected graph has an acyclic orientation, an assignment of a direction for its edges that makes it into a directed acyclic graph. For this reason it may be more accurate to call directed acyclic graphs acyclic directed graphs or acyclic digraphs.

Read more about Directed Acyclic Graph:  Partial Orders and Topological Ordering, Data Processing Networks, Causal and Temporal Structures, Paths With Shared Structure, Relation To Other Kinds of Graphs, Enumeration

Other articles related to "acyclic, graph, directed acyclic graph, graphs, directed acyclic graphs":

... many problems whose instances can be characterized by acyclic hypergraphs evaluating acyclic Boolean conjunctive queries checking the existence of a homomorphism between two acyclic relational structures checking ...
... Acyclic can refer to In chemistry, a compound which is not cyclic, e.g ... alkanes and acyclic aliphatic compounds In mathematics A graph without a cycle, especially A directed acyclic graph A chain complex in which all reduced homology groups are zero In economics, an economic ...
Longest Path Problem - Acyclic Graphs and Critical Paths
... A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation ... For most graphs, this transformation is not useful because it creates cycles of negative length in −G ... But if G is a directed acyclic graph, then no negative cycles can be created, and longest paths in G can be found in linear time by applying a linear time algorithm for shortest paths in −G, which is also a ...
Moral Graph
... A moral graph is a concept in graph theory, used to find the equivalent undirected form of a directed acyclic graph ... The moralized counterpart of a directed acyclic graph is formed by connecting nodes that have a common child, and then making all edges in the graph undirected ... Equivalently, a moral graph of a directed acyclic graph G is an undirected graph in which each node of the original G is now connected to its Markov blanket ...
Directed Acyclic Graph - Enumeration
... The graph enumeration problem of counting directed acyclic graphs was studied by Robinson (1973) ...

Famous quotes containing the words graph and/or directed:

    When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.
    Marshall McLuhan (1911–1980)

    A lover is never a completely self-reliant person viewing the world through his own eyes, but a hostage to a certain delusion. He becomes a perjurer, all his thoughts and emotions being directed with reference, not to an accurate and just appraisal of the real world but rather to the safety and exaltation of his loved one, and the madness with which he pursues her, transmogrifying his attention, blinds him like a victim.
    Alexander Theroux (b. 1940)