# Discrete Mathematics: Graph Algorithms, Algebraic Structures, Coding Theory and Cryptography PDF by R. Balakrishnan and Sriraman Sridharan

## 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

This book is US\$10
To get free sample pages OR Buy this book