Discrete Mathematics with Graph Theory

by Goodaire, Edgar G.; Parmenter, Michael M.

• ISBN13: 9780131679955
• ISBN10: 0131679953
• Edition: 3rd
• Format: Hardcover
• Copyright: 2005-06-24
• Publisher: Savvas Learning Company

Summary

Far more "user friendly" than the vast majority of similar books, this volume is truly written with the unsophisticated reader in mind. The pace is leisurely, but the authors are rigorous and maintain a serious attitude towards theorem proving throughout.Emphasizes "Active Reading" throughout, a skill vital to success in learning how to write proofs. Offers two sections on probability (2.4 and 2.5). Moves material on depth-first search, which previously comprised an entire (very short) chapter, to an earlier chapter where it fits more naturally. Rewrites section on RNA chains to include a new (and easier) algorithm for the recovery of an RNA chain from its complete enzyme digest. Provides true/false questions (with all answers in the back of the book) in every section. Features an appendix on matrices. A useful reference for mathematics enthusiasts who want to learn how to write proofs.

Table of Contents

Preface	xi
To the Student	xv
Suggested Lecture Schedule	xix
Yes, There Are Proofs!	1	(18)
Compound Statements	2	(8)
Proofs in Mathematics	10	(9)
Review Exercises	17	(2)
Logic	19	(19)
Truth Tables	19	(4)
The Algebra of Propositions	23	(7)
Logical Arguments	30	(8)
Review Exercises	36	(2)
Sets and Relations	38	(34)
Sets	38	(5)
Operations on Sets	43	(8)
Binary Relations	51	(6)
Equivalence Relations	57	(7)
Partial Orders	64	(8)
Review Exercises	70	(2)
Functions	72	(26)
Basic Terminology	72	(8)
Inverses and Composition	80	(8)
One-to-One Correspondence and the Cardinality of a Set	88	(10)
Review Exercises	96	(2)
The Integers	98	(49)
The Division Algorithm	98	(7)
Divisibility and the Euclidean Algorithm	105	(9)
Prime Numbers	114	(11)
Congruence	125	(10)
Applications of Congruence	135	(12)
Review Exercises	145	(2)
Induction and Recursion	147	(37)
Mathematical Induction	147	(13)
Recursively Defined Sequences	160	(10)
Solving Recurrence Relations; The Characteristic Polynomial	170	(6)
Solving Recurrence Relations; Generating Functions	176	(8)
Review Exercises	182	(2)
Principles of Counting	184	(21)
The Principle of Inclusion-Exclusion	184	(8)
The Addition and Multiplication Rules	192	(7)
The Pigeonhole Principle	199	(6)
Review Exercises	204	(1)
Permutations and Combinations	205	(42)
Permutations	205	(5)
Combinations	210	(6)
Elementary Probability	216	(8)
Probability Theory	224	(7)
Repetitions	231	(5)
Derangements	236	(3)
The Binomial Theorem	239	(8)
Review Exercises	245	(2)
Algorithms	247	(34)
What Is an Algorithm?	247	(6)
Complexity	253	(12)
Searching and Sorting	265	(11)
Enumeration of Permutations and Combinations	276	(5)
Review Exercises	280	(1)
Graphs	281	(23)
A Gentle Introduction	281	(7)
Definitions and Basic Properties	288	(8)
Isomorphism	296	(8)
Review Exercises	301	(3)
Paths and Circuits	304	(35)
Eulerian Circuits	304	(7)
Hamiltonian Cycles	311	(8)
The Adjacency Matrix	319	(7)
Shortest Path Algorithms	326	(13)
Review Exercises	336	(3)
Applications of Paths and Circuits	339	(31)
The Chinese Postman Problem	339	(5)
Digraphs	344	(8)
RNA Chains	352	(4)
Tournaments	356	(5)
Scheduling Problems	361	(9)
Review Exercises	367	(3)
Trees	370	(41)
Trees and their Properties	370	(9)
Spanning Trees	379	(5)
Minimum Spanning Tree Algorithms	384	(9)
Acyclic Digraphs and Bellman's Algorithm	393	(5)
Depth-First Search	398	(5)
The One-Way Street Problem	403	(8)
Review Exercises	409	(2)
Planar Graphs and Colorings	411	(27)
Planar Graphs	411	(8)
Coloring Graphs	419	(8)
Circuit Testing and Facilities Design	427	(11)
Review Exercises	435	(3)
The Max Flow---Min Cut Theorem	438
Flows and Cuts	438	(7)
Constructing Maximal Flows	445	(5)
Applications	450	(4)
Matchings	454
Review Exercises	460
Appendix	1	(1)
Solutions to True/False Questions and Selected Exercises	1	(1)
Glossary	1	(1)
Index	1