Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:deirdre:chapter3 [2014/01/29 04:58] – [Section 3.1 - Basic Definitions and Applications] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter3 [2014/02/12 04:40] (current) – [Section 3.6 - Directed Acyclic Graphs and Topological Ordering] tobind
@@ Line 103: / Line 103: @@
                     Add v to the list L[i+1]
               Endif
         Endfor
         Increment the layer counter i by one
@@ Line 130: / Line 131: @@
 I give this section a 9 on the topic, but only a 7 on the interesting/helpful. I feel like I got a good grasp on this from class/my notes.
+====== Section 3.4 - Testing Bipartiteness: An Application of BFS ======
+**The Problem**
+How do we figure out if a graph is bipartite?
+- If a graph G is bipartite, it cannot contain an odd cycle.
+**Designing the Algorithm**
+In fact, there is a very simple procedure to test for bipartiteness, and its analysis can be used to show that odd cycles are the only obstacle. First, we assume the graph is //G// is connected, since otherwise we can first compute its connected components and analyze each of them separately. Next, we pick any node //s ∈ V// and color it red. It follows that all the neighbors of //s// must be colored blue. And then their neighbors must be red. Etc. At the end, we either have a valid coloring or we don't. If we don't, it's not bipartite. We can see that we can implement BFS to do this!
+**Analyzing the Algorithm**
+Let //G// be a connected graph and let L1, L2 be the layers produced by BFS starting at node s. Then exactly one of the following two things must hold.
+  * There is no edge of //G// joining two nodes of the same layer. In this case //G// is a bipartite graph in which the nodes in even-numbered layers can be colored red and the nodes in odd-numbered layers can be colored blue..
+  * There is an edge of G joining two nodes of the same layer. In this case, G contains an odd-length cycle and so it cannot be bipartite.
+See book for proof (p96). This part was a 8 for interesting, but had minimal knowledge gain I feel like? It might have just been that I thought it was relatively simple when we talked briefly about it during class.
+====== Section 3.5 - Connectivity in Directed Graphs ======
+Remember: in directed graphs, the edge //(u,v)// has a direction: it goes from //u// to //v//. (relationship is asymmetric)
+To represent a dg, we use aversion of the adjacency list representation. Now, instead of each node having a single list of neighbors, each node has two lists associated with it: one list consists of nodes to which it has edges and a second list consists of nodes from which it has edges.
+**The Graph Search Algorithm**
+BFS starts at node //s//, defines first layer, second layer, etc. The nodes in layer //j// are precisely those for which the shortest path from //s// has exactly //j// edges. running time = //O(m+n)//. DFS also runs in linear time.
+**Strong Connectivity**
+(strongly connected = u -> v ^ v -> u)
+Two nodes //u// and //v// in a dg are mutually reachable if there is a path from //u// to //v// and also a path from //v// to //u//. If //u// and //v// are mutually reachable and //v// and //w// are m.r., then //u// and //w// are m.r.
+There is a simple linear time algorithm to test if a directed graph is strongly connected. We pick any node //s// and run BFS starting from //s//. we then also run BFS starting from //s// in G^rev. If one of the two searches fail to reach every node, G is not strongly connected.
+For any two nodes //s// and //t// in a dg, their strong components are either identical or disjoint.
+====== Section 3.6 - Directed Acyclic Graphs and Topological Ordering ======
+If an undirected graph has no cycles, then each of its connected components is a tree. But it's possible for a dg to have no cycles and still "have a very rich structure". If a dg has no cycles, we call it a DAG (directed acyclic graph).
+**The Problem**
+.18 If G has a topological ordering, then //G// is a DAG.
+Does every DAG have a topological ordering? How do we find one efficiently?
+**D and A the Algorithm**
+(Spoiler alert: The converse of 3.18 is true.) Which node do we put at the beginning of the topological ordering? Such a node would need to have no incoming edges. (In every DAG G, there is a node v with no incoming edges)
+Algorithm:
+ To compute a topological ordering of G:
+ Find a node v with no incoming edges and order it first
+ Delete v from G
+ Recursively compute a topological ordering of G-{v} and append this order after v
+We can achieve a running time of //O(m+n)// by iteratively deleting nodes with no incoming edges. We can do this efficiently by declaring nodes "active" and maintaining:
+ - for each node //w//, the number of incoming edges that //w// has from active nodes;
+ - the set S of all active nodes in //G// that have no incoming edges from other active nodes.
+At the start, all nodes are active. This allows us to keep track of nodes that are eligible for deletion.
+This section was an 8 to read. I must have been tired in class this day or else we didn't cover it very much because the acyclic stuff makes way more sense now.