![]() Choosing an orientation for a forest produces a special kind of directed acyclic graph called a polytree. The corresponding concept for undirected graphs is a forest, an undirected graph without cycles. The problems of finding shortest paths and longest paths can be solved on DAGs in linear time, in contrast to arbitrary graphs for which shortest path algorithms are slower and longest path problems are NP-hard. Transforming a directed graph with cycles into a DAG by deleting as few vertices or edges as possible (the feedback vertex set and feedback edge set problem, respectively) is an NP-hard problem, but any directed graph can be made into a DAG (its condensation) by contracting each strongly connected component into a single supervertex. Important polynomial time computational problems on DAGs include topological sorting (computing a topological ordering), construction of the transitive closure and transitive reduction (the largest and smallest DAGs with the same reachability relation, respectively) of sets, and the closure problem, in which the goal is to find a minimum-weight subset of vertices with no edges connecting them to the rest of the graph. The reachability relation in a DAG forms a partial order, and any finite partial order may be represented by a DAG using reachability. DAGs can also be used as a compact representation of sequence data, such as the directed acyclic word graph representation of a collection of strings, or the binary decision diagram representation of sequences of binary choices. DAGs can also represent collections of events and their influence on each other, either in a probabilistic structure such as a Bayesian network or as a record of historical data such as family trees or the version histories of distributed revision control systems. Combinational logic blocks in electronic circuit design, and the operations in dataflow programming languages, involve acyclic networks of processing elements. The program evaluation and review technique (PERT) uses DAGs to model the milestones and activities of large human projects, and schedule these projects to use as little total time as possible. Similarly, topological orderings of DAGs can be used to order the compilation operations in a makefile. For example, a spreadsheet can be modeled as a DAG, with a vertex for each cell and an edge whenever the formula in one cell uses the value from another a topological ordering of this DAG can be used to update all cell values when the spreadsheet is changed. Equivalently, a DAG is a directed graph that has a topological ordering, a sequence of the vertices such that every edge is directed from earlier to later in the sequence.ĭAGs can model many different kinds of information. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again. In mathematics, particularly graph theory, and computer science, a directed acyclic graph ( DAG or dag / ˈ d æ ɡ/ ( listen)) is a directed graph with no directed cycles. A directed graph is acyclic if and only if it has a topological ordering. A topological ordering of a directed acyclic graph: every edge goes from earlier in the ordering (upper left) to later in the ordering (lower right).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |