Differences

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

--- courses:cs211:winter2014:journals:haley:chapter3 [2014/01/22 02:23] – created archermcclellanh
+++ courses:cs211:winter2014:journals:haley:chapter3 [2014/02/12 07:33] (current) – archermcclellanh
@@ Line 18: / Line 18: @@
     * An undirected graph is a tree if it has no cycles.
         * Every n-node tree has exactly n-1 edges
+    * A bipartite graph is a 2-colorable graph - you can color the vertices using two colors such that no two adjacent vertices are colored the same.
     * I love graphs, so this section was an easy read. 10/10.
+===== 3.2: Graph Connectivity & Traversal =====
+    * Let's say we want to determine whether two vertices, //s// and //t//, are connected in a graph //G//. That is, whether there exists any path //p// in //G// such that both //s// and //t// are both on that path. How could we do this? We propose two algorithms to find all vertices in a connected component, starting at a vertex //v//.
+    * Breadth-first search: Add vertices one layer at a time in order of layer. Thus, add all vertices directly connected to //v//, then all vertices connected to something connected to //v//, and so on.
+        * There exists a path from //v// to some vertex //t// iff //t// is in some layer //j//.
+        * If two vertices are connected by an edge //e// in //G//, then those two vertices are at most one layer apart.
+        * The layer a vertex //w// is in is it's shortest path to vertex //v//.
+    * Depth-first search: Add vertices to the discovered vertices by going as far as you can from connected vertex to connected vertex. When you meet a dead-end, turn around and pick another connected vertex to search.
+    * Sets of connected components can be found by looking at a graph//G//, and placing all vertices discovered by either BFS or DFS for an arbitrary node, then exploring all nodes not yet discovered in the same way.
+        * We know that if two vertices are in //G//, their connected components are either the same or disjoint.
+    * Made sense in class, made sense in the book. 10/10.
+===== 3.3: Graph Traversal: Queues & Stacks =====
+    * We can represent a graph as either an adjacency list or an adjacency matrix.
+    * The list form requires O(n+m) for storage and vertex removal, O(n) for access, and O(m) for edge removal, but has constant-time addition of edges and vertices.
+    * The matrix requires O(n^2) for storage, vertex addition, and vertex removal, but has constant-time access, edge addition and edge removal.
+    * In spite of the fact that adjacency matrices seem worse, they're often preferred, especially to find all edges incident to a specific vertex.
+    * Both BFS and DFS take O(//n+m//) time complexity, where //n// represents the number of vertices and //m// the number of edges in //G//, assuming you use an adjacency //list//.
+    * Made sense in the book, kind of dry. 7/10.
+===== 3.4: Testing Bipartiteness =====
+    * Bipartite graphs contain no odd cycles.
+    * We can use breadth-first search to determine whether a graph is bipartite. We can then say:
+        * No edge of G joins two vertices of the same layer, thus G is bipartite and we can color the even layers one color and the odd another.
+        * xor
+        * An edge joins two vertices in the same layer, G contains an odd-length cycle, so G is not bipartite.
+    * This book section wasn't very interesting. 7/10.
+===== 3.5: Digraphs & Connectivity =====
+    * We represent digraphs as two adjacency lists, one of which is all in-edges and one of which is all out-edges.
+    * BFS & DFS are essentially the same now, with the following changes:
+        * BFS is given by finding all vertices with in-edges from our starting vertex to any other vertex.
+        * DFS is given recursively from vertex //v// by finding a vertex with an edge //v → u//.
+    * A digraph is strongly connected if for every pair of vertices (u,v) there exist paths u → v and v → u.
+        * If two vertices u,v are mutually reachable and v,w are mutually reachable, then u,w are mutually reachable.
+    * The strongly connected components of two vertices in a digraph D are either disjoint or identical.
+    * Well-written and interesting and delightful. 10/10.
+===== 3.6: Directed Acyclic Graphs & Topological Orderings =====
+    * A Directed Acyclic Graph is a directed graph without cycles. Go figure.
+    * They can be used to determine precedence relationships.
+    * A //topological ordering// of a directed graph G is an ordering of its nodes as v_1,v_2,...,v_n such that for each edge (v_i,v_j), i<j.
+    * Iff G is a DAG, it has a topological ordering.
+    * Every DAG necessarily has a vertex with no incoming edges.
+    * We compute topological orderings by finding a vertex in G without incoming edges, putting it first, and deleting it from G. Then recursively find a topo-ordering of G-v and appending that.
+    * This section was okay. 8/10.