All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

Directed acyclic graph

In mathematics, a directed acyclic graph, also called a dag, DAG, or acyclic directed graph, is a directed graph with no dicycles; that is, for any vertex v, there is no directed path starting and ending 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.

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.

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:

• 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 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.

Applications

Directed acyclic graphs have many important applications in computer science, including:

03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
Science kits, science lessons, science toys, maths toys, hobby kits, science games and books - these are some of many products that can help give your kid an edge in their science fair projects, and develop a tremendous interest in the study of science. When shopping for a science kit or other supplies, make sure that you carefully review the features and quality of the products. Compare prices by going to several online stores. Read product reviews online or refer to magazines.

Start by looking for your science kit review or science toy review. Compare prices but remember, Price \$ is not everything. Quality does matter.
 Science Fair Coach What do science fair judges look out for? ScienceHound Science Fair Projects for students of all ages
 All Science Fair Projects.com Site All Science Fair Projects Homepage Search | Browse | Links | From-our-Editor | Books | Help | Contact | Privacy | Disclaimer | Copyright Notice