Differences

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

--- courses:cs211:winter2012:journals:carrie:ch3 [2012/01/30 02:04] – hopkinsc
+++ courses:cs211:winter2012:journals:carrie:ch3 [2012/02/14 18:01] (current) – [3.6 Directed Acyclic Graphs and Topological Ordering] hopkinsc
@@ Line 1: / Line 1: @@
- ====== Chapter 3 ======
+====== Chapter 3 ======
-====== 3.1  ======
+====== 3.1 Basic Definitions and Applications ======
 Definitions, definitions and more definitions all about graphs.
@@ Line 30: / Line 30: @@
    * There is a mistake in the above thm written on pg 78. (on instead of). also can't I just use this theorem to prove the one in our home work set?
+====== 3.2 Graph Connectivity and Graph Traversal ======
+Already learned what it means to be connected - now looking at what we can do with that
+Breadth First Search
+  * Looks at one node then all the nodes attached to it then all the nodes attached to each of those new nodes, goes by layers
+  * layer represents how far it is from root node, (also node in layer 5 is two away from node in layer three etc)
+  * can find shortest path with BFS
+  * produces a tree with a root at s
+  * can be made so has order (n+m) - slides from sprenkle explain this well see day 1/27 or 1/25
+Theorem 3.3
+  * for each j >= 1, Lj produuced by BFS consists of all nodes at exactly j distance from s. There is a path from s to t iff t appears in some layer.
+Theorem 3.4
+  * Let T be a breadth-first search tree, let x and y be nodes in T belonging to layers Li and Lj respectively and let (x,y) be an edge of G. Then i and j differ by at most 1.
+  * proof in book and in notes
+Theorem 3.5
+  * The set R produced at the end of the algorithm is precisely the connected component of G containing s.
+  * (goes with comment about how connected sets are either disjoint or the same.)
+  * proof in book.
+Deapth First Search
+  * better for mazes
+  * go as far as possible that traverse backwards
+  * longer tree than the wide tree of BFS
+  * O(m+n)
+Theorem 3.6
+  * More like a lemma...
+  * for a given recusive call DFS(u), all nodes that are marked Explored between the invocation and end of this recursive call are descendants of u in T.
+  * use this to prove 3.7
+Theorem 3.7
+  * Let T be a dfs tree, let x and y be nodes in T, and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.
+Theorem 3.8
+  * For any nodes s and t in a graph, their connected components are either identical or disjoint.
+  * mention this above under theorem 3.5
+  * proof in book
+====== 3.3 Implementing Graph Traversal Using Queues and Stacks ======
+Representing Graphs
+  * Adjacency lists, less space and better for sparse graphs O(n+m), possible order n to search for edges.
+  * adjacency matrix more space O(n^2), constant time access, but if we have to traverse anyways mine as well use adjacency lists?
+Queues and Stacks
+  * not much on these actually in the book in this part, but we have plenty of notes on the powerpoints.
+Implementing BFS
+  * Use an adjacency list structure,
+  * O(m+n)
+  * see our notes
+  * also proof in the book on p. 91, proving the bound time. This could be helpful for future similar problems
+  * The book references using a queue in class it didn't matter, but now i'm slightly confused...
+Implementing DFS
+  * Need to use a stack. (Last in first off)
+  * O(m+n)
+A little confused about the finding the set of all connected components section, but I think when we talked about htis in class it made sense so I am not going to worry too much.
+====== 3.4 Testing Bipartiteness: An application of Breadth-First Search ======
+Bipartite graph - can split nodes into two groups, nodes in group are not connected to each other, only connected to other group.
+USE BFS to implement. (each layer is a different color, our implementation in class was super helpful.
+Theorem 3.14
+  * I was not going to copy this theorem down, because it is so close to 3.15, but it is the beginning of pi and I cannot resist that.
+  * If a graph g is bipartite then it cannot contain an odd cycle.
+Theorem 3.15
+  * 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 be true:
+     * 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 notes in odd numbered layers can be colored blue.
+     * There is an edge of G joining two nodes of the same layer. It this cane G contains an odd layer cycle and so it cannon be bipartite.
+====== 3.5 connectivity in Directed Graphs ======
+Representatoin - variation of adjacency list from above. Node needs a list to what it points to and what points to it.
+Graph search algorithms
+  * BFS and DFS are very similar to what they are in an undirected graph
+Theorem 3.16:
+  * If u and v are mutually reachable and v and w are mutually reachable  then u and w anre mutually reachable.
+  * similar to the whole connected are the same or disjoint.
+  * proof in book
+Theorem 3.17
+  * For any two nodes s and t in a directed graph, their strong components are either identical or disjoint.
+  * proof in book
+====== 3.6 Directed Acyclic Graphs and Topological Ordering ======
+Directed graph with no cycles - DAG, directed acyclic graph!
+  * seen in dependency networks
+  * 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,vj) we have i < j therefore all edges point forward.
+  * This will be useful for problm set 4
+Theorem 3.18
+  * if G has topological ordering then G is a dag
+  * 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.
+  *
+theorem 3.20
+   * see proof in book.
+   * 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!
+Update: Class did make this easier to understand. I actually remember using djikstra's alogirthm in a math class before!