Discrete Mathematics: Graph Algorithms, Algebraic Structures, Coding Theory and Cryptography
By R. Balakrishnan and Sriraman Sridharan
Contents:
List of Figures xiii
List of Tables xvii
Preface xix
Acknowledgment xxiii
Authors xxv
1 Graph Algorithms I 1
1.1 Representation of Graphs . . . . . . . . . . . . . . . . . . . . 1
1.2 Minimum Spanning Tree Algorithms . . . . . . . . . . . . . . 9
1.2.1 Prim’s minimum spanning tree algorithm . . . . . . . 11
1.2.2 Kruskal’s minimum spanning tree algorithm . . . . . . 19
1.2.3 Rooted ordered trees and traversal of trees . . . . . . 22
1.3 Shortest Path Algorithms . . . . . . . . . . . . . . . . . . . . 23
1.3.1 Single-source shortest path algorithm . . . . . . . . . 24
1.4 Dijkstra’s Algorithm for Negative Weighted Arcs . . . . . . . 33
1.5 All-Pairs Shortest Path Algorithm . . . . . . . . . . . . . . . 35
1.5.1 An application of Floyd’s algorithm . . . . . . . . . . 43
1.6 Transitive Closure of a Directed Graph . . . . . . . . . . . . 45
1.7 An O(n3) Transitive Closure Algorithm Due to Warshall . . 47
1.8 Navigation in Graphs . . . . . . . . . . . . . . . . . . . . . . 50
1.9 Applications of Depth-First Search . . . . . . . . . . . . . . . 55
1.9.1 Application 1: Finding connected components . . . . . 55
1.9.2 Application 2: Testing acyclic graph . . . . . . . . . . 56
1.9.3 Application 3: Finding biconnected components of a
connected multigraph . . . . . . . . . . . . . . . . . . 58
1.10 Depth-First Search for Directed Graphs . . . . . . . . . . . . 68
1.11 Applications of Depth-First Search for Directed Graphs . . . 70
1.11.1 Application 1: Finding the roots of a directed
graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1.11.2 Application 2: Testing if a digraph is without
circuits . . . . . . . . . . . . . . . . . . . . . . . . . . 72
1.11.3 Application 3: Topological sort . . . . . . . . . . . . . 72
1.11.3.1 An application of topological sort: PERT . . 76
1.11.4 Application 4: Strongly connected components
algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 79
1.12 Traveling Salesman Problem . . . . . . . . . . . . . . . . . . 90
1.12.1 Approximate algorithms for traveling salesman
problem . . . . . . . . . . . . . . . . . . . . . . . . . . 93
1.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
2 Graph Algorithms II 103
2.1 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . 103
2.2 Applications of bfs Algorithm . . . . . . . . . . . . . . . . . 107
2.3 Matchings in Graphs . . . . . . . . . . . . . . . . . . . . . . 113
2.3.1 An application: (k − 1)-regular subgraphs of k-regular
graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2.4 Matrices and Bipartite Graphs . . . . . . . . . . . . . . . . . 127
2.4.1 Personnel assignment problem or weighted matching
in a bipartite graph . . . . . . . . . . . . . . . . . . . 136
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
3 Algebraic Structures I (Matrices, Groups, Rings,
and Fields) 147
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.3 Operations on Matrices: Addition, Scalar Multiplication,
and Multiplication of Matrices . . . . . . . . . . . . . . . . . 147
3.3.1 Block multiplication of matrices . . . . . . . . . . . . 148
3.3.2 Transpose of a matrix . . . . . . . . . . . . . . . . . . 149
3.3.3 Inverse of a matrix . . . . . . . . . . . . . . . . . . . 149
3.3.4 Symmetric and skew-symmetric matrices . . . . . . . 150
3.3.5 Hermitian and skew-Hermitian matrices . . . . . . . . 150
3.3.6 Orthogonal and unitary matrices . . . . . . . . . . . . 151
3.3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . 151
3.4 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
3.4.1 Abelian and non-Abelian groups . . . . . . . . . . . . 152
3.4.2 Examples of Abelian groups . . . . . . . . . . . . . . . 154
3.4.3 Examples of non-Abelian groups . . . . . . . . . . . . 155
3.4.4 Group tables . . . . . . . . . . . . . . . . . . . . . . . 155
3.5 A Group of Congruent Transformations (Also called
Symmetries) . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
3.6 Another Group of Congruent Transformations . . . . . . . . 157
3.7 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
3.7.1 Examples of subgroups . . . . . . . . . . . . . . . . . . 158
3.7.2 Subgroup generated by a subset of a group . . . . . . 158
3.8 Cyclic Groups . . . . . . . . . . . . . . . . . . . . . . . . . . 159
3.8.1 Examples of cyclic groups . . . . . . . . . . . . . . . . 159
3.9 Lagrange’s Theorem for Finite Groups . . . . . . . . . . . . 163
3.10 Homomorphisms and Isomorphisms of Groups . . . . . . . . 166
3.11 Properties of Homomorphisms of Groups . . . . . . . . . . . 168
3.12 Automorphism of Groups . . . . . . . . . . . . . . . . . . . . 170
3.13 Normal Subgroups . . . . . . . . . . . . . . . . . . . . . . . . 171
3.14 Quotient Groups (or Factor Groups) . . . . . . . . . . . . . . 172
3.15 Basic Isomorphism Theorem for Groups . . . . . . . . . . . . 174
3.15.1 Examples of factor groups . . . . . . . . . . . . . . . . 175
3.16 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
3.17 Rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
3.17.1 Rings, definitions and examples . . . . . . . . . . . . . 178
3.17.1.1 Unity element of a ring . . . . . . . . . . . . 180
3.17.2 Units of a ring . . . . . . . . . . . . . . . . . . . . . . 180
3.17.2.1 Units of the ring Zn . . . . . . . . . . . . . . 180
3.17.2.2 Zero divisors . . . . . . . . . . . . . . . . . . 181
3.18 Integral Domains . . . . . . . . . . . . . . . . . . . . . . . . 181
3.19 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
3.20 Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
3.21 Principal Ideals . . . . . . . . . . . . . . . . . . . . . . . . . 184
3.22 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
3.22.1 Examples of fields . . . . . . . . . . . . . . . . . . . . 188
3.23 Characteristic of a Field . . . . . . . . . . . . . . . . . . . . 188
4 Algebraic Structures II (Vector Spaces and Finite Fields) 191
4.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 191
4.1.1 Examples of vector spaces . . . . . . . . . . . . . . . . 192
4.2 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.2.1 An example of a subspace . . . . . . . . . . . . . . . . 193
4.3 Spanning Sets . . . . . . . . . . . . . . . . . . . . . . . . . . 193
4.4 Linear Independence of Vectors . . . . . . . . . . . . . . . . 195
4.5 Bases of a Vector Space . . . . . . . . . . . . . . . . . . . . . 197
4.6 Dimension of a Vector Space . . . . . . . . . . . . . . . . . . 198
4.7 Solutions of Linear Equations and Rank of a Matrix . . . . . 201
4.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
4.9 Solutions of Linear Equations . . . . . . . . . . . . . . . . . 205
4.10 Solutions of Non-Homogeneous Linear Equations . . . . . . 206
4.11 LUP Decomposition . . . . . . . . . . . . . . . . . . . . . . . 208
4.11.1 Computing an LU decomposition . . . . . . . . . . . . 208
4.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
4.13 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
4.14 Factorization of Polynomials Over Finite Fields . . . . . . . 220
4.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
4.16 Mutually Orthogonal Latin Squares . . . . . . . . . . . . . . 223
5 Introduction to Coding Theory 225
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
5.2 Binary Symmetric Channels . . . . . . . . . . . . . . . . . . 226
5.3 Linear Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
5.4 Minimum Distance of a Code . . . . . . . . . . . . . . . . . 230
5.5 Hamming Codes . . . . . . . . . . . . . . . . . . . . . . . . 231
5.6 Standard Array Decoding . . . . . . . . . . . . . . . . . . . . 232
5.7 Sphere Packings . . . . . . . . . . . . . . . . . . . . . . . . . 235
5.8 Extended Codes . . . . . . . . . . . . . . . . . . . . . . . . . 236
5.9 Syndrome Decoding . . . . . . . . . . . . . . . . . . . . . . . 237
5.10 Error Detection . . . . . . . . . . . . . . . . . . . . . . . . . 238
5.11 Sphere Packing Bound or Hamming Bound . . . . . . . . . . 238
5.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
5.13 Cyclic Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
5.14 Dual Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
5.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
6 Cryptography 249
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
6.2 Some Classical Cryptosystems . . . . . . . . . . . . . . . . . 249
6.2.1 Caesar cryptosystem . . . . . . . . . . . . . . . . . . . 249
6.2.2 Affine cryptosystem . . . . . . . . . . . . . . . . . . . 250
6.2.3 Private key cryptosystems . . . . . . . . . . . . . . . . 251
6.2.4 Hacking an affine cryptosystem . . . . . . . . . . . . . 252
6.3 Encryption Using Matrices . . . . . . . . . . . . . . . . . . . 253
6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
6.5 Other Private Key Cryptosystems . . . . . . . . . . . . . . . 255
6.5.1 Vigenere cipher . . . . . . . . . . . . . . . . . . . . . . 255
6.5.2 The one-time pad . . . . . . . . . . . . . . . . . . . . 256
6.6 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . 256
6.6.1 Working of public key cryptosystems . . . . . . . . . . 257
6.6.1.1 Transmission of messages . . . . . . . . . . . 257
6.6.1.2 Digital signature . . . . . . . . . . . . . . . . 257
6.6.2 RSA public key cryptosystem . . . . . . . . . . . . . . 258
6.6.2.1 Description of RSA . . . . . . . . . . . . . . 258
6.6.3 The ElGamal public key cryptosystem . . . . . . . . . 260
6.6.4 Description of ElGamal system . . . . . . . . . . . . . 261
6.7 Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . 261
6.7.1 Non-trivial square roots (mod n) . . . . . . . . . . . . 261
6.7.2 Prime Number Theorem . . . . . . . . . . . . . . . . . 262
6.7.3 Pseudo-primality testing . . . . . . . . . . . . . . . . . 262
6.7.3.1 Base-2 Pseudo-prime test . . . . . . . . . . . 263
6.7.4 Miller-Rabin Algorithm . . . . . . . . . . . . . . . . . 263
6.7.5 Horner’s method to evaluate a polynomial . . . . . . . 263
6.7.6 Modular exponentiation algorithm based on repeated
squaring . . . . . . . . . . . . . . . . . . . . . . . . . . 265
6.8 The Agrawal-Kayal-Saxena (AKS) Primality Testing
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
6.8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 267
6.8.2 The basis of AKS algorithm . . . . . . . . . . . . . . . 267
6.8.3 Notation and preliminaries . . . . . . . . . . . . . . . 268
6.8.4 The AKS algorithm . . . . . . . . . . . . . . . . . . . 269
Appendix A: Answers to Chapter 1—Graph Algorithms I 279
Appendix B: Answers to Chapter 2—Graph Algorithms II 287
Appendix C: Answers to Chapter 3—Algebraic Structures I 289
Appendix D: Answers to Chapter 4—Algebraic Structures II 295
Appendix E: Answers to Chapter 5—Introduction
to Coding Theory 299
Appendix F: Answers to Chapter 6—Cryptography 303
Bibliography 307
Index 311