Discrete Mathematics (Classic Version) 5th Edition John A. Dossey SOLUTION

1 An Introduction to Combinatorial Problems and Techniques 1 1.1 The Time to Complete a Project . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 AMatching Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 A Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Algorithms and Their Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . 4 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Sets, Relations, and Functions 6 2.1 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Partial Ordering Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.5 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 Coding Theory 14 3.1 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3 The RSAMethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.4 Error-Detecting and Error-Correcting Codes . . . . . . . . . . . . . . . . . . 17 3.5 Matrix Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.6 Matrix Codes That Correct All Single-Digit Errors . . . . . . . . . . . . . . . 19 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 iii Table of Contents 4 Graphs 22 4.1 Graphs and Their Representations . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Shortest Paths and Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Coloring a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.5 Directed Graphs andMultigraphs . . . . . . . . . . . . . . . . . . . . . . . . 30 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5 Trees 36 5.1 Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.4 Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.5 Binary Trees and Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.6 Optimal Binary Trees and Binary Search Trees . . . . . . . . . . . . . . . . . 51 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6 Matching 63 6.1 Systems of Distinct Representatives . . . . . . . . . . . . . . . . . . . . . . . 63 6.2 Matchings in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.3 AMatching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.4 Applications of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.5 The HungarianMethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 7 Network Flows 68 7.1 Flows and Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 7.2 A Flow Augmentation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 70 7.3 TheMax-FlowMin-Cut Theorem . . . . . . . . . . . . . . . . . . . . . . . . 73 7.4 Flows andMatchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 iv Table of Contents 8 Counting Techniques 78 8.1 Pascal’s Triangle and the Binomial Theorem . . . . . . . . . . . . . . . . . . 78 8.2 Three Fundamental Principles . . . . . . . . . . . . . . . . . . . . . . . . . . 78 8.3 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . 79 8.4 Arrangements and Selections with Repetitions . . . . . . . . . . . . . . . . . 79 8.5 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 8.6 The Principle of Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . 81 8.7 Generating Permutations and r-Combinations . . . . . . . . . . . . . . . . . 82 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 9 Recurrence Relations and Generating Functions 84 9.1 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 9.2 TheMethod of Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 9.3 Linear Difference Equations with Constant Coefficients . . . . . . . . . . . . 91 9.4∗ Analyzing the Efficiency of Algorithms with Recurrence Relations . . . . . . 94 9.5 Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 99 9.6 The Algebra of Generating Functions . . . . . . . . . . . . . . . . . . . . . . 100 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 10 Combinatorial Circuits and Finite State Machines 105 10.1 Logical Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 10.2 Creating Combinatorial Circuits . . . . . . . . . . . . . . . . . . . . . . . . . 107 10.3 KarnaughMaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 10.4 Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115