Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:chen:chapter_3 [2011/02/02 05:16] – [3.4 Testing Bipartiteness: An Application of Breadth-First Search] zhongc
+++ courses:cs211:winter2011:journals:chen:chapter_3 [2011/02/16 12:33] (current) – zhongc
@@ Line 69: / Line 69: @@
 Interesting/Readable: 6 6
+====== 3.6 Directed Acyclic Graphs and Topological Ordering ======
+definitions:
+  * If a directed graph has no cycles, we call it--naturally enough--a directed acycIic graph, or a DAG.
+  * analogous to any dependant systems in problem solving
+  * DAGs can be used to encode precedence relations or dependencies in a natural way.
+Problem:
+Goal: Find an algorithm for finding the TO.
+We can represent such an interdependent Set of tasks by introducing a node for each task, and a directed edge (i, j) whenever i must be done before j. The graph must be a DAG.
+Preparation:
+G has a topological ordering, then G is a DAG.
+proof:
+contradiction, spse we have a topological ordering, and also a cycle.
+then see what happens to the max indexed nodes...see p126.
+In every DAG G, there is a node v with no incoming edges.
+proof:
+same idea as above.
+Algo Idea:
+find a node v with no incoming edges
+Order v first
+Delete v from G
+Recursively compute a topological ordering of G-{v}
+and append this order after v.
+Readable/Interesting: 7/7