Differences

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

--- courses:cs211:winter2012:journals:virginia:chapter3 [2012/02/16 02:52] – [Section 5: Connectivity in Directed Graphs] 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 52: / Line 52: @@
 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