Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revision | |||
courses:cs211:winter2012:journals:carrie:ch3 [2012/01/30 04:24] – hopkinsc | courses:cs211:winter2012:journals:carrie:ch3 [2012/02/14 18:01] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] hopkinsc | ||
---|---|---|---|
Line 126: | Line 126: | ||
* seen in dependency networks | * seen in dependency networks | ||
* for example tasks in order, represent each task by a node. | * for example tasks in order, represent each task by a node. | ||
- | * topological ordering of G is an ordering of its nodes as v1, v2, .... so that for every edge (vi, | + | * topological ordering of G is an ordering of its nodes as v1, v2, .... so that for every edge (vi, |
+ | * This will be useful for problm set 4 | ||
Theorem 3.18 | Theorem 3.18 | ||
Line 132: | Line 133: | ||
* see proof in book. | * see proof in book. | ||
* is this theorem if and only if? need to find out. TWO sentences later we do find out. The converse is true. | * is this theorem if and only if? need to find out. TWO sentences later we do find out. The converse is true. | ||
- | * ttheorem | + | |
+ | theorem | ||
* see proof in book. | * see proof in book. | ||
* uses a lemma 3.19 | * uses a lemma 3.19 | ||
I'm lost a little towards the end of 3.6, but I'm thinking once we get to it in class it will all be clear! | I'm lost a little towards the end of 3.6, but I'm thinking once we get to it in class it will all be clear! | ||
+ | |||
+ | Update: Class did make this easier to understand. I actually remember using djikstra' | ||