《计算机问题求解》课程教学资源：《Discrete Mathematics for Computer Scientists》参考书籍教材（Stein、DrysdaleBogart）

Contents xvii Matching in Bipartite Graphs 417 Searching for Augmenting Paths in Bipartite Graphs 417 The Augmentation-Cover Algorithm 420 Efficient Algorithms 426 Important Concepts,Formulas,and Theorems 427 Problems 428 6.5 Coloring and Planarity 430 The Idea of Coloring 430 Interval Graphs 433 Planarity 435 The Faces of a Planar Drawing 437 The Five-Color Theorem 441 Important Concepts,Formulas,and Theorems 444 Problems 445 APPENDIX A Derivation of the More General Master Theorem 449 More General Recurrences 449 Recurrences for General n 451 Removing Floors and Ceilings 452 Floors and Ceilings in the Stronger Version of the Master Theorem 453 Proofs of Theorems 453 Important Concepts,Formulas,and Theorems 457 Problems 458 APPENDIX B Answers and Hints to Selected Problems 461 Bibliography 477 Index 479

Contents xvii Matching in Bipartite Graphs 417 Searching for Augmenting Paths in Bipartite Graphs 417 The Augmentation-Cover Algorithm 420 Efficient Algorithms 426 Important Concepts, Formulas, and Theorems 427 Problems 428 6.5 Coloring and Planarity 430 The Idea of Coloring 430 Interval Graphs 433 Planarity 435 The Faces of a Planar Drawing 437 The Five-Color Theorem 441 Important Concepts, Formulas, and Theorems 444 Problems 445 APPENDIX A Derivation of the More General Master Theorem 449 More General Recurrences 449 Recurrences for General n 451 Removing Floors and Ceilings 452 Floors and Ceilings in the Stronger Version of the Master Theorem 453 Proofs of Theorems 453 Important Concepts, Formulas, and Theorems 457 Problems 458 APPENDIX B Answers and Hints to Selected Problems 461 Bibliography 477 Index 479

List of Theorems,Lemmas, and corollaries Chapter 1 Corollary 2.18.......................89 Theorem1.1..........16 Corollary 2.22.....................97 Theorem 1.2. 18 Theorem 1.3. 25 Chapter 3 Theorem 1.4. 26 Theorem3.2........................139 Theorem 1.5......................... 38 Theorem3.3.........141 Theorem 1.6. 39 Theorem 1.7......................... 46 Lemma3.1..........123 Theorem 1.8.......52 Lemma3.5.........154 Chapter 2 Corollary3.4.........141 Theorem2.1..…......… 61 Theorem 2.4......................... 67 Chapter 4 Theorem2.7....................... 78 Theorem 4.1........................188 Theorem2.9. 80 Theorem4.4.........191 Theorem 2.12....................... 82 Theorem 4.5 ..192 Theorem 2.14........................ 88 Theorem4.6........195 Theorem 2.15 88 Theorem 4.9....................... 215 Theorem 2.21 .96 Theorem2.23........101 Theorem 4.10..................... 219 Theorem4.1l. 220 Theorem2.24.........101 Theorem 4.12. .224 Theorem4.15.........244 Lemma 2.2. 65 Lemma 2.3 66 Lemma 4.3 190 Lemma 2.5 .75 Lemma4.7..........209 Lemma2.8.........79 Lemma4.14.......... 242 Lemma2.11..........81 Lemma 2.13 83 Corollary 4.2 189 Lemma 2.19 小+…小4小+…小。… 93 Corollary 4.8 210 Lemma 2.20 96 Corollary 4.13 .224 Lemma 2.25 ….111 Chapter 5 Corollary 2.6 .77 Corollary 2.10 80 Theorem5.1.........253 Corollary 2.16 88 Theorem 5.2 .256 Corollary2.17......... Theorem53......... .266 xix

List of Theorems, Lemmas, and Corollaries Chapter 1 Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . 16 Theorem 1.2 . . . . . . . . . . . . . . . . . . . . . . . . . 18 Theorem 1.3 . . . . . . . . . . . . . . . . . . . . . . . . . 25 Theorem 1.4 . . . . . . . . . . . . . . . . . . . . . . . . . 26 Theorem 1.5 . . . . . . . . . . . . . . . . . . . . . . . . . 38 Theorem 1.6 . . . . . . . . . . . . . . . . . . . . . . . . . 39 Theorem 1.7 . . . . . . . . . . . . . . . . . . . . . . . . . 46 Theorem 1.8 . . . . . . . . . . . . . . . . . . . . . . . . . 52 Chapter 2 Theorem 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . 61 Theorem 2.4 . . . . . . . . . . . . . . . . . . . . . . . . . 67 Theorem 2.7 . . . . . . . . . . . . . . . . . . . . . . . . . 78 Theorem 2.9 . . . . . . . . . . . . . . . . . . . . . . . . . 80 Theorem 2.12 . . . . . . . . . . . . . . . . . . . . . . . . 82 Theorem 2.14 . . . . . . . . . . . . . . . . . . . . . . . . 88 Theorem 2.15 . . . . . . . . . . . . . . . . . . . . . . . . 88 Theorem 2.21 . . . . . . . . . . . . . . . . . . . . . . . . 96 Theorem 2.23. . . . . . . . . . . . . . . . . . . . . . . 101 Theorem 2.24. . . . . . . . . . . . . . . . . . . . . . . 101 Lemma 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Lemma 2.3 . . . . . . . . . . . . . . . . . . . . . . . . . . 66 Lemma 2.5 . . . . . . . . . . . . . . . . . . . . . . . . . . 75 Lemma 2.8 . . . . . . . . . . . . . . . . . . . . . . . . . . 79 Lemma 2.11 . . . . . . . . . . . . . . . . . . . . . . . . . 81 Lemma 2.13 . . . . . . . . . . . . . . . . . . . . . . . . . 83 Lemma 2.19 . . . . . . . . . . . . . . . . . . . . . . . . . 93 Lemma 2.20 . . . . . . . . . . . . . . . . . . . . . . . . . 96 Lemma 2.25 . . . . . . . . . . . . . . . . . . . . . . . . 111 Corollary 2.6 . . . . . . . . . . . . . . . . . . . . . . . . 77 Corollary 2.10 . . . . . . . . . . . . . . . . . . . . . . . 80 Corollary 2.16 . . . . . . . . . . . . . . . . . . . . . . . 88 Corollary 2.17 . . . . . . . . . . . . . . . . . . . . . . . 88 Corollary 2.18 . . . . . . . . . . . . . . . . . . . . . . . 89 Corollary 2.22 . . . . . . . . . . . . . . . . . . . . . . . 97 Chapter 3 Theorem 3.2 . . . . . . . . . . . . . . . . . . . . . . . . 139 Theorem 3.3 . . . . . . . . . . . . . . . . . . . . . . . . 141 Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . 123 Lemma 3.5 . . . . . . . . . . . . . . . . . . . . . . . . . 154 Corollary 3.4 . . . . . . . . . . . . . . . . . . . . . . . 141 Chapter 4 Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . 188 Theorem 4.4 . . . . . . . . . . . . . . . . . . . . . . . . 191 Theorem 4.5 . . . . . . . . . . . . . . . . . . . . . . . . 192 Theorem 4.6 . . . . . . . . . . . . . . . . . . . . . . . . 195 Theorem 4.9 . . . . . . . . . . . . . . . . . . . . . . . . 215 Theorem 4.10. . . . . . . . . . . . . . . . . . . . . . . 219 Theorem 4.11. . . . . . . . . . . . . . . . . . . . . . . 220 Theorem 4.12. . . . . . . . . . . . . . . . . . . . . . . 224 Theorem 4.15. . . . . . . . . . . . . . . . . . . . . . . 244 Lemma 4.3 . . . . . . . . . . . . . . . . . . . . . . . . . 190 Lemma 4.7 . . . . . . . . . . . . . . . . . . . . . . . . . 209 Lemma 4.14 . . . . . . . . . . . . . . . . . . . . . . . . 242 Corollary 4.2 . . . . . . . . . . . . . . . . . . . . . . . 189 Corollary 4.8 . . . . . . . . . . . . . . . . . . . . . . . 210 Corollary 4.13 . . . . . . . . . . . . . . . . . . . . . . 224 Chapter 5 Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . 253 Theorem 5.2 . . . . . . . . . . . . . . . . . . . . . . . . 256 Theorem 5.3 . . . . . . . . . . . . . . . . . . . . . . . . 266 xix

xx List of Theorems,Lemmas,and Corollaries Theorem5.4..........272 Theorem6.9........381 Theorem5.5.......280 Theorem 6.10. …….392 Theorem5.7.......282 Theorem6.11.........393 Theorem 5.8........................294 Theorem 6.12.......398 Theorem 5.10. 300 Theorem 6.13. ...400 Theorem 5.11...................... 300 Theorem 6.18. 417 Theorem 5.12 301 Theorem6.20........424 Theorem 5.13.. .305 Theorem 6.22. .425 Theorem 5.14. .311 Theorem6.24.… .434 Theorem 5.15 .311 Theorem 6.26. 439 Theorem5.16..........312 Theorem 6.29 .441 Theorem 5.17 .314 Theorem 5.22 .319 Lemma 6.1......................... 363 Theorem 5.23.......329 Lemma6.4.… 370 Theorem 5.24. 333 Lemma6.8.........380 Theorem 5.25 …….336 Lemma6.14.......… 413 Theorem 5.29. ...350 Lemma6.15..........413 Theorem5.30..........353 Lemma6.16.......415 Lemma6.23.........432 Lemma5.9.......298 Lemma5.18.........315 Corollary6.6........371 Lemma5.19.....316 Corollary 6.17 416 Lemma5.20.......317 Corollary6.19.........417 Lemma5.21.....318 Corollary 6.21......................425 Lemma5.26........346 Corollary 6.25...................... 435 Lemma5.28........349 Corollary6.27........440 Corollary 6.28 .440 Corollary 5.6....................... 281 Corollary 5.27 .346 Appendix A Chapter 6 Theorem A.1 451 Theorem A.2 452 Theorem6.2.......363 Theorem A.3 453 Theorem6.3.........369 Theorem A.4 454 Theorem 6.5........................371 Theorem A.5 455 Theorem6.7........375

xx List of Theorems, Lemmas, and Corollaries Theorem 5.4 . . . . . . . . . . . . . . . . . . . . . . . . 272 Theorem 5.5 . . . . . . . . . . . . . . . . . . . . . . . . 280 Theorem 5.7 . . . . . . . . . . . . . . . . . . . . . . . . 282 Theorem 5.8 . . . . . . . . . . . . . . . . . . . . . . . . 294 Theorem 5.10. . . . . . . . . . . . . . . . . . . . . . . 300 Theorem 5.11. . . . . . . . . . . . . . . . . . . . . . . 300 Theorem 5.12. . . . . . . . . . . . . . . . . . . . . . . 301 Theorem 5.13. . . . . . . . . . . . . . . . . . . . . . . 305 Theorem 5.14. . . . . . . . . . . . . . . . . . . . . . . 311 Theorem 5.15. . . . . . . . . . . . . . . . . . . . . . . 311 Theorem 5.16. . . . . . . . . . . . . . . . . . . . . . . 312 Theorem 5.17. . . . . . . . . . . . . . . . . . . . . . . 314 Theorem 5.22. . . . . . . . . . . . . . . . . . . . . . . 319 Theorem 5.23. . . . . . . . . . . . . . . . . . . . . . . 329 Theorem 5.24. . . . . . . . . . . . . . . . . . . . . . . 333 Theorem 5.25. . . . . . . . . . . . . . . . . . . . . . . 336 Theorem 5.29. . . . . . . . . . . . . . . . . . . . . . . 350 Theorem 5.30. . . . . . . . . . . . . . . . . . . . . . . 353 Lemma 5.9 . . . . . . . . . . . . . . . . . . . . . . . . . 298 Lemma 5.18 . . . . . . . . . . . . . . . . . . . . . . . . 315 Lemma 5.19 . . . . . . . . . . . . . . . . . . . . . . . . 316 Lemma 5.20 . . . . . . . . . . . . . . . . . . . . . . . . 317 Lemma 5.21 . . . . . . . . . . . . . . . . . . . . . . . . 318 Lemma 5.26 . . . . . . . . . . . . . . . . . . . . . . . . 346 Lemma 5.28 . . . . . . . . . . . . . . . . . . . . . . . . 349 Corollary 5.6 . . . . . . . . . . . . . . . . . . . . . . . 281 Corollary 5.27 . . . . . . . . . . . . . . . . . . . . . . 346 Chapter 6 Theorem 6.2 . . . . . . . . . . . . . . . . . . . . . . . . 363 Theorem 6.3 . . . . . . . . . . . . . . . . . . . . . . . . 369 Theorem 6.5 . . . . . . . . . . . . . . . . . . . . . . . . 371 Theorem 6.7 . . . . . . . . . . . . . . . . . . . . . . . . 375 Theorem 6.9 . . . . . . . . . . . . . . . . . . . . . . . . 381 Theorem 6.10. . . . . . . . . . . . . . . . . . . . . . . 392 Theorem 6.11. . . . . . . . . . . . . . . . . . . . . . . 393 Theorem 6.12. . . . . . . . . . . . . . . . . . . . . . . 398 Theorem 6.13. . . . . . . . . . . . . . . . . . . . . . . 400 Theorem 6.18. . . . . . . . . . . . . . . . . . . . . . . 417 Theorem 6.20. . . . . . . . . . . . . . . . . . . . . . . 424 Theorem 6.22. . . . . . . . . . . . . . . . . . . . . . . 425 Theorem 6.24. . . . . . . . . . . . . . . . . . . . . . . 434 Theorem 6.26. . . . . . . . . . . . . . . . . . . . . . . 439 Theorem 6.29. . . . . . . . . . . . . . . . . . . . . . . 441 Lemma 6.1 . . . . . . . . . . . . . . . . . . . . . . . . . 363 Lemma 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . 370 Lemma 6.8 . . . . . . . . . . . . . . . . . . . . . . . . . 380 Lemma 6.14 . . . . . . . . . . . . . . . . . . . . . . . . 413 Lemma 6.15 . . . . . . . . . . . . . . . . . . . . . . . . 413 Lemma 6.16 . . . . . . . . . . . . . . . . . . . . . . . . 415 Lemma 6.23 . . . . . . . . . . . . . . . . . . . . . . . . 432 Corollary 6.6 . . . . . . . . . . . . . . . . . . . . . . . 371 Corollary 6.17 . . . . . . . . . . . . . . . . . . . . . . 416 Corollary 6.19 . . . . . . . . . . . . . . . . . . . . . . 417 Corollary 6.21 . . . . . . . . . . . . . . . . . . . . . . 425 Corollary 6.25 . . . . . . . . . . . . . . . . . . . . . . 435 Corollary 6.27 . . . . . . . . . . . . . . . . . . . . . . 440 Corollary 6.28 . . . . . . . . . . . . . . . . . . . . . . 440 Appendix A Theorem A.1 . . . . . . . . . . . . . . . . . . . . . . . 451 Theorem A.2 . . . . . . . . . . . . . . . . . . . . . . . 452 Theorem A.3 . . . . . . . . . . . . . . . . . . . . . . . 453 Theorem A.4 . . . . . . . . . . . . . . . . . . . . . . . 454 Theorem A.5 . . . . . . . . . . . . . . . . . . . . . . . 455

Preface OUR MOTIVATION AND VISION Many colleges and universities offer a course in discrete mathematics.Stu- dents taking these courses are from many disciplines,one of the largest being computer science.As a part of the Mathematics Across the Curricu- lum project at Dartmouth,supported by the National Science Foundation, we proposed to create a discrete mathematics course that directly addresses the needs of computer science students.In analyzing what topics in discrete mathematics we want our computer science students to know and why we want them to know these topics,we made two observations. First,there are a few topics we consider important to computer science that are not always covered thoroughly,if at all,in traditional discrete mathe- matics courses.Among these are recursion trees and the Master Theorem for solving recurrence relations,the probability theory needed to compute average run times and to analyze randomized algorithms,and an emphasis on strong and structural induction. Second,for each topic in discrete mathematics that we consider impor- tant for computer science students,there is a motivating topic in computer science that can be understood at the level of a first or second course in computer science.We feel this makes it possible to answer the age-old ques- tion students ask in applied mathematics courses:"Why do we have to learn this?"We therefore chose to write a textbook with computer science stu- dents in mind,with the objective of providing the necessary mathematical foundations for a computer science major,motivated by computer science problems that students can understand early in their study of computer science. In many computer science departments,discrete mathematics is one of the first courses taken by majors.It may even be a prerequisite to the first computer science course.In this case instructors are faced with a dilemma- teach the concepts purely mathematically with little or no visible application to computer science,or teach computer science examples to create a context Grant Number DUE-9552462 xxi

Preface OUR MOTIVATION AND VISION Many colleges and universities offer a course in discrete mathematics. Stu￾dents taking these courses are from many disciplines, one of the largest being computer science. As a part of the Mathematics Across the Curricu￾lum project at Dartmouth, supported by the National Science Foundation,1 we proposed to create a discrete mathematics course that directly addresses the needs of computer science students. In analyzing what topics in discrete mathematics we want our computer science students to know and why we want them to know these topics, we made two observations. First, there are a few topics we consider important to computer science that are not always covered thoroughly, if at all, in traditional discrete mathe￾matics courses. Among these are recursion trees and the Master Theorem for solving recurrence relations, the probability theory needed to compute average run times and to analyze randomized algorithms, and an emphasis on strong and structural induction. Second, for each topic in discrete mathematics that we consider impor￾tant for computer science students, there is a motivating topic in computer science that can be understood at the level of a first or second course in computer science. We feel this makes it possible to answer the age-old ques￾tion students ask in applied mathematics courses: “Why do we have to learn this?” We therefore chose to write a textbook with computer science stu￾dents in mind, with the objective of providing the necessary mathematical foundations for a computer science major, motivated by computer science problems that students can understand early in their study of computer science. In many computer science departments, discrete mathematics is one of the first courses taken by majors. It may even be a prerequisite to the first computer science course. In this case instructors are faced with a dilemma— teach the concepts purely mathematically with little or no visible application to computer science, or teach computer science examples to create a context 1Grant Number DUE-9552462 xxi

xxii Preface relevant to computer science students.The first leaves students complain- ing that they are being forced to take too much "irrelevant"'mathematics before they can take their first computer science course.The second leaves professors (who are often mathematicians)trying to explain fairly advanced computer science topics such as hashing,binary trees,and recursive pro- grams to students who may never have written a program.Even under the best of circumstances,this approach significantly reduces the depth of the mathematics that can be taught.Our analysis led to a different approach, creating a course that appears slightly later in students'studies.While we do not explicitly assume students have taken calculus,we assume familiar- ity with and make significant use of summation notation,logarithms,and exponential functions,so that a strong understanding of precalculus mate- rial is very helpful.?This course is meant to be taken after an introductory computer science course where students have seen recursive programs.Ide- ally it would be taken concurrently with or after a data structures course, but we explain the data structures that we use as examples.Therefore a data structures course is not a prerequisite for this course. We feel that there are several advantages to this placement.Particular examples include: Students have already had serious experience thinking about problem solving,algorithms,and writing code. Students have learned or are ready to learn several important computer science concepts such as hashing,recursion,sorting and searching,and basic data structures. Students know enough computer science that they already know the motivating examples or the examples are straightforward enough for them to understand.For example, Hashing can be used to motivate the study of probability Analysis of recursive programs such as mergesort and quicksort can be used to motivate recurrence relations and their solutions -Analyzing how often we expect to find a new minimum in a procedure that finds the minimum element of a list can be used to motivate studying linearity of expectation and harmonic numbers. 2Most of our students have had calculus.In isolated places we make use of elementary derivatives and in optional subsections in probability we use natural logarithm and exponential functions and elementary power series.By ignoring the few proofs or problems using derivatives and the optional subsections in probability,the instructor can avoid calculus

xxii Preface relevant to computer science students. The first leaves students complain￾ing that they are being forced to take too much “irrelevant” mathematics before they can take their first computer science course. The second leaves professors (who are often mathematicians) trying to explain fairly advanced computer science topics such as hashing, binary trees, and recursive pro￾grams to students who may never have written a program. Even under the best of circumstances, this approach significantly reduces the depth of the mathematics that can be taught. Our analysis led to a different approach, creating a course that appears slightly later in students’ studies. While we do not explicitly assume students have taken calculus, we assume familiar￾ity with and make significant use of summation notation, logarithms, and exponential functions, so that a strong understanding of precalculus mate￾rial is very helpful.2 This course is meant to be taken after an introductory computer science course where students have seen recursive programs. Ide￾ally it would be taken concurrently with or after a data structures course, but we explain the data structures that we use as examples. Therefore a data structures course is not a prerequisite for this course. We feel that there are several advantages to this placement. Particular examples include: • Students have already had serious experience thinking about problem solving, algorithms, and writing code. • Students have learned or are ready to learn several important computer science concepts such as hashing, recursion, sorting and searching, and basic data structures. • Students know enough computer science that they already know the motivating examples or the examples are straightforward enough for them to understand. For example, – Hashing can be used to motivate the study of probability. – Analysis of recursive programs such as mergesort and quicksort can be used to motivate recurrence relations and their solutions. – Analyzing how often we expect to find a new minimum in a procedure that finds the minimum element of a list can be used to motivate studying linearity of expectation and harmonic numbers. 2Most of our students have had calculus. In isolated places we make use of elementary derivatives and in optional subsections in probability we use natural logarithm and exponential functions and elementary power series. By ignoring the few proofs or problems using derivatives and the optional subsections in probability, the instructor can avoid calculus