Applied Combinatorics
3rd Edition
Published on 25. July 2024
Book
Hardback
600 pages
978-1-032-74352-3 (ISBN)
Description
The original goal in writing this book was to introduce the reader to the tools of combinatorics from an applied point of view. This third edition of Applied Combinatorics was substantially rewritten. There are many new exercises. Additionally, references throughout the book have been updated both in terms of new editions of previously referenced works, as well as with references to recently published books and articles. As the first edition appeared decades prior, the diction in the exposition has been updated and is more contemporary.
The book continues to be based on the authors' philosophy the best way to learn mathematics is through problem solving. Combinatorics can be a wonderful mechanism for introducing students to proofs. The authors treat proofs as rather informal while many of the harder proofs in the book are optional.
In this new edition, many new examples and exercises appear, as well as an overall updating of the exposition for more contemporary diction.
The book is divided into four parts.The first part introduces the basic tools of combinatorics and their applications. The remaining three parts are organizedaroundthe three basic problems of combinatorics: thecountingproblem,theexistenceproblem,andtheoptimizationproblem.Then Part IV ends with a discussion of optimizationproblemsforgraphsandnetworks.
Entire sections focus on applications as switching functions, the use of enzymes to uncover unknown RNA chains, searching and sorting problems of information retrieval, construction of error-correcting codes, counting of chemical compounds, calculation of power in voting situations, and uses of Fibonacci numbers. There are entire sections on applications of recurrences involving convolutions, applications of Eulerian chains, and applications of generating functions.
Most of the book is written for a first course on the topic at the undergraduate level. At a fast pace, there is more than enough material for a challenging graduate course. This book first appeared when courses on combinatorics were rare. It is one of the classics that, through its use, helped to establish a viable course in many mathematics departments throughout the world. It remains a useful tool for instructors and students alike.
The book continues to be based on the authors' philosophy the best way to learn mathematics is through problem solving. Combinatorics can be a wonderful mechanism for introducing students to proofs. The authors treat proofs as rather informal while many of the harder proofs in the book are optional.
In this new edition, many new examples and exercises appear, as well as an overall updating of the exposition for more contemporary diction.
The book is divided into four parts.The first part introduces the basic tools of combinatorics and their applications. The remaining three parts are organizedaroundthe three basic problems of combinatorics: thecountingproblem,theexistenceproblem,andtheoptimizationproblem.Then Part IV ends with a discussion of optimizationproblemsforgraphsandnetworks.
Entire sections focus on applications as switching functions, the use of enzymes to uncover unknown RNA chains, searching and sorting problems of information retrieval, construction of error-correcting codes, counting of chemical compounds, calculation of power in voting situations, and uses of Fibonacci numbers. There are entire sections on applications of recurrences involving convolutions, applications of Eulerian chains, and applications of generating functions.
Most of the book is written for a first course on the topic at the undergraduate level. At a fast pace, there is more than enough material for a challenging graduate course. This book first appeared when courses on combinatorics were rare. It is one of the classics that, through its use, helped to establish a viable course in many mathematics departments throughout the world. It remains a useful tool for instructors and students alike.
More details
Series
Edition
3rd edition
Language
English
Place of publication
United Kingdom
Publishing group
Taylor & Francis Ltd
Target group
College/higher education
Undergraduate Advanced
Illustrations
525 s/w Abbildungen, 525 s/w Photographien bzw. Rasterbilder
525 Halftones, black and white; 525 Illustrations, black and white
Dimensions
Height: 254 mm
Width: 178 mm
ISBN-13
978-1-032-74352-3 (9781032743523)
Copyright in bibliographic data is held by Nielsen Book Services Limited or its licensors: all rights reserved.
Schweitzer Classification
Persons
Fred S. Roberts is Professor of Mathematics and Director of DIMACS at Rutgers University.
Barry Tesman is Professor of Mathematics at Dickinson College.
Barry Tesman is Professor of Mathematics at Dickinson College.
Content
Preface
Notation
1 What Is Combinatorics?
1.1 The Three Problems of Combinatorics
1.2 The History and Applications of Combinatorics
References for Chapter 1
PART I The Basic Tools of Combinatorics
2 Basic Counting Rules
2.1 The Product Rule
2.2 The Sum Rule
2.3 Permutations
2.4 Complexity of Computation
2.5 r-Permutations
2.6 Subsets
2.7 r-Combinations
2.8 Probability
2.9 Sampling with Replacement
2.10 Occupancy Problems
2.10.1 The Types of Occupancy Problems
2.10.2 Case 1: Distinguishable Balls and Distinguishable Cells
2.10.3 Case 2: Indistinguishable Balls and Distinguishable Cells
2.10.4 Case 3: Distinguishable Balls and Indistinguishable Cells
2.10.5 Case 4: Indistinguishable Balls and Indistinguishable Cells
2.10.6 Examples
2.11 Multinomial Coefficients
2.11.1 Occupancy Problems with a Specified Distribution
2.11.2 Permutations with Classes of Indistinguishable Objects
2.12 Complete Digest by Enzymes
2.13 Permutations with Classes of Indistinguishable Objects Revisited
2.14 The Binomial Expansion
2.15 Power in Simple Games
2.15.1 Examples of Simple Games
2.15.2 The Shapley-Shubik Power Index
2.15.3 The U.N. Security Council
2.15.4 Bicameral Legislatures
2.15.5 Cost Allocation
2.15.6 Characteristic Functions
2.16 Generating Permutations and Combinations
2.16.1 An Algorithm for Generating Permutations
2.16.2 An Algorithm for Generating Subsets of Sets
2.16.3 An Algorithm for Generating Combinations
2.17 Inversion Distance Between Permutations and the Study of Mutations
2.18 Good Algorithms
2.18.1 Asymptotic Analysis
2.18.2 NP-Complete Problems
2.19 Pigeonhole Principle and Its Generalizations
2.19.1 The Simplest Version of the Pigeonhole Principle
2.19.2 Generalizations and Applications of the Pigeonhole Principle
2.19.3 Ramsey Numbers
Additional Exercises for Chapter 2
References for Chapter 2
3 Introduction to Graph Theory
3.1 Fundamental Concepts
3.1.1 Some Examples
3.1.2 Definition of Digraph and Graph
3.1.3 Labeled Digraphs and the Isomorphism Problem
3.2 Connectedness
3.2.1 Reaching in Digraphs
3.2.2 Joining in Graphs
3.2.3 Strongly Connected Digraphs and Connected Graphs
3.2.4 Subgraphs
3.2.5 Connected Components
3.3 Graph Coloring and Its Applications
3.3.1 Some Applications
3.3.2 Planar Graphs
3.3.3 Calculating the Chromatic Number
3.3.4 2-Colorable Graphs
3.3.5 Graph-Coloring Variants
3.4 Chromatic Polynomials
3.4.1 Definitions and Examples
3.4.2 Reduction Theorems
3.4.3 Properties of Chromatic Polynomials
3.5 Trees
3.5.1 Definition of a Tree and Examples
3.5.2 Properties of Trees
3.5.3 Proof of Theorem 3.15
3.5.4 Spanning Trees
3.5.5 Proof of Theorem 3.16 and a Related Result
3.5.6 Chemical Bonds and the Number of Trees
3.5.7 Phylogenetic Tree Reconstruction
3.6 Applications of Rooted Trees to Searching, Sorting, and
Phylogeny Reconstruction
3.6.1 Definitions
3.6.2 Search Trees
3.6.3 Proof of Theorem 3.24
3.6.4 Sorting
3.6.5 The Perfect Phylogeny Problem
3.7 Representing a Graph in the Computer
3.8 Ramsey Numbers Revisited
References for Chapter 3
4 Relations
4.1 Relations
4.1.1 Binary Relations
4.1.2 Properties of Relations/Patterns in Digraphs
4.2 Order Relations and Their Variants
4.2.1 Defining the Concept of Order Relation
4.2.2 The Diagram of an Order Relation
4.2.3 Linear Orders
4.2.4 Weak Orders
4.2.5 Stable Marriages
4.3 Linear Extensions of Partial Orders
4.3.1 Linear Extensions and Dimension
4.3.2 Chains and Antichains
4.3.3 Interval Orders
4.4 Lattices and Boolean Algebras
4.4.1 Lattices
4.4.2 Boolean Algebras
References for Chapter 4
PART II The Counting Problem
5 Generating Functions and Their Applications
5.1 Examples of Generating Functions
5.1.1 Power Series
5.1.2 Generating Functions
5.2 Operating on Generating Functions
5.3 Applications to Counting
5.3.1 Sampling Problems
5.3.2 A Comment on Occupancy Problems
5.4 The Binomial Theorem
5.5 Exponential Generating Functions and Generating Functions for Permutations
5.5.1 Definition of Exponential Generating Function
5.5.2 Applications to Counting Permutations
5.5.3 Distributions of Distinguishable Balls into Indistinguishable
Cells
5.6 Probability Generating Functions
5.7 The Coleman and Banzhaf Power Indices
References for Chapter 5
6 Recurrence Relations
6.1 Some Examples
6.1.1 Some Simple Recurrences
6.1.2 Fibonacci Numbers and Their Applications
6.1.3 Derangements
6.1.4 Recurrences Involving More than One Sequence
6.2 The Method of Characteristic Roots
6.2.1 The Case of Distinct Roots
6.2.2 Computation of the kth Fibonacci Number
6.2.3 The Case of Multiple Roots
6.3 Solving Recurrences Using Generating Functions
6.3.1 The Method
6.3.2 Derangements
6.3.3 Simultaneous Equations for Generating Functions
6.4 Some Recurrences Involving Convolutions
6.4.1 The Number of Simple, Ordered, Rooted Trees
6.4.2 The Ways to Multiply a Sequence of Numbers in a
Computer
6.4.3 Secondary Structure in RNA
6.4.4 Organic Compounds Built Up from Benzene Rings
References for Chapter 6
7 The Principle of Inclusion and Exclusion
7.1 The Principle and Some of Its Applications
7.1.1 Some Simple Examples
7.1.2 Proof of Theorem 6.1
7.1.3 Prime Numbers, Cryptography, and Sieves
7.1.4 The Probabilistic Case
7.1.5 The Occupancy Problem with Distinguishable Balls and
Cells
7.1.6 Chromatic Polynomials
7.1.7 Derangements
7.1.8 Counting Combinations
7.1.9 Rook Polynomials
7.2 The Number of Objects Having Exactly m Properties
7.2.1 The Main Result and Its Applications
7.2.2 Proofs of Theorems 7.4 and 7.5
References for Chapter 7
8 The Po?lya Theory of Counting
8.1 Equivalence Relations
8.1.1 Distinct Configurations and Databases
8.1.2 Definition of Equivalence Relations
8.1.3 Equivalence Classes
8.2 Permutation Groups
8.2.1 Definition of a Permutation Group
8.2.2 The Equivalence Relation Induced by a Permutation Group
8.2.3 Automorphisms of Graphs
8.3 Burnside's Lemma
8.3.1 Statement of Burnside's Lemma
8.3.2 Proof of Burnside's Lemma
8.4 Distinct Colorings
8.4.1 Definition of a Coloring
8.4.2 Equivalent Colorings
8.4.3 Graph Colorings Equivalent under Automorphisms
8.4.4 The Case of Switching Functions
8.5 The Cycle Index
8.5.1 Permutations as Products of Cycles
8.5.2 A Special Case of P?olya's Theorem
8.5.3 Graph Colorings Equivalent under Automorphisms Revisited
8.5.4 The Case of Switching Functions
8.5.5 The Cycle Index of a Permutation Group
8.5.6 Proof of Theorem 8.6
8.6 P?olya's Theorem
8.6.1 The Inventory of Colorings
8.6.2 Computing the Pattern Inventory
8.6.3 The Case of Switching Functions
8.6.4 Proof of P?olya's Theorem
References for Chapter 8
PART III The Existence Problem
9 Combinatorial Designs
9.1 Block Designs
9.2 Latin Squares
9.2.1 Some Examples
9.2.2 Orthogonal Latin Squares
9.2.3 Existence Results for Orthogonal Families
9.2.4 Proof of Theorem 9.3
9.2.5 Orthogonal Arrays with Applications to Cryptography
9.3 Finite Fields and Families of Latin Squares
9.3.1 Modular Arithmetic
9.3.2 Modular Arithmetic and the RSA Cryptosystem
9.3.3 The Finite Fields GF(pk)
9.3.4 Construction of a Complete Orthogonal Family of n x n Latin Squares if n Is a Power of a Prime
9.3.5 Justification of the Construction of a Complete Orthogonal Family if n = pk
9.4 Balanced Incomplete Block Designs
9.4.1 (b, v, r, k, ?)-Designs
9.4.2 Necessary Conditions for the Existence of
(b, v, r, k, ?)-Designs
9.4.3 Proof of Fisher's Inequality
9.4.4 Resolvable Designs
9.4.5 Steiner Triple Systems
9.4.6 Symmetric Balanced Incomplete Block Designs
9.4.7 Building New (b, v, r, k, ?)-Designs from Existing Ones
9.4.8 Group Testing and Its Applications
9.4.9 Steiner Systems and the National Lottery
9.5 Finite Projective Planes
9.5.1 Basic Properties
9.5.2 Projective Planes, Latin Squares, and (v, k, ?)-Designs
References for Chapter 9
10 Coding Theory
10.1 Information Transmission
10.2 Encoding and Decoding
10.3 Error-Correcting Codes
10.3.1
Error Correction and Hamming Distance
10.3.2
The Hamming Bound
10.3.3
The Probability of Error
10.3.4
Consensus Decoding and Its Connection to Finding Patterns
in Molecular Sequences
10.4
Linear
Codes
10.4.1
Generator Matrices
10.4.2
Error Correction Using Linear Codes
10.4.3
Hamming Codes
10.5 The Use of Block Designs to Find Error-Correcting Codes
10.5.1
HadamardCodes
10.5.2
ConstructingHadamardDesigns
10.5.3
The Richest (n, d)-Codes
10.5.4
SomeApplications
References
forChapter10
11 Existence Problems in Graph Theory
11.1 Depth-First Search: A Test for Connectedness
11.1.1 Depth-First Search
11.1.2 The Computational Complexity of Depth-First Search
11.1.3 A Formal Statement of the Algorithm
11.1.4 Testing for Connectedness of Truly Massive Graphs
11.2 The One-Way Street Problem
11.2.1 Robbins' Theorem
11.2.2 A Depth-First Search Algorithm
11.2.3 Efficient One-Way Street Assignments
11.2.4 Efficient One-Way Street Assignments for Grids
11.2.5 Annular Cities and Communications in Interconnection Networks
11.3 Eulerian Chains and Paths
11.3.1 The K?onigsberg Bridge Problem
11.3.2 An Algorithm for Finding an Eulerian Closed Chain
11.3.3 Further Results about Eulerian Chains and Paths
11.4 Applications of Eulerian Chains and Paths
11.4.1 The "Chinese Postman" Problem
11.4.2 Street Sweeping
11.4.3 Finding Unknown RNA/DNA Chains
11.4.4 A Coding Application
11.4.5 De Bruijn Sequences and Telecommunications
11.5 Hamiltonian Chains and Paths
11.5.1 Definitions
11.5.2 Sufficient Conditions for the Existence of a Hamiltonian
Circuit in a Graph
11.5.3 Sufficient Conditions for the Existence of a Hamiltonian Cycle
in a Digraph
11.6 Applications of Hamiltonian Chains and Paths
11.6.1
Tournaments
11.6.2
TopologicalSorting
11.6.3
SchedulingProblems inOperationsResearch
11.6.4
Facilities Design
11.6.5
Sequencing by Hybridization
References
forChapter11
PART IV Combinatorial Optimization
12 Matching and Covering
12.1 Some Matching Problems
12.2 Some Existence Results: Bipartite Matching and Systems of Distinct Representatives
12.2.1 Bipartite Matching
12.2.2 Systems of Distinct Representatives
12.3 The Existence of Perfect Matchings for Arbitrary Graphs
12.4 Maximum Matchings and Minimum Coverings
12.4.1 Vertex Coverings
12.4.2 Edge Coverings
12.5 Finding a Maximum Matching
12.5.1 M -Augmenting Chains
12.5.2 Proof of Theorem 12.7
12.5.3 An Algorithm for Finding a Maximum Matching
12.6 Matching as Many Elements of X as Possible
12.7 Maximum-Weight Matching
12.7.1 The "Chinese Postman" Problem Revisited
12.7.2 An Algorithm for the Optimal Assignment Problem
(Maximum-Weight Matching)
12.8 Stable Matchings
12.8.1 Gale-Shapley Algorithm
12.8.2 Numbers of Stable Matchings
12.8.3 Structure of Stable Matchings
12.8.4 Stable Marriage Extensions
References for Chapter 12
13 Optimization Problems for Graphs and Networks
13.1 Minimum Spanning Trees
13.1.1 Kruskal's Algorithm
13.1.2 Proof of Theorem 13.1
13.1.3 Prim's Algorithm
13.2 The Shortest Route Problem
13.2.1 The Problem
13.2.2 Dijkstra's Algorithm
13.2.3 Applications to Scheduling Problems
13.3 Network Flows
13.3.1 The Maximum-Flow Problem
13.3.2 Cuts
13.3.3 A Faulty Max-Flow Algorithm
13.3.4 Augmenting Chains
13.3.5 The Max-Flow Algorithm
13.3.6 A Labeling Procedure for Finding Augmenting Chains
13.3.7 Complexity of the Max-Flow Algorithm
13.3.8 Matching Revisited
13.3.9 Menger's Theorems
13.4 Minimum-Cost Flow Problems
13.4.1 Some Examples
References for Chapter 13
Author Index
Subject Index
Notation
1 What Is Combinatorics?
1.1 The Three Problems of Combinatorics
1.2 The History and Applications of Combinatorics
References for Chapter 1
PART I The Basic Tools of Combinatorics
2 Basic Counting Rules
2.1 The Product Rule
2.2 The Sum Rule
2.3 Permutations
2.4 Complexity of Computation
2.5 r-Permutations
2.6 Subsets
2.7 r-Combinations
2.8 Probability
2.9 Sampling with Replacement
2.10 Occupancy Problems
2.10.1 The Types of Occupancy Problems
2.10.2 Case 1: Distinguishable Balls and Distinguishable Cells
2.10.3 Case 2: Indistinguishable Balls and Distinguishable Cells
2.10.4 Case 3: Distinguishable Balls and Indistinguishable Cells
2.10.5 Case 4: Indistinguishable Balls and Indistinguishable Cells
2.10.6 Examples
2.11 Multinomial Coefficients
2.11.1 Occupancy Problems with a Specified Distribution
2.11.2 Permutations with Classes of Indistinguishable Objects
2.12 Complete Digest by Enzymes
2.13 Permutations with Classes of Indistinguishable Objects Revisited
2.14 The Binomial Expansion
2.15 Power in Simple Games
2.15.1 Examples of Simple Games
2.15.2 The Shapley-Shubik Power Index
2.15.3 The U.N. Security Council
2.15.4 Bicameral Legislatures
2.15.5 Cost Allocation
2.15.6 Characteristic Functions
2.16 Generating Permutations and Combinations
2.16.1 An Algorithm for Generating Permutations
2.16.2 An Algorithm for Generating Subsets of Sets
2.16.3 An Algorithm for Generating Combinations
2.17 Inversion Distance Between Permutations and the Study of Mutations
2.18 Good Algorithms
2.18.1 Asymptotic Analysis
2.18.2 NP-Complete Problems
2.19 Pigeonhole Principle and Its Generalizations
2.19.1 The Simplest Version of the Pigeonhole Principle
2.19.2 Generalizations and Applications of the Pigeonhole Principle
2.19.3 Ramsey Numbers
Additional Exercises for Chapter 2
References for Chapter 2
3 Introduction to Graph Theory
3.1 Fundamental Concepts
3.1.1 Some Examples
3.1.2 Definition of Digraph and Graph
3.1.3 Labeled Digraphs and the Isomorphism Problem
3.2 Connectedness
3.2.1 Reaching in Digraphs
3.2.2 Joining in Graphs
3.2.3 Strongly Connected Digraphs and Connected Graphs
3.2.4 Subgraphs
3.2.5 Connected Components
3.3 Graph Coloring and Its Applications
3.3.1 Some Applications
3.3.2 Planar Graphs
3.3.3 Calculating the Chromatic Number
3.3.4 2-Colorable Graphs
3.3.5 Graph-Coloring Variants
3.4 Chromatic Polynomials
3.4.1 Definitions and Examples
3.4.2 Reduction Theorems
3.4.3 Properties of Chromatic Polynomials
3.5 Trees
3.5.1 Definition of a Tree and Examples
3.5.2 Properties of Trees
3.5.3 Proof of Theorem 3.15
3.5.4 Spanning Trees
3.5.5 Proof of Theorem 3.16 and a Related Result
3.5.6 Chemical Bonds and the Number of Trees
3.5.7 Phylogenetic Tree Reconstruction
3.6 Applications of Rooted Trees to Searching, Sorting, and
Phylogeny Reconstruction
3.6.1 Definitions
3.6.2 Search Trees
3.6.3 Proof of Theorem 3.24
3.6.4 Sorting
3.6.5 The Perfect Phylogeny Problem
3.7 Representing a Graph in the Computer
3.8 Ramsey Numbers Revisited
References for Chapter 3
4 Relations
4.1 Relations
4.1.1 Binary Relations
4.1.2 Properties of Relations/Patterns in Digraphs
4.2 Order Relations and Their Variants
4.2.1 Defining the Concept of Order Relation
4.2.2 The Diagram of an Order Relation
4.2.3 Linear Orders
4.2.4 Weak Orders
4.2.5 Stable Marriages
4.3 Linear Extensions of Partial Orders
4.3.1 Linear Extensions and Dimension
4.3.2 Chains and Antichains
4.3.3 Interval Orders
4.4 Lattices and Boolean Algebras
4.4.1 Lattices
4.4.2 Boolean Algebras
References for Chapter 4
PART II The Counting Problem
5 Generating Functions and Their Applications
5.1 Examples of Generating Functions
5.1.1 Power Series
5.1.2 Generating Functions
5.2 Operating on Generating Functions
5.3 Applications to Counting
5.3.1 Sampling Problems
5.3.2 A Comment on Occupancy Problems
5.4 The Binomial Theorem
5.5 Exponential Generating Functions and Generating Functions for Permutations
5.5.1 Definition of Exponential Generating Function
5.5.2 Applications to Counting Permutations
5.5.3 Distributions of Distinguishable Balls into Indistinguishable
Cells
5.6 Probability Generating Functions
5.7 The Coleman and Banzhaf Power Indices
References for Chapter 5
6 Recurrence Relations
6.1 Some Examples
6.1.1 Some Simple Recurrences
6.1.2 Fibonacci Numbers and Their Applications
6.1.3 Derangements
6.1.4 Recurrences Involving More than One Sequence
6.2 The Method of Characteristic Roots
6.2.1 The Case of Distinct Roots
6.2.2 Computation of the kth Fibonacci Number
6.2.3 The Case of Multiple Roots
6.3 Solving Recurrences Using Generating Functions
6.3.1 The Method
6.3.2 Derangements
6.3.3 Simultaneous Equations for Generating Functions
6.4 Some Recurrences Involving Convolutions
6.4.1 The Number of Simple, Ordered, Rooted Trees
6.4.2 The Ways to Multiply a Sequence of Numbers in a
Computer
6.4.3 Secondary Structure in RNA
6.4.4 Organic Compounds Built Up from Benzene Rings
References for Chapter 6
7 The Principle of Inclusion and Exclusion
7.1 The Principle and Some of Its Applications
7.1.1 Some Simple Examples
7.1.2 Proof of Theorem 6.1
7.1.3 Prime Numbers, Cryptography, and Sieves
7.1.4 The Probabilistic Case
7.1.5 The Occupancy Problem with Distinguishable Balls and
Cells
7.1.6 Chromatic Polynomials
7.1.7 Derangements
7.1.8 Counting Combinations
7.1.9 Rook Polynomials
7.2 The Number of Objects Having Exactly m Properties
7.2.1 The Main Result and Its Applications
7.2.2 Proofs of Theorems 7.4 and 7.5
References for Chapter 7
8 The Po?lya Theory of Counting
8.1 Equivalence Relations
8.1.1 Distinct Configurations and Databases
8.1.2 Definition of Equivalence Relations
8.1.3 Equivalence Classes
8.2 Permutation Groups
8.2.1 Definition of a Permutation Group
8.2.2 The Equivalence Relation Induced by a Permutation Group
8.2.3 Automorphisms of Graphs
8.3 Burnside's Lemma
8.3.1 Statement of Burnside's Lemma
8.3.2 Proof of Burnside's Lemma
8.4 Distinct Colorings
8.4.1 Definition of a Coloring
8.4.2 Equivalent Colorings
8.4.3 Graph Colorings Equivalent under Automorphisms
8.4.4 The Case of Switching Functions
8.5 The Cycle Index
8.5.1 Permutations as Products of Cycles
8.5.2 A Special Case of P?olya's Theorem
8.5.3 Graph Colorings Equivalent under Automorphisms Revisited
8.5.4 The Case of Switching Functions
8.5.5 The Cycle Index of a Permutation Group
8.5.6 Proof of Theorem 8.6
8.6 P?olya's Theorem
8.6.1 The Inventory of Colorings
8.6.2 Computing the Pattern Inventory
8.6.3 The Case of Switching Functions
8.6.4 Proof of P?olya's Theorem
References for Chapter 8
PART III The Existence Problem
9 Combinatorial Designs
9.1 Block Designs
9.2 Latin Squares
9.2.1 Some Examples
9.2.2 Orthogonal Latin Squares
9.2.3 Existence Results for Orthogonal Families
9.2.4 Proof of Theorem 9.3
9.2.5 Orthogonal Arrays with Applications to Cryptography
9.3 Finite Fields and Families of Latin Squares
9.3.1 Modular Arithmetic
9.3.2 Modular Arithmetic and the RSA Cryptosystem
9.3.3 The Finite Fields GF(pk)
9.3.4 Construction of a Complete Orthogonal Family of n x n Latin Squares if n Is a Power of a Prime
9.3.5 Justification of the Construction of a Complete Orthogonal Family if n = pk
9.4 Balanced Incomplete Block Designs
9.4.1 (b, v, r, k, ?)-Designs
9.4.2 Necessary Conditions for the Existence of
(b, v, r, k, ?)-Designs
9.4.3 Proof of Fisher's Inequality
9.4.4 Resolvable Designs
9.4.5 Steiner Triple Systems
9.4.6 Symmetric Balanced Incomplete Block Designs
9.4.7 Building New (b, v, r, k, ?)-Designs from Existing Ones
9.4.8 Group Testing and Its Applications
9.4.9 Steiner Systems and the National Lottery
9.5 Finite Projective Planes
9.5.1 Basic Properties
9.5.2 Projective Planes, Latin Squares, and (v, k, ?)-Designs
References for Chapter 9
10 Coding Theory
10.1 Information Transmission
10.2 Encoding and Decoding
10.3 Error-Correcting Codes
10.3.1
Error Correction and Hamming Distance
10.3.2
The Hamming Bound
10.3.3
The Probability of Error
10.3.4
Consensus Decoding and Its Connection to Finding Patterns
in Molecular Sequences
10.4
Linear
Codes
10.4.1
Generator Matrices
10.4.2
Error Correction Using Linear Codes
10.4.3
Hamming Codes
10.5 The Use of Block Designs to Find Error-Correcting Codes
10.5.1
HadamardCodes
10.5.2
ConstructingHadamardDesigns
10.5.3
The Richest (n, d)-Codes
10.5.4
SomeApplications
References
forChapter10
11 Existence Problems in Graph Theory
11.1 Depth-First Search: A Test for Connectedness
11.1.1 Depth-First Search
11.1.2 The Computational Complexity of Depth-First Search
11.1.3 A Formal Statement of the Algorithm
11.1.4 Testing for Connectedness of Truly Massive Graphs
11.2 The One-Way Street Problem
11.2.1 Robbins' Theorem
11.2.2 A Depth-First Search Algorithm
11.2.3 Efficient One-Way Street Assignments
11.2.4 Efficient One-Way Street Assignments for Grids
11.2.5 Annular Cities and Communications in Interconnection Networks
11.3 Eulerian Chains and Paths
11.3.1 The K?onigsberg Bridge Problem
11.3.2 An Algorithm for Finding an Eulerian Closed Chain
11.3.3 Further Results about Eulerian Chains and Paths
11.4 Applications of Eulerian Chains and Paths
11.4.1 The "Chinese Postman" Problem
11.4.2 Street Sweeping
11.4.3 Finding Unknown RNA/DNA Chains
11.4.4 A Coding Application
11.4.5 De Bruijn Sequences and Telecommunications
11.5 Hamiltonian Chains and Paths
11.5.1 Definitions
11.5.2 Sufficient Conditions for the Existence of a Hamiltonian
Circuit in a Graph
11.5.3 Sufficient Conditions for the Existence of a Hamiltonian Cycle
in a Digraph
11.6 Applications of Hamiltonian Chains and Paths
11.6.1
Tournaments
11.6.2
TopologicalSorting
11.6.3
SchedulingProblems inOperationsResearch
11.6.4
Facilities Design
11.6.5
Sequencing by Hybridization
References
forChapter11
PART IV Combinatorial Optimization
12 Matching and Covering
12.1 Some Matching Problems
12.2 Some Existence Results: Bipartite Matching and Systems of Distinct Representatives
12.2.1 Bipartite Matching
12.2.2 Systems of Distinct Representatives
12.3 The Existence of Perfect Matchings for Arbitrary Graphs
12.4 Maximum Matchings and Minimum Coverings
12.4.1 Vertex Coverings
12.4.2 Edge Coverings
12.5 Finding a Maximum Matching
12.5.1 M -Augmenting Chains
12.5.2 Proof of Theorem 12.7
12.5.3 An Algorithm for Finding a Maximum Matching
12.6 Matching as Many Elements of X as Possible
12.7 Maximum-Weight Matching
12.7.1 The "Chinese Postman" Problem Revisited
12.7.2 An Algorithm for the Optimal Assignment Problem
(Maximum-Weight Matching)
12.8 Stable Matchings
12.8.1 Gale-Shapley Algorithm
12.8.2 Numbers of Stable Matchings
12.8.3 Structure of Stable Matchings
12.8.4 Stable Marriage Extensions
References for Chapter 12
13 Optimization Problems for Graphs and Networks
13.1 Minimum Spanning Trees
13.1.1 Kruskal's Algorithm
13.1.2 Proof of Theorem 13.1
13.1.3 Prim's Algorithm
13.2 The Shortest Route Problem
13.2.1 The Problem
13.2.2 Dijkstra's Algorithm
13.2.3 Applications to Scheduling Problems
13.3 Network Flows
13.3.1 The Maximum-Flow Problem
13.3.2 Cuts
13.3.3 A Faulty Max-Flow Algorithm
13.3.4 Augmenting Chains
13.3.5 The Max-Flow Algorithm
13.3.6 A Labeling Procedure for Finding Augmenting Chains
13.3.7 Complexity of the Max-Flow Algorithm
13.3.8 Matching Revisited
13.3.9 Menger's Theorems
13.4 Minimum-Cost Flow Problems
13.4.1 Some Examples
References for Chapter 13
Author Index
Subject Index