Discrete Mathematics With Graph Theory 3ed

I5CRETE АТПЕМАТ1С5 Preface New in the Third Edition Thank You To the Student From a Student EXERCISES Suggested Lecture Schedule Yes, There are Proofs! Logic Contents Yes, There Are Proofs! 1 Logic 2 Sets and Relations 3 Functions 4 The Integers 1 19 38 72 98 7 Permutations and Combinations 205 о Yes, There Are Proofs! 0.1 Compound Statements “And” and “Or” Implication The Converse of an Implication Double Implication Negation The Contrapositive Quantifiers What May I Assume? True/False Questions Exercises 0.2 Proofs in Mathematics Direct Proof Proof by Cases Prove the Contrapositive True/False Questions Exercises Review Exercises for Chapter О Logic 1.1 Truth Tables True/False Questions Exercises 1.2 The Algebra of Propositions Some Basic Logical Equivalences EXAMPLE 10 EXAMPLE 11 Application: Three-Way Switches True/False Questions Exercises 1.3 Logical Arguments Rules of Inference a True/False Questions Exercises 2 Sets and Relations 2.1 Sets True/False Questions Exercises 2.2 Operations on Sets Union and Intersection True/False Questions Exercises 2.3 Binary Relations EXAMPLE 16 EXAMPLE 18 Higher-Order Relations True/False Questions Exercises 2.4 Equivalence Relations EXAMPLE 32 True/FaIse Questions Exercises 2.5 Partial Orders True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 2 3.1 3 Functions Baste Terminology The Identity Function The Ins and Outs of Functions True/False Questions Exercises 3.2 Inverses and Composition EXAMPLE 19 Composition of Functions True/False Questions Exercises 3.3 One-to-One Correspondence and the Cardinality of a Set Key Terms & Ideas Review Exercises for Chapter 3 The Integers 4.1 The Division Algorithm •e Representing Natural Numbers in Various Bases True/False Questions Exercises 4.2 Divisibility and the Euclidean Algorithm Solution. We have The Lattice of Divisors of a Natural Number True/False Questions Exercises 4.3 Prime Numbers Mersenne Primes Fermat Primes How Many Primes Are There? More Open Problems True/False Questions Exercises True/False Questions Exercises 4.5 Applications of Congruence International Standard Book Numbers Universal Product Codes The Chinese Remainder Theorem Determining Numbers by Their Remainders Cryptography True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 4 5 Induction and Recursion 5.1 Mathematical Induction Mathematical Induction and Well Ordering True/False Questions Exercises 5.2 Recursively Defined Sequences Some Special Sequences an = a + (n — l)d. $ = ^[2a + (n-lW], = |(2 ■ 3"-1 + 3"-1 - 1) = 1(3 ■ 3й-’ - 1) = |(3" - 1) Application: Pseudorandom Numbers True/False Questions Exercises 5.3 Solving Recurrence Relations; The Characteristic Polynomial True/False Questions Exercises 5.4 Solving Recurrence Relations; Generating Functions Key Terms & Ideas Review Exercises for Chapter 5 6 Principles of Counting 6.1 The Principle of Inclusion-Exclusion True/False Questions Exercises 6.2 The Addition and Multiplication Rules True/False Questions Exercises 6.3 Pause 9 True/False Questions Exercises Review Exercises for Chapter 6 Permutations and Combinations 7.1 Permutations Л? = Л(Д-1)(Л-2)..(3)(2)(1) True/False Questions Exercises 7.2 Combinations Pin. r) ”71 True/False Questions Exercises 7.3 Elementary Probability Solution. Solution. 11. True/False Questions Exercises 7.4 Probability Theory 14. 17. True/False Questions Exercises 7*5 Repetitions P(n,r) True/Fafse Questions Exercises 7.6 Derangements True/False Questions Exercises 7.7 The Binomial Theorem Solution. Solution. True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 7 8 Algorithms 8.1 What Is an Algorithm? = a0 + (aL + (a2 + j- (an_, + a„x)x) ■ • • )*• True/False Questions Exercises 8.2 Complexity EXAMPLE 8 EXAMPLE 9 True/False Questions Exercises 8.3 Searching and Sorting EXAMPLE 23 For the input list True/False Questions Exercises 8.4 Enumeration of Permutations and Combinations True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 8 Graphs 9.1 A Gentle Introduction True/False Questions Exercises 9.2 Definitions and Basic Properties True/False Questions Exercises 9.3 Isomorphism True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 9 10 Paths and Circuits 10.1 Eulerian Circuits True/False Questions Exercises 10.2 Hamiltonian Cycles Application: Gray Codes6 True/False Questions Exercises 10.3 The Adjacency Matrix EXAMPLE 8 True/False Questions Exercises 10.4 Shortest Path Algorithms The Traveling Salesman's Problem True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 1O 11 Applications of Paths and Circuits 11.1 The Chinese Postman Problem Figure 11.1 True/False Questions Exercises 11.2 Digraphs True/False Questions Exercises 11.3 RNA Chains I True/False Questions Exercises *11.4 Tournaments True/False Questions Exercises 11.5 Scheduling Problems Figure 11.26 Figure 11.27 Exercises Key Terms & Ideas Review Exercises for Chapter 11 12 Trees 12.1 Trees and their Properties Figure 12 .8 Figure 12.12 True/False Questions Exercises 12.2 Spanning Trees True/False Questions Exercises 12-3 Minimum Spanning Tree Algorithms A Bound for a Minimum Hamiltonian Cycle True/False Questions Exercises 12. 4 Acyclic Digraphs and Bellman's Algorithm True/False Questions Figure 12,22 Exercises 12.5 Depth-First Search True/False Questions Exercises Figure 12.26 12.6 The One-Way Street Problem Exercises Key Terms & Ideas Review Exercises for Chapter 12 13 Planar Graphs and Colorings 13.1 Planar Graphs All V - E + F = 2, True/False Questions Exercises 13.2 Coloring Graphs True/False Questions Exercises Child Doesn't get along with 13.3 Circuit Testing and Facilities Design Circuit Testing Figure 13.19 Facilities Design Figure 13. 22 8. №№№).№.№). True/False Questions Exercises Figure 13.24 Key Terms & Ideas Review Exercises for Chapter 13 The Max Flow-Min Cut Theorem 14.1 Flows and Cuts The Construction of Flows True/False Questions Exercises 14.2 Constructing Maximal Flows val(^) = £2 ~ = £2 “ °) = X2 Cuv ~ caP^’ T>>- Rational Weights True/False Questions Exercises 14.3 Applications Multiple Sources and/or Sinks Supply and Demand Problems Undirected Edges Edge-Disjoint Paths Job Assignments True/False Questions Exercises 14.4 Matchings True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 14 Bettor Teams Matrices and Determinants Determinants Evaluating a Determinant with Elementary Row Operations EXAMPLE 5 Solutions to True/False Questions and Selected Exercises Exercises 0,1 Section 0.2 True/False Exercises 0.2 Section 1.1 True/False Exercises 1.1 Exercises 1.2 Exercises 1.3 Section 2.1 True/False Exercises 2.1 Section 2.2 True/False Exercises 2.2 Exercises 2.3 Section 2.4 True/False Exercises 2.4 Section 2.5 True/False Exercises 2.5 Section 3.1 True/False Exercises 3.1 Section 3.2 True/False Exercises 3.2 Section 3.3 True/False Exercises 3.3 Section 4.1 True/False Exercises 4.1 Section 4.2 True/False Exercises 4.2 Section 4.3 True/False Exercises 4.3 Section 4.4 True/False Exercises 4.4 Section 4.5 True/False Exercises 4.5 Section 5.1 True/False Exercises 5.1 Section 5.2 True/False Exercises 5.2 Section 5.3 True/False Exercises 5.3 Section 5.4 True/False Exercises 5.4 Section 6.1 True/False Exercises 6.1 Section 6.2 True/False Exercises 6.2 Section 6.3 True/False Exercises 6.3 Section 7.1 True/False Exercises 7.1 Section 7.2 True/False Exercises 7.2 Section 7.3 True/False Exercises 7.3 Section 7.4 True/False Exercises 7.4 Section 7.5 True/False Exercises 7.5 Section 7.6 True/False Exercises 7.6 Section 7.7 True/False Exercises 7.7 Section 8.1 True/False Exercises 8.1 Section 8.2 True/False Exercises 8.2 Section 8.3 True/False Exercises 8.3 Section 8.4 True/False Section 9.1 True/False Exercises 9.1 Section 9.2 True/False Exercises 9.2 Section 9.3 True/False Exercises 9.3 Section 10.1 True/False Section 10.2 True/False Exercises 10.2 Section 10.3 True/False Exercises 10.3 Section 10.4 True/False Exercises 10.4 Section 11.1 True/False Section 11.2 True/False Exercises 11.2 Section 11.3 True/False Exercises 11.3 Section 11.4 True/False Exercises 11.4 Section 11.5 True/False Exercises 11.5 Section 12.1 True/False Exercises 12.1 Section 12.3 True/False Exercises 12.3 Section 12.4 True/False Exercises 12.4 Section 12.5 True/False Exercises 12.5 Exercises 12.6 Exercises 13.1 Section 13.2 True/False Exercises 13.2 Section 13.3 True/False Exercises 13.3 Section 14,1 True/False Exercises 14.1 Section 14.2 True/False Exercises 14.2 Section 14.3 True/False Exercises 14.3 Section 14.4 True/False Exercises 14.4 Glossary c Index I5CRETE ATHEMATIC5 I5CRETE АТПЕМАТ1С5 Preface New in the Third Edition Thank You To the Student From a Student EXERCISES Suggested Lecture Schedule Yes, There are Proofs! Logic Contents Yes, There Are Proofs! 1 Logic 2 Sets and Relations 3 Functions 4 The Integers 1 19 38 72 98 7 Permutations and Combinations 205 о Yes, There Are Proofs! 0.1 Compound Statements “And” and “Or” Implication The Converse of an Implication Double Implication Negation The Contrapositive Quantifiers What May I Assume? True/False Questions Exercises 0.2 Proofs in Mathematics Direct Proof Proof by Cases Prove the Contrapositive True/False Questions Exercises Review Exercises for Chapter О Logic 1.1 Truth Tables True/False Questions Exercises 1.2 The Algebra of Propositions Some Basic Logical Equivalences EXAMPLE 10 EXAMPLE 11 Application: Three-Way Switches True/False Questions Exercises 1.3 Logical Arguments Rules of Inference a True/False Questions Exercises 2 Sets and Relations 2.1 Sets True/False Questions Exercises 2.2 Operations on Sets Union and Intersection True/False Questions Exercises 2.3 Binary Relations EXAMPLE 16 EXAMPLE 18 Higher-Order Relations True/False Questions Exercises 2.4 Equivalence Relations EXAMPLE 32 True/FaIse Questions Exercises 2.5 Partial Orders True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 2 3.1 3 Functions Baste Terminology The Identity Function The Ins and Outs of Functions True/False Questions Exercises 3.2 Inverses and Composition EXAMPLE 19 Composition of Functions True/False Questions Exercises 3.3 One-to-One Correspondence and the Cardinality of a Set Key Terms & Ideas Review Exercises for Chapter 3 The Integers 4.1 The Division Algorithm •e Representing Natural Numbers in Various Bases True/False Questions Exercises 4.2 Divisibility and the Euclidean Algorithm Solution. We have The Lattice of Divisors of a Natural Number True/False Questions Exercises 4.3 Prime Numbers Mersenne Primes Fermat Primes How Many Primes Are There? More Open Problems True/False Questions Exercises True/False Questions Exercises 4.5 Applications of Congruence International Standard Book Numbers Universal Product Codes The Chinese Remainder Theorem Determining Numbers by Their Remainders Cryptography True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 4 5 Induction and Recursion 5.1 Mathematical Induction Mathematical Induction and Well Ordering True/False Questions Exercises 5.2 Recursively Defined Sequences Some Special Sequences an = a + (n — l)d. $ = ^[2a + (n-lW], = |(2 ■ 3"-1 + 3"-1 - 1) = 1(3 ■ 3й-’ - 1) = |(3" - 1) Application: Pseudorandom Numbers True/False Questions Exercises 5.3 Solving Recurrence Relations; The Characteristic Polynomial True/False Questions Exercises 5.4 Solving Recurrence Relations; Generating Functions Key Terms & Ideas Review Exercises for Chapter 5 6 Principles of Counting 6.1 The Principle of Inclusion-Exclusion True/False Questions Exercises 6.2 The Addition and Multiplication Rules True/False Questions Exercises 6.3 Pause 9 True/False Questions Exercises Review Exercises for Chapter 6 Permutations and Combinations 7.1 Permutations Л? = Л(Д-1)(Л-2)..(3)(2)(1) True/False Questions Exercises 7.2 Combinations Pin. r) ”71 True/False Questions Exercises 7.3 Elementary Probability Solution. Solution. 11. True/False Questions Exercises 7.4 Probability Theory 14. 17. True/False Questions Exercises 7*5 Repetitions P(n,r) True/Fafse Questions Exercises 7.6 Derangements True/False Questions Exercises 7.7 The Binomial Theorem Solution. Solution. True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 7 8 Algorithms 8.1 What Is an Algorithm? = a0 + (aL + (a2 + j- (an_, + a„x)x) ■ • • )*• True/False Questions Exercises 8.2 Complexity EXAMPLE 8 EXAMPLE 9 True/False Questions Exercises 8.3 Searching and Sorting EXAMPLE 23 For the input list True/False Questions Exercises 8.4 Enumeration of Permutations and Combinations True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 8 Graphs 9.1 A Gentle Introduction True/False Questions Exercises 9.2 Definitions and Basic Properties True/False Questions Exercises 9.3 Isomorphism True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 9 10 Paths and Circuits 10.1 Eulerian Circuits True/False Questions Exercises 10.2 Hamiltonian Cycles Application: Gray Codes6 True/False Questions Exercises 10.3 The Adjacency Matrix EXAMPLE 8 True/False Questions Exercises 10.4 Shortest Path Algorithms The Traveling Salesman's Problem True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 1O 11 Applications of Paths and Circuits 11.1 The Chinese Postman Problem Figure 11.1 True/False Questions Exercises 11.2 Digraphs True/False Questions Exercises 11.3 RNA Chains I True/False Questions Exercises *11.4 Tournaments True/False Questions Exercises 11.5 Scheduling Problems Figure 11.26 Figure 11.27 Exercises Key Terms & Ideas Review Exercises for Chapter 11 12 Trees 12.1 Trees and their Properties Figure 12 .8 Figure 12.12 True/False Questions Exercises 12.2 Spanning Trees True/False Questions Exercises 12-3 Minimum Spanning Tree Algorithms A Bound for a Minimum Hamiltonian Cycle True/False Questions Exercises 12. 4 Acyclic Digraphs and Bellman's Algorithm True/False Questions Figure 12,22 Exercises 12.5 Depth-First Search True/False Questions Exercises Figure 12.26 12.6 The One-Way Street Problem Exercises Key Terms & Ideas Review Exercises for Chapter 12 13 Planar Graphs and Colorings 13.1 Planar Graphs All V - E + F = 2, True/False Questions Exercises 13.2 Coloring Graphs True/False Questions Exercises Child Doesn't get along with 13.3 Circuit Testing and Facilities Design Circuit Testing Figure 13.19 Facilities Design Figure 13. 22 8. NoNoNo).No.No). True/False Questions Exercises Figure 13.24 Key Terms & Ideas Review Exercises for Chapter 13 The Max Flow-Min Cut Theorem 14.1 Flows and Cuts The Construction of Flows True/False Questions Exercises 14.2 Constructing Maximal Flows val(^) = £2 ~ = £2 “ °) = X2 Cuv ~ caP^’ T>>- Rational Weights True/False Questions Exercises 14.3 Applications Multiple Sources and/or Sinks Supply and Demand Problems Undirected Edges Edge-Disjoint Paths Job Assignments True/False Questions Exercises 14.4 Matchings True/False Questions Exercises Key Terms & Ideas Review Exercises for Chapter 14 Bettor Teams Matrices and Determinants Determinants Evaluating a Determinant with Elementary Row Operations EXAMPLE 5 Solutions to True/False Questions and Selected Exercises Exercises 0,1 Section 0.2 True/False Exercises 0.2 Section 1.1 True/False Exercises 1.1 Exercises 1.2 Exercises 1.3 Section 2.1 True/False Exercises 2.1 Section 2.2 True/False Exercises 2.2 Exercises 2.3 Section 2.4 True/False Exercises 2.4 Section 2.5 True/False Exercises 2.5 Section 3.1 True/False Exercises 3.1 Section 3.2 True/False Exercises 3.2 Section 3.3 True/False Exercises 3.3 Section 4.1 True/False Exercises 4.1 Section 4.2 True/False Exercises 4.2 Section 4.3 True/False Exercises 4.3 Section 4.4 True/False Exercises 4.4 Section 4.5 True/False Exercises 4.5 Section 5.1 True/False Exercises 5.1 Section 5.2 True/False Exercises 5.2 Section 5.3 True/False Exercises 5.3 Section 5.4 True/False Exercises 5.4 Section 6.1 True/False Exercises 6.1 Section 6.2 True/False Exercises 6.2 Section 6.3 True/False Exercises 6.3 Section 7.1 True/False Exercises 7.1 Section 7.2 True/False Exercises 7.2 Section 7.3 True/False Exercises 7.3 Section 7.4 True/False Exercises 7.4 Section 7.5 True/False Exercises 7.5 Section 7.6 True/False Exercises 7.6 Section 7.7 True/False Exercises 7.7 Section 8.1 True/False Exercises 8.1 Section 8.2 True/False Exercises 8.2 Section 8.3 True/False Exercises 8.3 Section 8.4 True/False Section 9.1 True/False Exercises 9.1 Section 9.2 True/False Exercises 9.2 Section 9.3 True/False Exercises 9.3 Section 10.1 True/False Section 10.2 True/False Exercises 10.2 Section 10.3 True/False Exercises 10.3 Section 10.4 True/False Exercises 10.4 Section 11.1 True/False Section 11.2 True/False Exercises 11.2 Section 11.3 True/False Exercises 11.3 Section 11.4 True/False Exercises 11.4 Section 11.5 True/False Exercises 11.5 Section 12.1 True/False Exercises 12.1 Section 12.3 True/False Exercises 12.3 Section 12.4 True/False Exercises 12.4 Section 12.5 True/False Exercises 12.5 Exercises 12.6 Exercises 13.1 Section 13.2 True/False Exercises 13.2 Section 13.3 True/False Exercises 13.3 Section 14,1 True/False Exercises 14.1 Section 14.2 True/False Exercises 14.2 Section 14.3 True/False Exercises 14.3 Section 14.4 True/False Exercises 14.4 Glossary c Index I5CRETE ATHEMATIC5