Differences

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

--- courses:cs211:winter2014:journals:haley:chapter3 [2014/01/29 04:39] – archermcclellanh
+++ courses:cs211:winter2014:journals:haley:chapter3 [2014/02/12 07:33] (current) – archermcclellanh
@@ Line 59: / Line 59: @@
         * If two vertices u,v are mutually reachable and v,w are mutually reachable, then u,w are mutually reachable.
     * The strongly connected components of two vertices in a digraph D are either disjoint or identical.
-    * May I just say this section was dope? It was well-written and interesting and delightful. 10/10.
+    * Well-written and interesting and delightful. 10/10.
+===== 3.6: Directed Acyclic Graphs & Topological Orderings =====
+    * A Directed Acyclic Graph is a directed graph without cycles. Go figure.
+    * They can be used to determine precedence relationships.
+    * A //topological ordering// of a directed graph G is an ordering of its nodes as v_1,v_2,...,v_n such that for each edge (v_i,v_j), i<j.
+    * Iff G is a DAG, it has a topological ordering.
+    * Every DAG necessarily has a vertex with no incoming edges.
+    * We compute topological orderings by finding a vertex in G without incoming edges, putting it first, and deleting it from G. Then recursively find a topo-ordering of G-v and appending that.
+    * This section was okay. 8/10.