Some Review Notes

1. Section 1.2.
   1. Concepts to know: Ordinary and Strong Induction.
   2. Look at Examples 1-7.
   3. Look at Problems 1-15.
2. Chapter 1 Review.
   1. Look at the Review Problems and Summary on pages 39-40.
3. Section 5.1.
   1. Concepts to know: graph, vertex, edge, loop, incident, adjacent, parallel edges, simple graph, isomorphic graphs, complete graph, bipartite graph, complete bipartite graph, directed graph, weighted graph, degree, degree sequence, r-regular graph, p, q, , .
   2. Proofs to know: Theorem 5.1, Corollary 1 to Theorem 5.1, Corollary 2 to Theorem 5.1.
   3. Look at Puzzle 1, 2, 3(a), 4.
   4. Look at Problems 1-20.
4. Section 5.2.
   1. Concepts to know: walk, path, trail, subgraph, connected, component, connected graph, adjacency matrix, adjacency list.
   2. Look at Problems 1-8.
5. Section 5.3.
   1. Concepts to know: circuit, cycle, Eulerian trail, Eulerian circuit, Hamiltonian path, Hamiltonian cycle.
   2. Proofs to know: Theorem 5.2, Theorem 5.3, Theorem 5.4.
   3. Know how to find an Eulerian trail or circuit.
   4. Puzzles 1-4.
   5. Look at Problems 1-14.
6. Section 5.4.
   1. Concepts to know: planar graph, plane graph, Euler's formula, r.
   2. Proofs to know: Theorem 5.6, Theorem 5.7.
   3. Theorems to know: Theorem 5.8.
   4. Look at Puzzle 1-2.
   5. Look at Example 1.
   6. Look at Problems 1-11.
7. Section 5.5.
   1. Concepts to know: four-color problem, chromatic number, chromatic polynomial.
   2. Proofs to know: Theorem 5.11.
   3. Theorems to know: Theorem 5.9, Theorem 5.10.
   4. Look at Puzzle 2.
   5. Look at Example 2.
   6. Look at Problems 1-10.
8. Chapter 5 Review.
   1. Look at the Review Problems and Summary on pages 171-172.
9. Section 6.1
   1. Concepts to know: Breadth First Search, length, distance, Dijkstra's algorithm.
   2. Proofs to know: Theorem 6.3.
   3. Theorems to know: Theorem 6.1, Theorem 6.2.
   4. Look at Example 1.
   5. Look at Problems 1-10 in Section 6.1.
10. Section 6.2.
    1. Concepts to know: tree, forest, spanning tree, Prüfer code.
    2. Proofs to know: Theorem 6.6, Corollary 2 to Theorem 6.6, Theorem 6.8.
    3. Theorems to know: Theorem 6.4, Theorem 6.5, Corollary 1 to Theorem 6.6, Theorem 6.7, Theorem 6.9.
    4. Look at Problems 1-15.
11. Section 6.3.
    1. Concepts to know: directed tree, reachable, directed path, root, rooted tree, branch, leaf, descendant, binary tree, ternary tree, m-ary tree, regular m-ary tree, level, height, binary search, minimum-weight tree, Prim's algorithm, Kruskal's algorithm, optimal tree, Huffman's algorithm.
    2. Theorems to know: Theorem 6.10, Theorem 6.11.
    3. Look at Problems 1-10.
12. Chapter 6 Review.
    1. Look at the Review Problems and Summary on pages 198-199.
13. Section 10.2
    1. Concepts to know: activity network, earliest starting time algorithm, critical path analysis, latest completion time, float time.
    2. Theorems to know: Theorem 10.4.
    3. Look at Example 2.
    4. Look at Problems 4-5.

• About this document ...