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' | ||
