Applied Combinatorics

Prelude xi

Part One Graph Theory 1

Chapter 1 Elements of Graph Theory 3

1.1 Graph Models 3

1.2 Isomorphism 14

1.3 Edge Counting 24

1.4 Planar Graphs 31

1.5 Summary and References 44

Supplementary Exercises 45

Chapter 2 Covering Circuits and Graph Coloring 49

2.1 Euler Cycles 49

2.2 Hamilton Circuits 56

2.3 Graph Coloring 68

2.4 Coloring Theorems 77

2.5 Summary and References 86

Supplement: Graph Model for Instant Insanity 87

Supplement Exercises 92

Chapter 3 Trees and Searching 93

3.1 Properties of Trees 93

3.2 Search Trees and Spanning Trees 103

3.3 The Traveling Salesperson Problem 113

3.4 Tree Analysis of Sorting Algorithms 121

3.5 Summary and References 125

Chapter 4 Network Algorithms 127

4.1 Shortest Paths 127

4.2 Minimum Spanning Trees 131

4.3 Network Flows 135

4.4 Algorithmic Matching 153

4.5 The Transportation Problem 164

4.6 Summary and References 174

Part Two Enumeration 177

Chapter 5 General Counting Methods for Arrangements and Selections 179

5.1 Two Basic Counting Principles 179

5.2 Simple Arrangements and Selections 189

5.3 Arrangements and Selections with Repetitions 206

5.4 Distributions 214

5.5 Binomial Identities 226

5.6 Summary and References 236

Supplement: Selected Solutions to Problems in Chapter 5 237

Chapter 6 Generating Functions 249

6.1 Generating Function Models 249

6.2 Calculating Coefficients of Generating Functions 256

6.3 Partitions 266

6.4 Exponential Generating Functions 271

6.5 A Summation Method 277

6.6 Summary and References 281

Chapter 7 Recurrence Relations 283

7.1 Recurrence Relation Models 283

7.2 Divide-and-Conquer Relations 296

7.3 Solution of Linear Recurrence Relations 300

7.4 Solution of Inhomogeneous Recurrence Relations 304

7.5 Solutions with Generating Functions 308

7.6 Summary and References 316

Chapter 8 Inclusion–Exclusion 319

8.1 Counting with Venn Diagrams 319

8.2 Inclusion–Exclusion Formula 328

8.3 Restricted Positions and Rook Polynomials 340

8.4 Summary and Reference 351

Part Three Additional Topics 353

Chapter 9 Polya’s Enumeration Formula 355

9.1 Equivalence and Symmetry Groups 355

9.2 Burnside’s Theorem 363

9.3 The Cycle Index 369

9.4 Polya’s Formula 375

9.5 Summary and References 382

Chapter 10 Games with Graphs 385

10.1 Progressively Finite Games 385

10.2 Nim-Type Games 393

10.3 Summary and References 400

Postlude 401

Appendix 415

A.1 Set Theory 415

A.2 Mathematical Induction 420

A.3 A Little Probability 423

A.4 The Pigeonhole Principle 427

A.5 Computational Complexity and NP-Completeness 430

Glossary of Counting and Graph Theory Terms 435

Bibliography 439

Solutions To Odd-Numbered Problems 441

Index 475