This is an old revision of the document!
Week 4
Chapter 3: Graphs
3.5: Connectivity in Directed Graphs
As noted in section 3.1, undirected graphs are just a special case of directed graphs in that an undirected has a set of edges such that for every edge (u, v) there also exists an edge (v, u), making every edge effectively bidirectional.
When a graph is described as being strongly connected, that means that for every pair of nodes in the graph there is a path of edges connecting one to the other and vice versa1).
3.6: Directed Acyclic Graphs and Topological Ordering
A directed acyclic graph is defined to be a directed graph in which no cycles occur. Such graphs typically have a large number of edges compared to the number of nodes. Every directed acyclic graph has a topological ordering in which edges from nodes earlier in the order always point to nodes that occur later in the ordering.
