This is an old revision of the document!
Table of Contents
Chapter 3: Graphs
3.1 Basic Definitions and Applications
3.2 Graph Connectivity and Graph Traversal
3.3 Implementing Graph Traversal Using Queues and Stacks
3.4 Testing Bipartiteness: An Application of Breadth-First Search
3.5 Connectivity in Directed Graphs
3.6 Directed Acyclic Graphs and Topological Ordering
DAGs are directed graphs that do not contain cycles. This section proves that a graph is a DAG if and only if G has a topological ordering. It mentions that despite DAGs having no cycles, they can contain many nodes: (n choose 2) nodes.
