Für diesen Artikel ist leider kein Bild verfügbar.

Applied Combinatorics

Buch | Hardcover
600 Seiten
2024 | 3rd edition
Chapman & Hall/CRC (Verlag)
978-1-032-74352-3 (ISBN)
137,15 inkl. MwSt
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.

Fred S. Roberts is Professor of Mathematics and Director of DIMACS at Rutgers University. Barry Tesman is Professor of Mathematics at Dickinson College.

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

Erscheint lt. Verlag 25.7.2024
Reihe/Serie Discrete Mathematics and Its Applications
Zusatzinfo 525 Halftones, black and white; 525 Illustrations, black and white
Sprache englisch
Maße 178 x 254 mm
Themenwelt Mathematik / Informatik Mathematik Graphentheorie
ISBN-10 1-032-74352-2 / 1032743522
ISBN-13 978-1-032-74352-3 / 9781032743523
Zustand Neuware
Haben Sie eine Frage zum Produkt?
Mehr entdecken
aus dem Bereich
Numbers and Counting, Groups, Graphs, Orders and Lattices

von Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger …

Buch | Softcover (2023)
De Gruyter (Verlag)
64,95