Applied Combinatorics

Chapter 1: Elements of Graph Theory

• • 1.1 Graph Models
• • 1.2 Isomorphism
• • 1.3 Edge Counting
• • 1.4 Planar Graphs
• • 1.5 Summary and References
• • Supplementary Exercises

Chapter 2: Covering Circuits and Graph Coloring

• • 2.1 Euler Cycles
• • 2.2 Hamilton Circuits
• • 2.3 Graph Coloring
• • 2.4 Coloring Theorems
• • 2.5 Summary and References
• • Supplement: Graph Model for Instant Insanity
• • Supplement Exercises

Chapter 3: Trees and Searching

• • 3.1 Properties of Trees
• • 3.2 Search Trees and Spanning Trees
• • 3.3 The Traveling Salesperson Problem
• • 3.4 Tree Analysis of Sorting Algorithms
• • 3.5 Summary and References

Chapter 4: Network Algorithms

• • 4.1 Shortest Paths
• • 4.2 Minimum Spanning Trees
• • 4.3 Network Flows
• • 4.4 Algorithmic Matching
• • 4.5 The Transportation Problem
• • 4.6 Summary and References

Chapter 5: General Counting Methods for Arrangements and Selections

• • 5.1 Two Basic Counting Principles
• • 5.2 Simple Arrangements and Selections
• • 5.3 Arrangements and Selections with Repetitions
• • 5.4 Distributions
• • 5.5 Binomial Identities
• • 5.6 Summary and References
• • Supplement: Selected Solutions to Problems in Chapter 5

Chapter 6: Generating Functions

• • 6.1 Generating Function Models
• • 6.2 Calculating Coefficients of Generating Functions
• • 6.3 Partitions
• • 6.4 Exponential Generating Functions
• • 6.5 A Summation Method
• • 6.6 Summary and References

Chapter 7: Recurrence Relations

• • 7.1 Recurrence Relation Models
• • 7.2 Divide-and-Conquer Relations
• • 7.3 Solution of Linear Recurrence Relations
• • 7.4 Solution of Inhomogeneous Recurrence Relations
• • 7.5 Solutions with Generating Functions
• • 7.6 Summary and References

Chapter 8: Inclusion–Exclusion

• • 8.1 Counting with Venn Diagrams
• • 8.2 Inclusion–Exclusion Formula
• • 8.3 Restricted Positions and Rook Polynomials
• • 8.4 Summary and Reference

Chapter 9: Polya’s Enumeration Formula

• • 9.1 Equivalence and Symmetry Groups
• • 9.2 Burnside’s Theorem
• • 9.3 The Cycle Index
• • 9.4 Polya’s Formula
• • 9.5 Summary and References

Chapter 10: Games with Graphs

• • 10.1 Progressively Finite Games
• • 10.2 Nim-Type Games
• • 10.3 Summary and References