Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |
| courses:cs211:winter2018:journals:shermanc:chapter3 [2018/02/07 04:25] – shermanc | courses:cs211:winter2018:journals:shermanc:chapter3 [2018/02/07 04:26] (current) – [3.6: Directed Acyclic Graphs and Topological Ordering] shermanc |
|---|
| ===== 3.6: Directed Acyclic Graphs and Topological Ordering ===== | ===== 3.6: Directed Acyclic Graphs and Topological Ordering ===== |
| |
| This section started off with a bang: an undirected graph with no cycles, it is just a tree. __**//Boom!//**__ (I think I'm having too much fun with DokuWiki syntax; now back to the important stuff.) Despite this, it is possible for a directed graph to have a no cycles but still have a complex structure. This structure is called a __DAG__, or //directed acyclic graph//. | This section started off with a bang: an undirected graph with no cycles, it is just a tree. __**//Boom!//**__ (I think I'm having too much fun with DokuWiki syntax; now back to the fun stuff.) Despite this, it is possible for a directed graph to have a no cycles but still have a complex structure. This structure is called a __DAG__, or //directed acyclic graph//. |
| |
| A simple way to think about DAGs is as if we have a set of classes the have prerequisites, as was the example in class. This has to be a DAG, because it just wouldn't make sense if a class that had a prerequisite of a lower-level class was itself a prerequisite of another lower-level class. To make sure this is true, there is what is called a __topological ordering__, where for every edge (v<sub>//i//</sub>, v<sub>//j//</sub>), //i// < //j//. Thus, every edge points in the forward or downhill direction and everything before a certain node must already be completed. This provides us the fact that if we have a graph G that has a topological ordering, then G is a DAG. | A simple way to think about DAGs is as if we have a set of classes the have prerequisites, as was the example in class. This has to be a DAG, because it just wouldn't make sense if a class that had a prerequisite of a lower-level class was itself a prerequisite of another lower-level class. To make sure this is true, there is what is called a __topological ordering__, where for every edge (v<sub>//i//</sub>, v<sub>//j//</sub>), //i// < //j//. Thus, every edge points in the forward or downhill direction and everything before a certain node must already be completed. This provides us the fact that if we have a graph G that has a topological ordering, then G is a DAG. |
