Computational discrete mathematics : combinatorics and graph theory with Mathematica / Sriram Pemmaraju, Steven Skiena.

Format:

Book

Author/Creator:

Pemmaraju, Sriram V., 1966-

Contributor:

Skiena, Steven S.

Class of 1924 Book Fund.

Language:

English

Subjects (All):

Combinatorica (Computer file).

Combinatorial analysis--Data processing.

Combinatorial analysis.

Graph theory--Data processing.

Graph theory.

Physical Description:

xiii, 480 pages : illustrations ; 25 cm

Place of Publication:

Cambridge, U.K. ; New York : Cambridge University Press, 2003.

Summary:

Combinatorica, an extension to the popular computer algebra system Mathematica, is the most comprehensive software available for educational 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, by encouraging computational experimentation and visualization. The book is suitable for self-study and as a primary or supplementary text book for discrete mathematics courses.

Contents:

About Combinatorica

What's Between the Covers

Why Mathematica?

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

Generating k-Subsets

Strings

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 Polya's Theorem

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 Paris of Tableaux

Generating Young Tableaux

Counting Tableaux by Shape

Random Tableaux

Longest Increasing Subsequences

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

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 k-Partite Graphs

Cycles, Stars, and Wheels

Grid Graphs

Interconnection Networks

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

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

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

8.7 Planar Graphs 370

Testing Planarity

Reference Guide 376.

Notes:

Includes bibliographical references (pages 448-457) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Class of 1924 Book Fund.

ISBN:

0521806860

OCLC:

51294119

Online:

Publisher description