Computational Discrete Mathematics
Combinatorics and Graph Theory with
Mathematica
SRIRAM PEMMARAJU STEVEN SKIENA
The University of Iowa SUNY at Stony Brook
CAMBRIDGE
UNIVERSITY PRESS
Table of Contents
Preface ix
• About Combinatorica • What's Between the Covers • Why Mathematica? • Acknowledgments • Caveat • Dedication
Chapter 1. Combinatorica: An Explorer's Guide
1.1 Combinatorial Objects: Permutations, Subsets, Partitions 3
• Permutations and Subsets • Partitions, Compositions, and Young Tableaux
1.2 Graph Theory and Algorithms 10
• Representing Graphs • Drawing Graphs • Generating Graphs • Properties of Graphs • Algorithmic Graph Theory
1.3 Combinatorica Conversion Guide 32
• The Main Differences • Functions Whose Usage Has Changed
1.4 An Overview of Mathematica 41
• The Structure of Functions • Mathematical Operations • List Manipulation • Iteration • Ten Little n-Sums • Conditionals
• Compiling Mathematica Code
Chapter 2. Permutations and Combinations
2.1 Generating Permutations 55
• Lexicographically Ordered Permutations • Ranking and Unranking Permutations • Random Permutations • Minimum
Change Permutations
2.2 Inversions and Inversion Vectors 69
• Inversion Vectors • Counting Inversions • The Index of a Permutation • Runs and Eulerian Numbers
2.3 Combinations 76
• Subsets via Binary Representation • Gray Codes • Lexicographically Ordered Subsets • Generatingfc-Subsets• Strings
2.4 Exercises 89
• Thought Exercises • Programming Exercises • Experimental Exercises
Chapter 3. Algebraic Combinatorics
3.1 The Cycle Structure of Permutations 93
• Odd and Even Permutations • Types of Permutations • Hiding Cycles • Counting Cycles
3.2 Special Classes of Permutations 104
• Involutions • Derangements
3.3 Polya Theory 109
• Permutation Groups • Group Action • Equivalence Classes and Orbits • Cycle Index of Permutation Groups
• Applying P61ya's Theorem
3.4 Exercises 131
• Thought Exercises • Programming Exercises • Experimental Exercises
vi Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica
Chapter 4. Partitions, Compositions, and Young Tableaux
4.1 Integer Partitions 135
• Generating Partitions • Generating Functions and Partitions • Ferrers Diagrams • Random Partitions
4.2 Compositions 146
• Random Compositions • Generating Compositions
4.3 Set Partitions 149
• Generating Set Partitions • Stirling and Bell Numbers • Ranking, Unranking, and Random Set Partitions • Set
Partitions and Restricted Growth Functions
4.4 Young Tableaux 162
• Insertion and Deletion • Permutations and Pairs of Tableaux • Generating Young Tableaux • Counting Tableaux by
Shape • Random Tableaux • Longest Increasing Subsequences
4.5 Exercises 173
• Thought Exercises • Programming Exercises • Experimental Exercises
Chapter 5. Graph Representation
5.1 Data Structures for Graphs 179
• The Internal Representation • Edge Lists • Adjacency Lists • Adjacency Matrices • Incidence Matrices
5.2 Modifying Graphs 192
• Additions, Deletions, and Changes • Setting Graph Options
5.3 Classifying Graphs 198
5.4 Displaying Graphs 200
• The Vertex and Edge Options • Inherited Options • A Hierarchy of Options • Highlighting and Animation
5.5 Basic Graph Embeddings 213
• Circular Embeddings • Ranked Embeddings • Radial Embeddings • Rooted Embeddings
5.6 Improving Embeddings 219
• Translating, Dilating, and Rotating Graphs • Shaking Graphs • Spring Embeddings
5.7 Storing and Editing Graphs 224
5.8 Exercises 226
• Thought Exercises • Programming Exercises • Experimental Exercises
Chapter 6. Generating Graphs
6.1 Building Graphs from Other Graphs 231
• Contracting Vertices • Inducing and Permuting Subgraphs • Unions and Intersections • Sums and Differences • Joins
of Graphs • Products of Graphs • Line Graphs
6.2 Regular Structures 244
• Complete Graphs • Circulant Graphs • Complete fc-Partite Graphs • Cycles, Stars, and Wheels • Grid Graphs
• Interconnection Networks
Table of Contents vii
6.3 Trees 258
• Labeled Trees • Complete Trees
6.4 Random Graphs 262
• Constructing Random Graphs • Realizing Degree Sequences
6.5 Relations and Functional Graphs 269
• Graphs from Relations • Functional Graphs
6.6 Exercises 273
• Thought Exercises • Programming Exercises • Experimental Exercises
Chapter 7. Properties of Graphs
7.1 Graph Traversals 277
• Breadth-First Search • Depth-First Search
7.2 Connectivity 283
• Connected Components • Strong and Weak Connectivity • Orienting Graphs • Biconnected Components • k-
Connectivity • Harary Graphs
7.3 Cycles in Graphs 294
• Acyclic Graphs • Girth • Eulerian Cycles • Hamiltonian Cycles and Paths • Traveling Salesman Tours
7.4 Graph Coloring 306
• Bipartite Graphs • Chromatic Polynomials • Finding a Vertex Coloring • Edge Colorings
7.5 Cliques, Vertex Covers, and Independent Sets 316
• Maximum Clique • Minimum Vertex Cover • Maximum Independent Set
7.6 Exercises 319
• Thought Exercises • Programming Exercises • Experimental Exercises
Chapter 8. Algorithmic Graph Theory
8.1 Shortest Paths 323
• Single-Source Shortest Paths • All-Pairs Shortest Paths • Applications of All-Pairs Shortest Paths • Number of Paths
8.2 Minimum Spanning Trees 335
• Union-Find • Kruskal's Algorithm • Counting Spanning Trees
8.3 Network Flow 340
8.4 Matching 343
• Maximal Matching • Bipartite Matching • Weighted Bipartite Matching and Vertex Cover • Stable Marriages
8.5 Partial Orders 352
• Topological Sorting • Transitive Closure and Reduction • Hasse Diagrams • Dilworth's Theorem
8.6 Graph Isomorphism 363
• Finding Isomorphisms • Tree Isomorphism • Self-Complementary Graphs
vffi Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica
8.7 Planar Graphs 370
• Testing Planarity
8.8 Exercises 372
• Thought Exercises • Programming Exercises • Experimental Exercises
Appendix 375
Reference Guide 376
Bibliography 447
Index 459
