This concise text offers an introduction to discrete mathematics for undergraduate students in computer science and mathematics. Mathematics educators consider it vital that their students be exposed to a course in discrete methods that introduces them to combinatorial mathematics and to algebraic and logical structures focusing on the interplay between computer science and mathematics. The present volume emphasizes combinatorics, graph theory with applications to some stand network optimization problems, and algorithms to solve these problems.
Chapters 0–3 cover fundamental operations involving sets and the principle of mathematical induction, and standard combinatorial topics: basic counting principles, permutations, combinations, the inclusion-exclusion principle, generating functions, recurrence relations, and an introduction to the analysis of algorithms. Applications are emphasized wherever possible and more than 200 exercises at the ends of these chapters help students test their grasp of the material.
Chapters 4 and 5 survey graphs and digraphs, including their connectedness properties, applications of graph coloring, and more, with stress on applications to coding and other related problems. Two important problems in network optimization ? the minimal spanning tree problem and the shortest distance problem ? are covered in the last two chapters. A very brief nontechnical exposition of the theory of computational complexity and NP-completeness is outlined in the appendix.
Author(s): V. K. Balakrishnan
Series: Dover Books on Computer Science
Publisher: Dover Publications
Year: 2010
Language: English
Pages: 251
Balakrishnan V. K . Introductory Discrete Mathematics (Dover Books on Computer Science)(DP,2010) ......Page 4
Copyright ......Page 5
Contents ......Page 7
Preface xiii ......Page 12
0.1 Introduction to Set Theory 1......Page 14
0.2 Functions and Relations 7......Page 20
0.3 Inductive Proofs and Recursive Definitions 17......Page 30
0.4 The Language of Logic 22......Page 35
0.5 Notes and References 25......Page 38
0.6 Exercises 26......Page 39
1.1 Two Basic Counting Rules 35......Page 48
1.2 Permutations 38......Page 51
1.3 Combinations 42......Page 55
1.4 More on Permutations and Combinations 48......Page 61
1.5 The Pigeonhole Principle 53......Page 66
1.6 The Inclusion-Exclusion Principle 59......Page 72
1.7 Summary of Results in Combinatorics 69......Page 82
1.8 Notes and References 71......Page 84
1.9 Exercises 72......Page 85
2.1 Introduction 80......Page 93
2.2 Ordinary Generating Functions 83......Page 96
2.3 Exponential Generating Functions 86......Page 99
2.5 Exercises 90......Page 103
3.1 Introduction 94......Page 107
3.2 Homogeneous Recurrence Relations 97......Page 110
3.3 Inhomogeneous Recurrence Relations 102......Page 115
3.4 Recurrence Relations and Generating Functions 105......Page 118
3.5 Analysis of Algorithms 108......Page 121
3.7 Exercises 116......Page 129
4.1 Introduction 120......Page 133
4.2 Adjacency Matrices and Incidence Matrices 125......Page 138
4.3 Joining in Graphs 129......Page 142
4.4 Reaching in Digraphs 132......Page 145
4.5 Testing Connectedness 133......Page 146
4.7 Notes and References 135......Page 148
4.8 Exercises 136......Page 149
5.1 Eulerian Paths and Eulerian Circuits 140......Page 153
5.2 Coding and de Bruijn Digraphs 144......Page 157
5.3 Hamiltonian Paths and Hamiltonian Cycles 149......Page 162
5.4 Applications of Hamiltonian Cycles 153......Page 166
5.5 Vertex Coloring and Planarity of Graphs 155......Page 168
5.6 Notes and References 161......Page 174
5.7 Exercises 162......Page 175
6.1 Definitions and Properties 164......Page 177
6.2 Spanning Trees 167......Page 180
6.3 Binary Trees 170......Page 183
6.4 Notes and References 177......Page 190
6.5 Exercises 178......Page 191
7.1 More on Spanning Trees 180......Page 193
7.2 Kruskal’s Greedy Algorithm 184......Page 197
7.3 Prim’s Greedy Algorithm 187......Page 200
7.6 Exercises 193......Page 206
8.1 Introduction 196......Page 209
8.2 Dijkstra’s Algorithm 197......Page 210
8.3 Floyd-Warshall Algorithm 202......Page 215
8.4 Comparison of the Two Algorithms 204......Page 217
8.6 Exercises 205......Page 218
A.l Problems and Their Instances 207......Page 220
A.2 The Size of an Instance 208......Page 221
A.4 Complexity of an Algorithm 209......Page 222
A.5 The “Big Oh’’ or the O(-) Notation\t210......Page 223
A.6 Easy Problems and Difficult Problems 211......Page 224
A.7 The Class P and the Class NP 212......Page 225
A.8 Polynomial Transformations and NP-Completeness 214......Page 227
A.9 Coping with Hard Problems 217......Page 230
Bibliography 219......Page 232
Answers to Selected Exercises 224......Page 237
Index 231......Page 244
cover......Page 1
