Contents v 10 Graphs................................641 10.1 Graphs and Graph Models 641 10.2 Graph Terminology and Special Types of Graphs 65 10.3 Representing Graphs and Graph Isomorphism. .668 104 Connectivity ..678 10 5 Euler and Hamilton Paths 693 10.6 Shortest-Path Problems .707 10.7 Planar G aphs 。。。， 718 10.8 Graph Coloring. 727 End-of-Chapter Material 735 11 Trees............................................................... 745 11.1 Introduction to Trees 745 11.2 Applications of Trees. .757 113 Tree Traversal .772 114 Spanning Trees 785 11.5 Minimum Spanning Trees 707 End-of-Chapter Material 803 12 Boolean Algebra. .811 12.1 Boolean Functions .811 12.2 Representing Boolean Functions 9 123 Logic Gates 82 12.4 Minimization of Circuits ,828 End-of-Chapter Material. .843 13 Modeling Computation.................................... 847 13.1 Languages and Grammars 84 13.2 Finite-State Machines with Output....................................... ....858 13.3 Finite-State Machines with No Output .865 134 Language Recognition 878 13 5 Turing Machines 888 End-of-Chapter Material 899 Appendixes......A-1 Axioms for the Real Numbers and the Positive Intege 1 Exponential and Logarithmic Functions Pseudocod Suggested Readin s B-1 AweOdd-Numbered Exercises 5- Photo Credits C-1
Contents v 10 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641 10.1 Graphs and Graph Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641 10.2 Graph Terminology and Special Types of Graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .651 10.3 Representing Graphs and Graph Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668 10.4 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678 10.5 Euler and Hamilton Paths. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693 10.6 Shortest-Path Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707 10.7 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718 10.8 Graph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735 11 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745 11.1 Introduction to Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745 11.2 Applications of Trees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .757 11.3 Tree Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 772 11.4 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785 11.5 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803 12 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811 12.1 Boolean Functions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 811 12.2 Representing Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 819 12.3 Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 822 12.4 Minimization of Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 828 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843 13 Modeling Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847 13.1 Languages and Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847 13.2 Finite-State Machines with Output. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .858 13.3 Finite-State Machines with No Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865 13.4 Language Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 878 13.5 Turing Machines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .888 End-of-Chapter Material . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 899 Appendixes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A-1 1 Axioms for the Real Numbers and the Positive Integers ............................1 2 Exponential and Logarithmic Functions ..........................................7 3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Suggested Readings B-1 Answers to Odd-Numbered Exercises S-1 Photo Credits C-1 Index of Biographies I-1 Index I-2
About the author enneth H rosen has had a long career as a distinguished member of the Technical staff at AT&T Laboratories in Monmouth County.New Jersey.He currently holds the position of Visiting Research Professor at Monmouth University,where he teaches graduate courses in computer science. (1972).and his Phed the University of Michan. oulder:Th n193 and the unive rsity of Maine.Orono.where he was an associate professor of mather While working at AT&T Labs,he taught at Monmouth University,teaching courses in discrete mathematics,coding theory,and data security.He currently teaches courses in algorithm design and in computer security and cryptography. Dr.Rosen has publis numerous articles in pro ofessional journals in number theory and the author of e w into Chinese.He is also the author of maties and its McGraw-Hill,currently in its seventh edition.Discrete Mathematics and Its Applications has sold more than 350,000 copies in North America during its lifetime,and hundreds of thousands of copies throughout the rest of the world.This book has also been tra ated into Spanish tnamese,and Korean.He is als l T Chinese.Gierman s and Italiar Dr Rosen is also the editor of the Han and Combinatorial Mathematics,published by CRC Press,and he is the advisory editor of the CRC series of books in discrete mathematics,consisting of more than 55 volumes on different s,most ofwhichare introduced in this book.Dr.Rosenservesasan ociate Edito or the jou where he works with sub iesaleeasofd rete math matics,inclu ing graph theory,enum Inc's Ma in both these areas.Dr.Rosen has also worked with several publishing companies on their homework delivery platforms includingosorked on wide range of proects. search studies,product line ta commun and t 0y cCh8pepanARTPan ork in the area of image networking.He also invented many new services,and holds more than 55 patents.One ofhis more interesting projects involved helping evaluate technology for the AT&T attraction that was part of EPCOT Center
About the Author Kenneth H. Rosen has had a long career as a Distinguished Member of the Technical Staff at AT&T Laboratories in Monmouth County, New Jersey. He currently holds the position of Visiting Research Professor at Monmouth University, where he teaches graduate courses in computer science. Dr. Rosen received his B.S. in Mathematics from the University of Michigan, Ann Arbor (1972), and his Ph.D. in Mathematics from M.I.T. (1976), where he wrote his thesis in the area of number theory under the direction of Harold Stark. Before joining Bell Laboratories in 1982, he held positions at the University of Colorado, Boulder; The Ohio State University, Columbus; and the University of Maine, Orono, where he was an associate professor of mathematics. While working at AT&T Labs, he taught at Monmouth University, teaching courses in discrete mathematics, coding theory, and data security. He currently teaches courses in algorithm design and in computer security and cryptography. Dr. Rosen has published numerous articles in professional journals in number theory and in mathematical modeling. He is the author of the widely used Elementary Number Theory and Its Applications, published by Pearson, currently in its sixth edition, which has been translated into Chinese. He is also the author of Discrete Mathematics and Its Applications, published by McGraw-Hill, currently in its seventh edition. Discrete Mathematics and Its Applications has sold more than 350,000 copies in North America during its lifetime, and hundreds of thousands of copies throughout the rest of the world. This book has also been translated into Spanish, French, Greek, Chinese, Vietnamese, and Korean. He is also co-author of UNIX: The Complete Reference; UNIX SystemV Release 4: An Introduction; and Best UNIX Tips Ever, all published by Osborne McGraw-Hill. These books have sold more than 150,000 copies, with translations into Chinese, German, Spanish, and Italian. Dr. Rosen is also the editor of the Handbook of Discrete and Combinatorial Mathematics, published by CRC Press, and he is the advisory editor of the CRC series of books in discrete mathematics, consisting of more than 55 volumes on different aspects of discrete mathematics, most of which are introduced in this book. Dr. Rosen serves as an Associate Editor for the journal Discrete Mathematics, where he works with submitted papers in several areas of discrete mathematics, including graph theory, enumeration, and number theory. He is also interested in integrating mathematical software into the educational and professional environments, and worked on several projects with Waterloo Maple Inc.’s MapleTM software in both these areas. Dr. Rosen has also worked with several publishing companies on their homework delivery platforms. At Bell Laboratories andAT&T Laboratories, Dr. Rosen worked on a wide range of projects, including operations research studies, product line planning for computers and data communications equipment, and technology assessment. He helped plan AT&T’s products and services in the area of multimedia, including video communications, speech recognition, speech synthesis, and image networking. He evaluated new technology for use by AT&T and did standards work in the area of image networking. He also invented many new services, and holds more than 55 patents. One of his more interesting projects involved helping evaluate technology for the AT&T attraction that was part of EPCOT Center. vi
Preface n writing this book,I was guided by my long-standing experience and interest in teaching crete matheman the ror the stuc mather atic to students who are often skeptical i wanted to give students studving computer science all of the mathematical foundations they need for their future studies.I wanted to give mathematics students an understanding of important mathematical concepts together with a sense of why these concepts are important for applications.And most importantly,I wanted to accomplish nese goal s with instr g tool usin ly in the most appropriate manner for their particular set of students.I hope that Ihave achedt goals I have been extremely gratified by the tremendous success of this text.The many improve ments in th e have been made possible by the suggestions of a larg s an many of th m 6.l anYeLSsinCorao r two-term i diserete mathematics by students in a wide variety of mai including mathematics computer science and enginee ng college algebra is the only explicit prerequisite although a certain degree of mathematica maturity is needed to study discrete mathematics in a meaningful way.This book has been de signed to meet the needs of almost all types of introductory discrete mathematics courses.It is ensive.Th signe nd profess Goals of a Discrete Mathematics Course A discrete mathematics course has more than one purpose.Students should leamn a particular set of mathematical facts and how to apply them;more importantly,such a course should teach students ho w to thin 10g1 an mat To achieve mathematica se goals,this text stresse g an rent ways pro algorithm ic thinking and applications and modeing successful discrete mathematics cou should carefully blend and balance all five themes 1.Mathematical Reasoning:Students must understand mathematical reasoning in order to na discussion comprehend,and construct mathematical arguments.This text ich serves as the undation for the subs equent d ro the ar athe tructing pre 90 t t technique. vii
Preface In writing this book, I was guided by my long-standing experience and interest in teaching discrete mathematics. For the student, my purpose was to present material in a precise, readable manner, with the concepts and techniques of discrete mathematics clearly presented and demonstrated. My goal was to show the relevance and practicality of discrete mathematics to students, who are often skeptical. I wanted to give students studying computer science all of the mathematical foundations they need for their future studies. I wanted to give mathematics students an understanding of important mathematical concepts together with a sense of why these concepts are important for applications. And most importantly, I wanted to accomplish these goals without watering down the material. For the instructor, my purpose was to design a flexible, comprehensive teaching tool using proven pedagogical techniques in mathematics. I wanted to provide instructors with a package of materials that they could use to teach discrete mathematics effectively and efficiently in the most appropriate manner for their particular set of students. I hope that I have achieved these goals. I have been extremely gratified by the tremendous success of this text. The many improvements in the seventh edition have been made possible by the feedback and suggestions of a large number of instructors and students at many of the more than 600 North American schools, and at any many universities in parts of the world, where this book has been successfully used. This text is designed for a one- or two-term introductory discrete mathematics course taken by students in a wide variety of majors, including mathematics, computer science, and engineering. College algebra is the only explicit prerequisite, although a certain degree of mathematical maturity is needed to study discrete mathematics in a meaningful way. This book has been designed to meet the needs of almost all types of introductory discrete mathematics courses. It is highly flexible and extremely comprehensive. The book is designed not only to be a successful textbook, but also to serve as valuable resource students can consult throughout their studies and professional life. Goals of a Discrete Mathematics Course A discrete mathematics course has more than one purpose. Students should learn a particular set of mathematical facts and how to apply them; more importantly, such a course should teach students how to think logically and mathematically. To achieve these goals, this text stresses mathematical reasoning and the different ways problems are solved. Five important themes are interwoven in this text: mathematical reasoning, combinatorial analysis, discrete structures, algorithmic thinking, and applications and modeling. A successful discrete mathematics course should carefully blend and balance all five themes. 1. Mathematical Reasoning: Students must understand mathematical reasoning in order to read, comprehend, and construct mathematical arguments. This text starts with a discussion of mathematical logic, which serves as the foundation for the subsequent discussions of methods of proof. Both the science and the art of constructing proofs are addressed. The technique of mathematical induction is stressed through many different types of examples of such proofs and a careful explanation of why mathematical induction is a valid proof technique. vii
vii Preface 2.Combinatorial Analysis:An important problem-solving skill is the ability to count or enu- merate objects.The discussion of enumeration in this book begins with the basic techniques 3.Discrete Structures:A course in discrete mathematics should teach students how to work with discrete structures,which are the abstract mathematical structures used to represent discrete objects and relationships between these objects.These discrete structures include sets,permutations,relations,graphs,trees,and finite-state machines 4 Algorithmic Thinking:Certain classes of problems are solved by the specification of an algorithm.After an algorithm has been described,a computer program can be constructed implementing it.The mathematical portions of this activity,which include the specification of the algorithm,the verification that it works properly,and the analysis of the computer 5.Applications and Modeling:Discrete mathematics has applications to almost every conceiv able area of study. Ihere are many applications to computer science and data networking in this t as well as apple a ns to s h diverse areas as chemistry, geography, tremely important problem-solving skill.which students have the opportunity to develop by constructing their own models in some of the exercises. Changes in the Seventh Edition Although the sixth edition has been an extremely effective text many instructors including longtime users.have requested changes designed to make this book more effective.I have devoted a significant amount of time and energy to satisfy their requests and I have worked hard ys to make the book mor ecve and more compend s a major revision,with changes ba om more than 40 0 1S 2 ed to lo theory,and graph theory make this book more flexible and comprehensive.Numerous changes in the seventh edition have been designed to help students more easily learn the material Additional explanations and examples have been added to clarify material where students often have dimculty w exercises. th routine and challenging,have been added. Highly relevan ed to the Int ence,and to thematic nde be as ben from ex nsive deve of discrete mathematics.and many new tools under development will be released in the year following publication of this book. I hone that instructors will closely w edition to diseover how it might r their needs Alth ugh it is impractical to list all the changes in this edition.a brief list that highlights some key changes,listed by the benefits they provide,may be useful. More Flexible Organization A2PlitecgTogcPPeCmeionalogcaefoundnanevdcdicaedsciomwhohbicd Recurrence relations are now covered in Chapter 2. Expanded coverage of countability is now found in a dedicated section in Chapter2
viii Preface 2. Combinatorial Analysis: An important problem-solving skill is the ability to count or enumerate objects. The discussion of enumeration in this book begins with the basic techniques of counting. The stress is on performing combinatorial analysis to solve counting problems and analyze algorithms, not on applying formulae. 3. Discrete Structures: A course in discrete mathematics should teach students how to work with discrete structures, which are the abstract mathematical structures used to represent discrete objects and relationships between these objects. These discrete structures include sets, permutations, relations, graphs, trees, and finite-state machines. 4. Algorithmic Thinking: Certain classes of problems are solved by the specification of an algorithm. After an algorithm has been described, a computer program can be constructed implementing it. The mathematical portions of this activity, which include the specification of the algorithm, the verification that it works properly, and the analysis of the computer memory and time required to perform it, are all covered in this text. Algorithms are described using both English and an easily understood form of pseudocode. 5. Applications and Modeling: Discrete mathematics has applications to almost every conceivable area of study. There are many applications to computer science and data networking in this text, as well as applications to such diverse areas as chemistry, biology, linguistics, geography, business, and the Internet. These applications are natural and important uses of discrete mathematics and are not contrived. Modeling with discrete mathematics is an extremely important problem-solving skill, which students have the opportunity to develop by constructing their own models in some of the exercises. Changes in the Seventh Edition Although the sixth edition has been an extremely effective text, many instructors, including longtime users, have requested changes designed to make this book more effective. I have devoted a significant amount of time and energy to satisfy their requests and I have worked hard to find my own ways to make the book more effective and more compelling to students. The seventh edition is a major revision, with changes based on input from more than 40 formal reviewers, feedback from students and instructors, and author insights. The result is a new edition that offers an improved organization of topics making the book a more effective teaching tool. Substantial enhancements to the material devoted to logic, algorithms, number theory, and graph theory make this book more flexible and comprehensive. Numerous changes in the seventh edition have been designed to help students more easily learn the material. Additional explanations and examples have been added to clarify material where students often have difficulty. New exercises, both routine and challenging, have been added. Highly relevant applications, including many related to the Internet, to computer science, and to mathematical biology, have been added. The companion website has benefited from extensive development activity and now provides tools students can use to master key concepts and explore the world of discrete mathematics, and many new tools under development will be released in the year following publication of this book. I hope that instructors will closely examine this new edition to discover how it might meet their needs. Although it is impractical to list all the changes in this edition, a brief list that highlights some key changes, listed by the benefits they provide, may be useful. More Flexible Organization Applications of propositional logic are found in a new dedicated section, which briefly introduces logic circuits. Recurrence relations are now covered in Chapter 2. Expanded coverage of countability is now found in a dedicated section in Chapter 2.
Preface ix ■S anded coverage ofalgorithms(Chapter3)and number More second and third level heads have beenused to break sections into smaller coherent parts Tools for Easier Learning Difficult discussions and proofs have been marked with the famous Bourbaki"dangerous bend"symbol in the margin. New marginal notes make connections,add interesting notes,and provide advice to students. added explanations,in both proofs and exposition,make iteasier for Many new exercises,both routine and challenging,have been added,while many ex- isting exercises have been improved. Enhanced Coverage of Logic,Sets,and Proof The satisfiability problem is addressed in greater depth,with Sudoku modeled in terms of satisfiability Hilbert's Grand Hotel is used to help explain uncountability Proofs throughout the book have been made more accessible by adding steps and reasons behind these steps. A template for proofs by mathematical induction has been added The step that applies the inductive hypothesis in mathematical induction proof is now explicitly noted. Algorithms The pseudocode used in the book has been updated. Useful rules for big-O estimates of logarithms,powers,and exponential functions have been added. Number Theory and Cryptography eltionhipbetween the mod function and congrunceshas been explained more The sieve of Eratosthenes is now introduced earlier in the book Linear congruences and modular inverses are now covered in more detail Applications of number theory,including check digits and hash functions,are covered in great depth. ■A new section o hy integrates previous the notion Cryptographic protocols,including digital signatures and key sharing,are now covered
Preface ix Separate chapters now provide expanded coverage of algorithms (Chapter 3) and number theory and cryptography (Chapter 4). More second and third level heads have been used to break sections into smaller coherent parts. Tools for Easier Learning Difficult discussions and proofs have been marked with the famous Bourbaki “dangerous bend” symbol in the margin. New marginal notes make connections, add interesting notes, and provide advice to students. More details and added explanations, in both proofs and exposition, make it easier for students to read the book. Many new exercises, both routine and challenging, have been added, while many existing exercises have been improved. Enhanced Coverage of Logic, Sets, and Proof The satisfiability problem is addressed in greater depth, with Sudoku modeled in terms of satisfiability. Hilbert’s Grand Hotel is used to help explain uncountability. Proofs throughout the book have been made more accessible by adding steps and reasons behind these steps. A template for proofs by mathematical induction has been added. The step that applies the inductive hypothesis in mathematical induction proof is now explicitly noted. Algorithms The pseudocode used in the book has been updated. Explicit coverage of algorithmic paradigms, including brute force, greedy algorithms, and dynamic programing, is now provided. Useful rules for big-O estimates of logarithms, powers, and exponential functions have been added. Number Theory and Cryptography Expanded coverage allows instructors to include just a little or a lot of number theory in their courses. The relationship between the mod function and congruences has been explained more fully. The sieve of Eratosthenes is now introduced earlier in the book. Linear congruences and modular inverses are now covered in more detail. Applications of number theory, including check digits and hash functions, are covered in great depth. A new section on cryptography integrates previous coverage, and the notion of a cryptosystem has been introduced. Cryptographic protocols, including digital signatures and key sharing, are now covered.