Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2011:journals:camille:chapter3 [2011/02/01 05:49] – [Section 5: Connectivity in Directed Graphs] cobbc | courses:cs211:winter2011:journals:camille:chapter3 [2011/02/12 14:28] (current) – [Section 6: Directed Acyclic Graphs and Topological Ordering] cobbc |
|---|
| |
| * **Summary:** | * **Summary:** |
| | Undirected graphs without cycles are really simple (connected components = trees), but it's possible for directed graphs to be "rich" (i.e. complicated) without having any (directed) cycles. A directed graph without cycles is a directed acyclic graph (DAG). DAGs can be used to encode precedence relations or dependencies. Ex. tasks that depend on each other where nodes are the tasks and the directed edge from node i to j (i, j) means that i must be done before j. If there's a cycle, ordering of those tasks doesn't make any sense (everything in the cycle has to be done before everything else). A valid ordering of the "tasks"/nodes in a DAG is called a topological ordering. The tasks are "lined up" and all of the edges "point forward." Then the book proves (p. 101) that if G has a topological ordering, it's a DAG. Does the reverse work? And how do you find a DAG's topological ordering? Yes, the reverse does work. The first node in the ordering has no incoming edges (proof: any DAG has at least one node without incoming edges). Put that node first and delete it from the graph. Recursively compute a topological ordering from the leftover graph. Book goes into a more rigorous explanation. |
| |
| * **Insights and Questions:** | * **Insights and Questions:** |
| | The difference that they pointed out between directed and undirected graphs (that directed graphs with the same total number of edges as a "corresponding" undirected graph can be much more complicated) is really interesting. I guess it makes sense, but I hadn't really thought about comparing them in that way before. |
| |
| * **Readability:** | * **Readability:** |
| | As always, this section was very readable. I am glad I read it after we went over it in class, though, mostly because the word "topological" is kind of scary (haha ...). |
