x Preface Graph Theory A structured introduction to graph theory applications has been added. More coverage has been devoted to the notion of social networks. ”6paaposhmeexdsRandnonaaeplcaioasreapBomr Matchings in bipartite graphs are now covered,including Hall's theorem and its proof. onnectedness has been Enrichment Material many biographies have been expanded and updated and new biographies of bellmar Bezout Bienyame,Cardano,Catalan,Cocks,Cook,Dirac,Hall,Hilbert,Ore,and Tao have been added. Historical information has been added throughout the text Numerous updates for latest discoveries have been made. Expanded Media Extensive effort has been devoted to producing valuable web resources for this book Extra examples in key parts of the text have been provided on companion website. s have been developed,with tools for using them to explore topies A new online ancillary,The Virtual Discrete Mathematics Tutor,available in fall 2012, will help students overcome problems learning discrete mathematics. A new homework delivery system available in fall 2012 will provide automated home. work for both numerical and conceptual exercises ■Student asse ssment modules are available for key concepts Powerpoint transparencies for instructor use have been developed. An extensive collection of external web links is provided. Features of the Book ACCESSIBILITY This text has proved to be easily read and understood by beginning students mathematical prerequisites all th s ne where calculus is referred to are explicitly noted Most students should easily understand the pseudocode used in the text to express algorithms,regardless of whether they have formally studied programming languages.There is no formal computer science prerequisite. Each chapter begins at an easily understood and accessible level.Once basic mathematica
x Preface Graph Theory A structured introduction to graph theory applications has been added. More coverage has been devoted to the notion of social networks. Applications to the biological sciences and motivating applications for graph isomorphism and planarity have been added. Matchings in bipartite graphs are now covered, including Hall’s theorem and its proof. Coverage of vertex connectivity, edge connectivity, and n-connectedness has been added, providing more insight into the connectedness of graphs. Enrichment Material Many biographies have been expanded and updated, and new biographies of Bellman, Bézout Bienyamé, Cardano, Catalan, Cocks, Cook, Dirac, Hall, Hilbert, Ore, and Tao have been added. Historical information has been added throughout the text. Numerous updates for latest discoveries have been made. Expanded Media Extensive effort has been devoted to producing valuable web resources for this book. Extra examples in key parts of the text have been provided on companion website. Interactive algorithms have been developed, with tools for using them to explore topics and for classroom use. A new online ancillary, The Virtual Discrete Mathematics Tutor, available in fall 2012, will help students overcome problems learning discrete mathematics. A new homework delivery system, available in fall 2012, will provide automated homework for both numerical and conceptual exercises. Student assessment modules are available for key concepts. Powerpoint transparencies for instructor use have been developed. A supplement Exploring Discrete Mathematics has been developed, providing extensive support for using MapleTM or MathematicaTM in conjunction with the book. An extensive collection of external web links is provided. Features of the Book ACCESSIBILITY This text has proved to be easily read and understood by beginning students. There are no mathematical prerequisites beyond college algebra for almost all the content of the text. Students needing extra help will find tools on the companion website for bringing their mathematical maturity up to the level of the text. The few places in the book where calculus is referred to are explicitly noted. Most students should easily understand the pseudocode used in the text to express algorithms, regardless of whether they have formally studied programming languages. There is no formal computer science prerequisite. Each chapter begins at an easily understood and accessible level. Once basic mathematical concepts have been carefully developed, more difficult material and applications to other areas of study are presented.
Preface xi FLEXIBILITY refully designed for fexible approximately the same length,and each section is divided into subsections that form natural blocks of material for teaching.Instructors can easily pace their lectures using these blocks. WRITING STYLE The writing style in this book is direct and pragmatic.Precise mathe MATHEMATICAL RIGOR AND PRECISION All definiti th ons and t orems in this te needed in mathematics proofs are motivated and develon their re al carefully justified.The axioms used in proofs and the basic properties that follow from them are explicitly described in an appendix,giving students a clear idea of what they can assume in a proof.Recursive definitions are explained and used extensively. WORKED EXAMPLES Over 800examples are used to illustrate concepts,relate different applic cluded in thi strate ty of disc ide riety of areas.including computer science.data networking.psychology,chemistry,engineering linguistics,biology,business,and the Internet. ALGORITHMS Results in discrete mathematics are often expressed in terms of algo- rithms,hence,key algorithms are introduced in each chapter of the book.These algorithms als mentary leve The beek n the t briefbiographies of 83 mathematicians and com entists are ineluded as foot notes.These biographies include information about the lives,careers,and accomplishments of these important contributors to discrete mathematics and images,when available,are displayed In addition,numerous historical footnotes are included that supplement the historical in- refrectngtxthave een made to keep thebook p-dateby KEY TERMS AND RESULTS A list ofk only the mo ortant that students sults foll in the chapter. EXERCISES There are over 4000 exercises in the text with many different tynes of questions posed.There is an ample supply of straightforward exercises that develop basic skills. a large number of intermediate exercises,and many challenging exercises.Exercises are stated clearly and unambiguously,and all are carefully graded for level of difficulty.Exercise sets t develop new concepts not covered in the text,enabling students scover new than those that are much more challenginghose solutions require calculus are explicitly noted.Exercises that develop results used in the text are clearly identified with the right pointing hand symbol Answers or outlined solutions to all odd
Preface xi FLEXIBILITY This text has been carefully designed for flexible use. The dependence of chapters on previous material has been minimized. Each chapter is divided into sections of approximately the same length, and each section is divided into subsections that form natural blocks of material for teaching. Instructors can easily pace their lectures using these blocks. WRITING STYLE The writing style in this book is direct and pragmatic. Precise mathematical language is used without excessive formalism and abstraction. Care has been taken to balance the mix of notation and words in mathematical statements. MATHEMATICAL RIGOR AND PRECISION All definitions and theorems in this text are stated extremely carefully so that students will appreciate the precision of language and rigor needed in mathematics. Proofs are motivated and developed slowly; their steps are all carefully justified. The axioms used in proofs and the basic properties that follow from them are explicitly described in an appendix, giving students a clear idea of what they can assume in a proof. Recursive definitions are explained and used extensively. WORKED EXAMPLES Over 800 examples are used to illustrate concepts, relate different topics, and introduce applications. In most examples, a question is first posed, then its solution is presented with the appropriate amount of detail. APPLICATIONS The applications included in this text demonstrate the utility of discrete mathematics in the solution of real-world problems. This text includes applications to a wide variety of areas, including computer science, data networking, psychology, chemistry, engineering, linguistics, biology, business, and the Internet. ALGORITHMS Results in discrete mathematics are often expressed in terms of algorithms; hence, key algorithms are introduced in each chapter of the book. These algorithms are expressed in words and in an easily understood form of structured pseudocode, which is described and specified in Appendix 3. The computational complexity of the algorithms in the text is also analyzed at an elementary level. HISTORICAL INFORMATION The background of many topics is succinctly described in the text. Brief biographies of 83 mathematicians and computer scientists are included as footnotes. These biographies include information about the lives, careers, and accomplishments of these important contributors to discrete mathematics and images, when available, are displayed. In addition, numerous historical footnotes are included that supplement the historical information in the main body of the text. Efforts have been made to keep the book up-to-date by reflecting the latest discoveries. KEY TERMS AND RESULTS A list of key terms and results follows each chapter. The key terms include only the most important that students should learn, and not every term defined in the chapter. EXERCISES There are over 4000 exercises in the text, with many different types of questions posed. There is an ample supply of straightforward exercises that develop basic skills, a large number of intermediate exercises, and many challenging exercises. Exercises are stated clearly and unambiguously, and all are carefully graded for level of difficulty. Exercise sets contain special discussions that develop new concepts not covered in the text, enabling students to discover new ideas through their own work. Exercises that are somewhat more difficult than average are marked with a single star ∗; those that are much more challenging are marked with two stars ∗∗. Exercises whose solutions require calculus are explicitly noted. Exercises that develop results used in the text are clearly identified with the right pointing hand symbol . Answers or outlined solutions to all odd-
xii Preface numbered exercises are provided at the back of the text.The solutions include proofs in which most of the steps are clearly spelled out. REVIEW QUESTIONS set of review questions is provided at theend ofeach chapte r To ng answers SUPPLEMENTARY EXERCISE SETS Each chapter is followed by a rich and varied set of supplementary exercises.These exercises are generally more difficult than those in the exercise sets following the sections.The supplementary exercises reinforce the concepts of the chapter and integrate different topics more effectively COMPUTER PROJECTS at pu ts The tely 150 iects tie what stud a mathematical and a programming point of view,are marked with a star,and those that are extremely challenging are marked with two stars. A set of compu a ons 00 chapter.Ihese (approxi atical ong Putatio acka Many of these exercises give students the opportunity to uncover new facts and ideas through computation (Some of these exercises are discussed in the exploring discrete mathematics companion workbooks available online.) WRITING PROJECTS Each chapter is fo wed by a set of wr u and n to new topics and ideas.All are des ed to exnose students to ideas not covered in denth in the text.These projects tie mathematical concepts together with the writing process and help expose students to possible areas for future study.(Suggested references for these projects can be found online or in the printed Stdent's Solutions Guide.) There are thre app ndixes to the text.The firs uces axioms fo tivend logarithn funct are pro naterial used heavily in the course.The third specifies the pseudocode used to describe algorithms in this text. SUGGESTED READINGS A list of suggested readings for the overall book and for each chapter is provided after the appendices.These suggested readings include books at or below many years ago,w e been put the pubi w year How to Use This Book This text has been carefully written and constructed to support discrete mathematics courses at several levels and with differing foci.The following table identifies the core and optional course in other sections covere
xii Preface numbered exercises are provided at the back of the text. The solutions include proofs in which most of the steps are clearly spelled out. REVIEW QUESTIONS A set of review questions is provided at the end of each chapter. These questions are designed to help students focus their study on the most important concepts and techniques of that chapter. To answer these questions students need to write long answers, rather than just perform calculations or give short replies. SUPPLEMENTARY EXERCISE SETS Each chapter is followed by a rich and varied set of supplementary exercises. These exercises are generally more difficult than those in the exercise sets following the sections. The supplementary exercises reinforce the concepts of the chapter and integrate different topics more effectively. COMPUTER PROJECTS Each chapter is followed by a set of computer projects. The approximately 150 computer projects tie together what students may have learned in computing and in discrete mathematics. Computer projects that are more difficult than average, from both a mathematical and a programming point of view, are marked with a star, and those that are extremely challenging are marked with two stars. COMPUTATIONS AND EXPLORATIONS A set of computations and explorations is included at the conclusion of each chapter. These exercises (approximately 120 in total) are designed to be completed using existing software tools, such as programs that students or instructors have written or mathematical computation packages such as MapleTM or MathematicaTM. Many of these exercises give students the opportunity to uncover new facts and ideas through computation. (Some of these exercises are discussed in the Exploring Discrete Mathematics companion workbooks available online.) WRITING PROJECTS Each chapter is followed by a set of writing projects. To do these projects students need to consult the mathematical literature. Some of these projects are historical in nature and may involve looking up original sources. Others are designed to serve as gateways to new topics and ideas. All are designed to expose students to ideas not covered in depth in the text. These projects tie mathematical concepts together with the writing process and help expose students to possible areas for future study. (Suggested references for these projects can be found online or in the printed Student’s Solutions Guide.) APPENDIXES There are three appendixes to the text. The first introduces axioms for real numbers and the positive integers, and illustrates how facts are proved directly from these axioms. The second covers exponential and logarithmic functions, reviewing some basic material used heavily in the course. The third specifies the pseudocode used to describe algorithms in this text. SUGGESTED READINGS A list of suggested readings for the overall book and for each chapter is provided after the appendices. These suggested readings include books at or below the level of this text, more difficult books, expository articles, and articles in which discoveries in discrete mathematics were originally published. Some of these publications are classics, published many years ago, while others have been published in the last few years. How to Use This Book This text has been carefully written and constructed to support discrete mathematics courses at several levels and with differing foci. The following table identifies the core and optional sections. An introductory one-term course in discrete mathematics at the sophomore level can be based on the core sections of the text, with other sections covered at the discretion of the
Preface xii n include all the nnal math by covering some or all of the optional computer science sections.Instructors can find sample syllabi for a wide range of discrete mathematics courses and teaching suggestions for using each Chapter Core Optional CS Optional Math 2.5 3.1-3.3(as needed) 4 1-4 4 (as needed) 45.4.6 51-53 5.45.5 6 61-63 66 6.4,6.5 7. 1.4 .2,7.3 818 9.5 92 828486 10.1-10 11.1 112113 12 121-124 13 13.1-13.5 Instructors using this book can adjust the level of difficulty of their course by choosing either to cover or to omit the more challenging examples at the end of sections,as well as .cnallenging exercises.The chapter dependency chart shown here displays the stro dependencie udy ofa Resource Guide depen Chapter 12 Chapter 3* Chapter 4 Chapter 13 Chapter 5* hapter.7 Ancillaries STUDENTS SOLUTIONS GUIDE This student manua vailable contain sed and why it works For approaches are described to show that a problem can be solved in several different ways.Sug gested references for the writing projects found at the end of each chapter are also included in this volume.Also included are a guide to writing proofs and an extensive description of common
Preface xiii instructor. A two-term introductory course can include all the optional mathematics sections in addition to the core sections. A course with a strong computer science emphasis can be taught by covering some or all of the optional computer science sections. Instructors can find sample syllabi for a wide range of discrete mathematics courses and teaching suggestions for using each section of the text can be found in the Instructor’s Resource Guide available on the website for this book. Chapter Core Optional CS Optional Math 1 1.1–1.8 (as needed) 2 2.1–2.4, 2.6 (as needed) 2.5 3 3.1–3.3 (as needed) 4 4.1–4.4 (as needed) 4.5, 4.6 5 5.1–5.3 5.4, 5.5 6 6.1–6.3 6.6 6.4, 6.5 7 7.1 7.4 7.2, 7.3 8 8.1, 8.5 8.3 8.2, 8.4, 8.6 9 9.1, 9.3, 9.5 9.2 9.4, 9.6 10 10.1–10.5 10.6–10.8 11 11.1 11.2, 11.3 11.4, 11.5 12 12.1–12.4 13 13.1–13.5 Instructors using this book can adjust the level of difficulty of their course by choosing either to cover or to omit the more challenging examples at the end of sections, as well as the more challenging exercises. The chapter dependency chart shown here displays the strong dependencies. A star indicates that only relevant sections of the chapter are needed for study of a later chapter. Weak dependencies have been ignored. More details can be found in the Instructor Resource Guide. Chapter 9* Chapter 10* Chapter 11 Chapter 13 Chapter 12 Chapter 2* Chapter 7 Chapter 8 Chapter 6* Chapter 3* Chapter 1 Chapter 4* Chapter 5* Ancillaries STUDENT’S SOLUTIONS GUIDE This student manual, available separately, contains full solutions to all odd-numbered problems in the exercise sets. These solutions explain why a particular method is used and why it works. For some exercises, one or two other possible approaches are described to show that a problem can be solved in several different ways. Suggested references for the writing projects found at the end of each chapter are also included in this volume. Also included are a guide to writing proofs and an extensive description of common
xiv Preface mistakes students make in discrete mathematics,plus sample tests and a sample crib sheet for each chapter designed to help students prepare for exams. ISBN.10:0-07-735350-) SBN-13:978-0-07-735350-6 INSTRUCTOR'S RESOURCE GUIDE This manual,available on the website and in printed form by request for instructors.contains full solutions to even-numbered exercises in the text suggestions on how to teach the material in each chanter of the book are provided including the points to stress in each section and how to put the material into perspective.It also offers sample tests for each chapter and a test bank containing over 1500 exam qu uestions to ly,s vera 1SBN-10:0-07-735349-8 1SBN-13:978-0-07-735349-0) Acknowledgments d h ck a ons. lean-Claude Evard.and G gia Mede er for their technical re seventh edition and their"eagle eves."which have belped ensure the accuracy of this book I also appreciate the help provided by all those who have submitted comments via the website. I thank the reviewers of this seventh and the six previous editions.These reviewers have provided much helpful criticism and encouragement to me.I hope this edition lives up to their nigh expectations. Reviewers for the Seventh Edition Philip Barry of Minnesota.Minneapolis TJ.Duda Jerry lanni dia Commnity College ofFlorida Ravi Janardan Kirl Norliza Katuk Calumet-Hammond John Carter Herbert Enderton William Klost University of Toronto University of California,Los Angeles Narendra Chaudhari Namyang Technological University Allan Cochran Kim Factor Unirersity of arkansas Marguette University Jaro F MaChmp GcecePaicUnenin PetgCleRacUmcran Ronald Dotzel Ken Holladay Vladimir Logvinenko University of Missouri-S.Louis University of New Orleans De An-a Community College
xiv Preface mistakes students make in discrete mathematics, plus sample tests and a sample crib sheet for each chapter designed to help students prepare for exams. (ISBN-10: 0-07-735350-1) (ISBN-13: 978-0-07-735350-6) INSTRUCTOR’S RESOURCE GUIDE This manual, available on the website and in printed form by request for instructors, contains full solutions to even-numbered exercises in the text. Suggestions on how to teach the material in each chapter of the book are provided, including the points to stress in each section and how to put the material into perspective. It also offers sample tests for each chapter and a test bank containing over 1500 exam questions to choose from. Answers to all sample tests and test bank questions are included. Finally, several sample syllabi are presented for courses with differing emphases and student ability levels. (ISBN-10: 0-07-735349-8) (ISBN-13: 978-0-07-735349-0) Acknowledgments I would like to thank the many instructors and students at a variety of schools who have used this book and provided me with their valuable feedback and helpful suggestions. Their input has made this a much better book than it would have been otherwise. I especially want to thank Jerrold Grossman, Jean-Claude Evard, and Georgia Mederer for their technical reviews of the seventh edition and their “eagle eyes,” which have helped ensure the accuracy of this book. I also appreciate the help provided by all those who have submitted comments via the website. I thank the reviewers of this seventh and the six previous editions. These reviewers have provided much helpful criticism and encouragement to me. I hope this edition lives up to their high expectations. Reviewers for the Seventh Edition Philip Barry University of Minnesota, Minneapolis Miklos Bona University of Florida Kirby Brown Queens College John Carter University of Toronto Narendra Chaudhari Nanyang Technological University Allan Cochran University of Arkansas Daniel Cunningham Buffalo State College George Davis Georgia State University Andrzej Derdzinski The Ohio State University Ronald Dotzel University of Missouri-St. Louis T.J. Duda Columbus State Community College Bruce Elenbogen University of Michigan, Dearborn Norma Elias Purdue University, Calumet-Hammond Herbert Enderton University of California, Los Angeles Anthony Evans Wright State University Kim Factor Marquette University Margaret Fleck University of Illinois, Champaign Peter Gillespie Fayetteville State University Johannes Hattingh Georgia State University Ken Holladay University of New Orleans Jerry Ianni LaGuardia Community College Ravi Janardan University of Minnesota, Minneapolis Norliza Katuk University of Utara Malaysia William Klostermeyer University of North Florida Przemo Kranz University of Mississippi Jaromy Kuhl University of West Florida Loredana Lanzani University of Arkansas, Fayetteville Steven Leonhardi Winona State University Xu Liutong Beijing University of Posts and Telecommunications Vladimir Logvinenko De Anza Community College