You are previewing Computational Discrete Mathematics.
O'Reilly logo
Computational Discrete Mathematics

Book Description

This book was first published in 2003. Combinatorica, an extension to the popular computer algebra system Mathematica, is the most comprehensive software available for teaching and research applications of discrete mathematics, particularly combinatorics and graph theory. This book is the definitive reference/user's guide to Combinatorica, with examples of all 450 Combinatorica functions in action, along with the associated mathematical and algorithmic theory. The authors cover classical and advanced topics on the most important combinatorial objects: permutations, subsets, partitions, and Young tableaux, as well as all important areas of graph theory: graph construction operations, invariants, embeddings, and algorithmic graph theory. In addition to being a research tool, Combinatorica makes discrete mathematics accessible in new and exciting ways to a wide variety of people, by encouraging computational experimentation and visualization. The book contains no formal proofs, but enough discussion to understand and appreciate all the algorithms and theorems it contains.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Contents
  6. Preface
    1. About Combinatorica
    2. What’s Between the Covers
    3. Why Mathematica?
    4. Acknowledgments
    5. Caveat
    6. Dedication
  7. Chapter 1: Combinatorica: An Explorer’s Guide
    1. 1.1 Combinatorial Objects: Permutations, Subsets, Partitions
      1. 1.1.1 Permutations and Subsets
      2. 1.1.2 Partitions, Compositions, and Young Tableaux
    2. 1.2 Graph Theory and Algorithms
      1. 1.2.1 Representing Graphs
      2. 1.2.2 Drawing Graphs
      3. 1.2.3 Generating Graphs
      4. 1.2.4 Properties of Graphs
      5. 1.2.5 Algorithmic Graph Theory
    3. 1.3 Combinatorica Conversion Guide
      1. 1.3.1 The Main Differences
      2. 1.3.2 Functions Whose Usage Has Changed
    4. 1.4 An Overview of Mathematica
      1. 1.4.1 The Structure of Functions
      2. 1.4.2 Mathematical Operations
      3. 1.4.3 List Manipulation
      4. 1.4.4 Iteration
      5. 1.4.5 Ten Little n-Sums
      6. 1.4.6 Conditionals
      7. 1.4.7 Compiling Mathematica Code
  8. Chapter 2: Permutations and Combinations
    1. 2.1 Generating Permutations
      1. 2.1.1 Lexicographically Ordered Permutations
      2. 2.1.2 Ranking and Unranking Permutations
      3. 2.1.3 Random Permutations
      4. 2.1.4 Minimum Change Permutations
    2. 2.2 Inversions and Inversion Vectors
      1. 2.2.1 Inversion Vectors
      2. 2.2.2 Counting Inversions
      3. 2.2.3 The Index of a Permutation
      4. 2.2.4 Runs and Eulerian Numbers
    3. 2.3 Combinations
      1. 2.3.1 Subsets via Binary Representation
      2. 2.3.2 Gray Codes
      3. 2.3.3 Lexicographically Ordered Subsets
      4. 2.3.4 Generating k-Subsets
      5. 2.3.5 Strings
    4. 2.4 Exercises
      1. 2.4.1 Thought Exercises
      2. 2.4.2 Programming Exercises
      3. 2.4.3 Experimental Exercises
  9. Chapter 3: Algebraic Combinatorics
    1. 3.1 The Cycle Structure of Permutations
      1. 3.1.1 Odd and Even Permutations
      2. 3.1.2 Types of Permutations
      3. 3.1.3 Hiding Cycles
      4. 3.1.4 Counting Cycles
    2. 3.2 Special Classes of Permutations
      1. 3.2.1 Involutions
      2. 3.2.2 Derangements
    3. 3.3 Pólya Theory
      1. 3.3.1 Permutation Groups
      2. 3.3.2 Group Action
      3. 3.3.3 Equivalence Classes and Orbits
      4. 3.3.4 Cycle Index of Permutation Groups
      5. 3.3.5 Applying Pólya’s Theorem
    4. 3.4 Exercises
      1. 3.4.1 Thought Exercises
      2. 3.4.2 Programming Exercises
      3. 3.4.3 Experimental Exercises
  10. Chapter 4: Partitions, Compositions, and Young Tableaux
    1. 4.1 Integer Partitions
      1. 4.1.1 Generating Partitions
      2. 4.1.2 Generating Functions and Partitions
      3. 4.1.3 Ferrers Diagrams
      4. 4.1.4 Random Partitions
    2. 4.2 Compositions
      1. 4.2.1 Random Compositions
      2. 4.2.2 Generating Compositions
    3. 4.3 Set Partitions
      1. 4.3.1 Generating Set Partitions
      2. 4.3.2 Stirling and Bell Numbers
      3. 4.3.3 Ranking, Unranking, and Random Set Partitions
      4. 4.3.4 Set Partitions and Restricted Growth Functions
    4. 4.4 Young Tableaux
      1. 4.4.1 Insertion and Deletion
      2. 4.4.2 Permutations and Pairs of Tableaux
      3. 4.4.3 Generating Young Tableaux
      4. 4.4.4 Counting Tableaux by Shape
      5. 4.4.5 Random Tableaux
      6. 4.4.6 Longest Increasing Subsequences
    5. 4.5 Exercises
      1. 4.5.1 Thought Exercises
      2. 4.5.2 Programming Exercises
      3. 4.5.3 Experimental Exercises
  11. Chapter 5: Graph Representation
    1. 5.1 Data Structures for Graphs
      1. 5.1.1 The Internal Representation
      2. 5.1.2 Edge Lists
      3. 5.1.3 Adjacency Lists
      4. 5.1.4 Adjacency Matrices
      5. 5.1.5 Incidence Matrices
    2. 5.2 Modifying Graphs
      1. 5.2.1 Additions, Deletions, and Changes
      2. 5.2.2 Setting Graph Options
    3. 5.3 Classifying Graphs
    4. 5.4 Displaying Graphs
      1. 5.4.1 The Vertex and Edge Options
      2. 5.4.2 Inherited Options
      3. 5.4.3 A Hierarchy of Options
      4. 5.4.4 Highlighting and Animation
    5. 5.5 Basic Graph Embeddings
      1. 5.5.1 Circular Embeddings
      2. 5.5.2 Ranked Embeddings
      3. 5.5.3 Radial Embeddings
      4. 5.5.4 Rooted Embeddings
    6. 5.6 Improving Embeddings
      1. 5.6.1 Translating, Dilating, and Rotating Graphs
      2. 5.6.2 Shaking Graphs
      3. 5.6.3 Spring Embeddings
    7. 5.7 Storing and Editing Graphs
    8. 5.8 Exercises
      1. 5.8.1 Thought Exercises
      2. 5.8.2 Programming Exercises
      3. 5.8.3 Experimental Exercises
  12. Chapter 6: Generating Graphs
    1. 6.1 Building Graphs from Other Graphs
      1. 6.1.1 Contracting Vertices
      2. 6.1.2 Inducing and Permuting Subgraphs
      3. 6.1.3 Unions and Intersections
      4. 6.1.4 Sums and Differences
      5. 6.1.5 Joins of Graphs
      6. 6.1.6 Products of Graphs
      7. 6.1.7 Line Graphs
    2. 6.2 Regular Structures
      1. 6.2.1 Complete Graphs
      2. 6.2.2 Circulant Graphs
      3. 6.2.3 Complete k-Partite Graphs
      4. 6.2.4 Cycles, Stars, and Wheels
      5. 6.2.5 Grid Graphs
      6. 6.2.6 Interconnection Networks
    3. 6.3 Trees
      1. 6.3.1 Labeled Trees
      2. 6.3.2 Complete Trees
    4. 6.4 Random Graphs
      1. 6.4.1 Constructing Random Graphs
      2. 6.4.2 Realizing Degree Sequences
    5. 6.5 Relations and Functional Graphs
      1. 6.5.1 Graphs from Relations
      2. 6.5.2 Functional Graphs
    6. 6.6 Exercises
      1. 6.6.1 Thought Exercises
      2. 6.6.2 Programming Exercises
      3. 6.6.3 Experimental Exercises
  13. Chapter 7: Properties of Graphs
    1. 7.1 Graph Traversals
      1. 7.1.1 Breadth-First Search
      2. 7.1.2 Depth-First Search
    2. 7.2 Connectivity
      1. 7.2.1 Connected Components
      2. 7.2.2 Strong and Weak Connectivity
      3. 7.2.3 Orienting Graphs
      4. 7.2.4 Biconnected Components
      5. 7.2.5 k- Connectivity
      6. 7.2.6 Harary Graphs
    3. 7.3 Cycles in Graphs
      1. 7.3.1 Acyclic Graphs
      2. 7.3.2 Girth
      3. 7.3.3 Eulerian Cycles
      4. 7.3.4 Hamiltonian Cycles and Paths
      5. 7.3.5 Traveling Salesman Tours
    4. 7.4 Graph Coloring
      1. 7.4.1 Bipartite Graphs
      2. 7.4.2 Chromatic Polynomials
      3. 7.4.3 Finding a Vertex Coloring
      4. 7.4.4 Edge Colorings
    5. 7.5 Cliques, Vertex Covers, and Independent Sets
      1. 7.5.1 Maximum Clique
      2. 7.5.2 Minimum Vertex Cover
      3. 7.5.3 Maximum Independent Set
    6. 7.6 Exercises
      1. 7.6.1 Thought Exercises
      2. 7.6.2 Programming Exercises
      3. 7.6.3 Experimental Exercises
  14. Chapter 8: Algorithmic Graph Theory
    1. 8.1 Shortest Paths
      1. 8.1.1 Single-Source Shortest Paths
      2. 8.1.2 All-Pairs Shortest Paths
      3. 8.1.3 Applications of All-Pairs Shortest Paths
      4. 8.1.4 Number of Paths
    2. 8.2 Minimum Spanning Trees
      1. 8.2.1 Union-Find
      2. 8.2.2 Kruskal’s Algorithm
      3. 8.2.3 Counting Spanning Trees
    3. 8.3 Network Flow
    4. 8.4 Matching
      1. 8.4.1 Maximal Matching
      2. 8.4.2 Bipartite Matching
      3. 8.4.3 Weighted Bipartite Matching and Vertex Cover
      4. 8.4.4 Stable Marriages
    5. 8.5 Partial Orders
      1. 8.5.1 Topological Sorting
      2. 8.5.2 Transitive Closure and Reduction
      3. 8.5.3 Hasse Diagrams
      4. 8.5.4 Dilworth’s Theorem
    6. 8.6 Graph Isomorphism
      1. 8.6.1 Finding Isomorphisms
      2. 8.6.2 Tree Isomorphism
      3. 8.6.3 Self-Complementary Graphs
    7. 8.7 Planar Graphs
      1. 8.7.1 Testing Planarity
    8. 8.8 Exercises
      1. 8.8.1 Thought Exercises
      2. 8.8.2 Programming Exercises
      3. 8.8.3 Experimental Exercises
  15. Appendix
    1. Reference Guide
  16. Bibliography
  17. Index