Differences

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

--- courses:cs211:winter2012:journals:virginia:chapter3 [2012/01/30 02:19] – [Section 4: Testing Bipartiteness: An Application of BFS] lovellv
+++ courses:cs211:winter2012:journals:virginia:chapter3 [2012/02/16 03:06] (current) – lovellv
@@ Line 5: / Line 5: @@
 ===== Section 1: Basic Definitions and Applications =====
-A //graph// consists of a collection of nodes (V) and edges (E).  //Directed graphs// have "one-way" edges to indicate asymmetric relationships while //undirected graphs// have "two-way" edges to indicate symmetric relationships.  Some examples of graphs include transportation, communication, information and social networks.
+A **graph** consists of a collection of nodes (V) and edges (E).  **Directed graphs** have "one-way" edges to indicate asymmetric relationships while **undirected graphs** have "two-way" edges to indicate symmetric relationships.  Some examples of graphs include transportation, communication, information and social networks.
-A //path// in a graph is a sequence of nodes where each consecutive pair is connected by an edge.  A path is //simple// if all the vertices are distinct.  A path is a //cycle// if the first and last node are the same.  We say a graph is //connected// if there is a path from one node to every other.  The //distance// from one node to another is the length of the shortest path between them, measured in number of edges.
+A **path** in a graph is a sequence of nodes where each consecutive pair is connected by an edge.  A path is **simple** if all the vertices are distinct.  A path is a **cycle** if the first and last node are the same.  We say a graph is **connected** if there is a path from one node to every other.  The **distance** from one node to another is the length of the shortest path between them, measured in number of edges.
-A graph is a //tree// if it is connected and does not contain a cycle.  Trees represent hierarchies.
+A graph is a **tree** if it is connected and does not contain a cycle.  Trees represent hierarchies.
 Theorem: Any two of the following imply the third (i) G is connected, (ii) G does not contain a cycle, (iii) G has n-1 edges
@@ Line 46: / Line 46: @@
 ===== Section 5: Connectivity in Directed Graphs =====
+In this section, we begin to consider directed graphs.  We represent directed graphs with two adjacency lists - one of the nodes //to// which s has edges and one of the nodes //from// which it has edges.
+BFS and DFS are almost the same as in undirected graphs.  Both discover the set of nodes reachable from s, but in directed graphs, it is not guaranteed that we can get back to s from these nodes.  If there is a path from s to t and from t to s, then we say s and t are **mutually reachable**.  We say a directed graph is **strongly connected** if every pair of nodes are mutually reachable.
+The **strong component** containing s in a directed graph is the set of all v such that s and v are mutually reachable.  The strong component is similar to the connected component for an undirected graph.  Like the connected component, strong components are either identical or disjoint.
+Readability: 8
+===== Section 6: Directed Acyclic Graphs and Topological Orderings =====
+A special type of directed graph that contains no cycles is a **directed acyclic graph** (DAG).  DAGs can be used to represent precedence relations or dependencies.  One natural problem relating to DAGs is how to create a **topological ordering** (an ordering in which all edges point forward) from a DAG.  This is the equivalent to finding the order in which we may do tasks which depend on each other.  It is easy to see if a graph has a topological ordering, it is a DAG, but it is not obvious every DAG has a topological ordering.
+In fact, every DAG does have a topological ordering. We can find it by finding a node with no incoming edges, ordering it next in our topological ordering, deleting it from our graph, and repeating until we have added every node.  This algorithm has O(m+n) run time. (p 103)
+Readability: 8