====== Chapter 3 ====== ====== 3.1 Basic Definitions and Applications ====== Definitions, definitions and more definitions all about graphs. I know what a graph is, but just to review - edges E, and vertices (u,v) in V make up a graph. e connects from u to v. A graph can be: * Directed: go from vertx v to vertex u with edge e, but you cannot go from u to v on e * Undirected: how we typically think of graphs the edge connects the two vertices with no direction. * Tree: connected graph with no cycle * Connected is when there are edges to all vertices. We use the edges to fine a path * A certain type of path is a cycle that starts at one vertex and end up back at it by following edges Different types of graphs: * Transportation networks - algrotihm to find the best route might be an eventual problem, weight with milage, cost of fuel traffic etc. * Communication networks - problem: find a place in the room to put your wireless router * information networks: web etc. * Social networks - still have bad memories from trying to create facebook in 111 * dependency networks Theorems: * every n-node tree has exactly n-1 edges: we will prove this in hw ps 3 * let G be an undirected graph of n nodes: Any two fo the following statements * G is connected * G does not contain a cycle * G has n - 1 edges. * 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!