FACTOID # 6: Michigan is ranked 22nd in land area, but since 41.27% of the state is composed of water, it jumps to 11th place in total area.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Directed acyclic graph
A simple directed acyclic graph
A simple directed acyclic graph

In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path that starts and ends on v. DAGs appear in models where it doesn't make sense for a vertex to have a path to itself; for example, if an edge uv indicates that v is a part of u, such a path would indicate that u is a part of itself, which is impossible. Image File history File links A directed acyclic graph, created by Derrick Coetzee in Illustrator and Photoshop. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... This article just presents the basic definitions. ... In the mathematical field of graph theory a cycle graph or circle graph is a graph that consists of a cycle. ... One major problem that has plagued graph theory since its inception is the lack of consistency in terminology. ...


Every directed acyclic graph corresponds to a partial order on its vertices, in which uv is in the partial order exactly when there exists a directed path from u to v in the graph. However, many different directed acyclic graphs may represent the same partial order in this way. Among these graphs, the one with the fewest edges is the transitive reduction and the one with the most edges is the transitive closure. In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... In mathematics, the transitive reduction of a binary relation R on a set X is the smallest relation on X such that that the transitive closure of is the same as the transitive closure of R. If the transitive closure of R is antisymmetric and finite, then is unique. ... In mathematics, the transitive closure of a binary relation R on a set X is the smallest transitive relation on X that contains R. For any relation R the transitive closure of R always exists. ...

Contents

Terminology

A source is a vertex with no incoming edges, while a sink is a vertex with no outgoing edges. A finite DAG has at least one source and at least one sink.


The length of a finite DAG is the length (number of edges) of a longest directed path.


Properties

Every directed acyclic graph has a topological sort, an ordering of the vertices such that each vertex comes before all vertices it has edges to. In general, this ordering is not unique. Any two graphs representing the same partial order have the same set of topological sort orders. In graph theory, a topological sort of a directed acyclic graph (DAG) is a linear ordering of the nodes of the graph such that x comes before y if theres a directed path from x to y in the DAG. An equivalent definition is that each node comes before...


DAGs can be considered to be a generalization of trees in which certain subtrees can be shared by different parts of the tree. In a tree with many identical subtrees, this can lead to a drastic decrease in space requirements to store the structure. Conversely, a DAG can be expanded to a forest of rooted trees using this simple algorithm: A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...

  • While there is a vertex v with in-degree n > 1,
    • Make n copies of v, each with the same outgoing edges but no incoming edges.
    • Attach one of the incoming edges of v to each vertex.
    • Delete v.

If we explore the graph without modifying it or comparing nodes for equality, this forest will appear identical to the original DAG.


Some algorithms become simpler when used on DAGs instead of general graphs. For example, search algorithms like depth-first search without iterative deepening normally must mark vertices they have already visited and not visit them again. If they fail to do this, they may never terminate because they follow a cycle of edges forever. Such cycles do not exist in DAGs. Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. ... Iterative deepening depth-first search is a state space search strategy, that visits each node in the search tree in the same order as breadth-first search but does so by gradually increasing the maximum depth limit of the search iteratively. ...


The number of Non-Isomorphic DAGs is obtained by Weisstein's conjecture[1]: the number of DAGs on n vertices is equal to the number of nxn matrices with entries from {0,1} and only positive real eigenvalues, proved by McKay et al. [2].


Applications

Directed acyclic graphs have many important applications in computer science, including: Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

In theoretical physics a directed acyclic graph can be used to represent spacetime as a causal set. A parse tree is a tree that represents the syntactic structure of a string according to some formal grammar. ... A bayesian network (or a belief network) is a directed acyclic graph which represents independencies embodied in a given joint probability distribution over a set of variables. ... In computer science, garbage collection (also known as GC) is a form of automatic memory management. ... In computer science, reference counting is a technique of storing the number of references, pointers, or handles to a resource such as an object or block of memory. ... Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications (updates). ... A binary tree, a simple type of branching linked data structure. ... In computer science, instruction scheduling is a compiler optimization used to improve instruction-level parallelism, which improves performance on machines with instruction pipelines. ... make is a computer program that automates the compilation of programs whose files are dependent on each other. ... In object-oriented programming, a class is a programming language construct that is used to group related instance variables and methods. ... In object-oriented programming, inheritance is a way to form new classes (instances of which are called objects) using classes that have already been defined. ... Object-oriented programming (OOP) is a programming paradigm that uses objects to design applications and computer programs. ... In databases and transaction processing, serializability is the property of a schedule being serializable. ... A Transaction Processing System (TPS) is a type of information system. ... In computing, a directory, catalog, or folder, is an entity in a file system which can contain a group of files and/or other directories. ... // Introduction A scene-graph is a general data structure commonly used by vector-based graphics editing applications and modern computer games. ... In 3D computer graphics, the viewing frustum or view frustum is the region of space in the modeled world that may appear on the screen; it is the field of view of the notional camera. ... In 3D computer graphics, hidden surface determination is the process used to determine which surfaces and parts of surfaces are not visible from a certain viewpoint. ... hi i m here wat r u doin ... The Rete algorithm is an efficient pattern matching algorithm for implementing rule-based (expert) systems. ... Theoretical physics employs mathematical models and abstractions of physics, as opposed to experimental processes, in an attempt to understand nature. ... The causal sets programme is an approach to quantum gravity. ...


References

  1. ^ Eric W. Weisstein, Weisstein's Conjecture at MathWorld.
  2. ^ McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; and Wilf, H. "Acyclic Digraphs and Eigenvalues of (0,1)-Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.pdf or http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html

Dr. Eric W. Weisstein Encyclopedist Dr. Eric W. Weisstein (born March 18, 1969, in Bloomington, Indiana) is a noted encyclopedist in several technical areas of science and mathematics. ... MathWorld is an online mathematics reference work, sponsored by Wolfram Research Inc. ...

External links


  Results from FactBites:
 
Directed acyclic graph - Wikipedia, the free encyclopedia (642 words)
DAGs appear in models where it doesn't make sense for a vertex to have a path to itself; for example, if an edge u→v indicates that v is a part of u, such a path would indicate that u is a part of itself, which is impossible.
Among these graphs, the one with the fewest edges is the transitive reduction and the one with the most edges is the transitive closure.
DAGs can be considered to be a generalization of trees in which certain subtrees can be shared by different parts of the tree.
Graphs (1162 words)
A graph G= consists of a set of vertices (also known as nodes) V and a set of edges (also known as arcs) E. An edge connects two vertices u and v; v is said to be adjacent to u.
Graphs are useful for representing networks and maps of roads, railways, airline routes, pipe systems, telephone lines, electrical connections, prerequisites amongst courses, dependencies amongst tasks in a manufacturing system and a host of other data.
Note that a rooted tree is a special kind of directed graph and that an unrooted tree is a special kind of undirected graph.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m