Computational Graph Theory with Combinatorica
| Table of Contents | Combinatorica in Action | Combinatorica Resources | The Old Combinatorica | Errata list |
We are proud to announce that Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica is finally available! |
Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica is the definitive guide to Combinatorica, perhaps the most widely used software for teaching and research in discrete mathematics. The Combinatorica user community ranges from students to engineers to researchers in mathematics, computer science, physics, economics, and the humanities. Combinatorica has received the EDUCOM Higher Education Software Award and been employed in teaching from grade school to graduate levels. Combinatorica is included with every copy of the popular computer algebra system Mathematica. Experimenting with Combinatorica provides an exciting new way to learn combinatorics and graph theory. This book provides examples of all 450 Combinatiorica functions in action, along with the associated mathematical and algorithmic theory. The book contains no formal proofs, but enough discussion to understand and appreciate all the algorithms and theorems contained within. We cover classical and advanced topics on the most important combinatorial objects: permutations, subsets, partitions, and Young tableaux. We also cover all important areas of graph theory: graph construction operations, invariants, and embeddings as well as algorithmic graph theory. This book can also serve as a unique textbook with enough material to teach or supplement full-semester, experimentally-enhanced courses in combinatorics and graph theory using Mathematica. Three interesting classes of exercises are provided -- theorem/proof, programming exercises, and experimental explorations, providing great flexibility in teaching and learning the material. |
Combinatorica in Action!
|
|
||||
|
|
The newest version of Combinatorica offers substantially improved efficiency and graphics. Thanks to our new sparse-graph representation, is now possible to do interesting operations on graphs with thousands or even hundreds of thousands of vertices. Additional functionality in terms of new graph invariants and computations have also been provided.
This new version was codeveloped by Sriram Pemmaraju and Steven Skiena. The new Combinatorica is best described in our book Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Cambridge University Press, 2003. A nice review of our book appeared in the journal Leonardo.
The new Combinatorica is distributed with Mathematica starting with MMa version 4.2, but runs on older versions of MMa as well. The latest Combinatorica is available for download as the file NewCombinatorica.m. Let us know of your experiences. A short list of known bugs is available.
This work has been partially supported by the National Science Foundation and the Office of Naval Research.
Combinatorica Resources
Combinatorica resources include:
- Latest version of Combinatorica --- Available for download as the file NewCombinatorica.m.
- Getting Started with Combinatorica --- Brief reference guide to Combinatorica in HTML and PDF.
- A paper on the history, philosophy, and design goals of Combinatorica, to appear in the Graph Theory Notes of New York.
- Competing sets of Combinatorica lecture slides (in PDF) by Steven and Sriram, so take your pick!
- Demo Notebook -- Check out our demo notebook containing Combinatorica examples.
- Graph Editor --- A Java-based graph editor for the new Combinatorica has been written by Levon Lloyd.
- Algorithm Animations --- We have put together a collection of algorithm animations which is fun to check out, including dfs/bfs, connected components, Hamiltonian cycle, Eulerian cycle, shortest path, transitive closure, and minimum spanning tree animations!
-
Graph Database --
We have assembled a collection of
in Combinatorica format for testing conjectures
and algorithms.
- Graph Gallery -- Visit our gallery of interesting Combinatorica graphics, including a notebook of our chapter frontpiece images.
- Auxiliary Code from Book -- These bits of code are not of general interest, but were used in particular examples in Computational Discrete Mathematics
The official home of Combinatorica on the net is www.combinatorica.com, Send us bug reports or ask to be put on the mailing list for new releases. Other links of interest include:
- See the Wolfram Research News and Events article Veteran Mathematica User Steven Skiena Is Showing the Fun of Discrete Mathematics for more on the history of Combinatorica.
- Goksen Bacak, Tina Beseri, and Unal Ufuktepe have put together a nice interactive graph coloring demo using webMathematica and Combinatorica.
- Jason Alexander has produced an interesting LocalInteractions package for experimenting with local interaction models of evolutionary games on top of the graph drawing and editing routines of Combinatorica.
- Gabriel Valiente has built an interesting package for graph grammars on top of Combinatorica.
- John Lattanzio developed a graph coloring heuristic which gives better colorings than the Brelaz function in Combinatorica. Local and WRI copies of this page are also available.
- The MuPAD-Combinat project has developed an open-source algebraic combinatorics package for the computer algebra system MuPAD, which will be of interest to those focusing on algebraic combinatorics.
Combinatorica: The Old Edition
|
The original version of Combinatorica was included with Mathematica versions 1.1 through 4.1 in the Packages/DiscreteMath directory. The on-line documentation for the original Combinatorica covers only a subset of these functions, which was best described in Steven Skiena's book: Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, Advanced Book Division, Addison-Wesley, Redwood City CA, June 1990. ISBN number 0-201-50943-1. Japanese translation published by Toppan, Tokyo, July 1992. This book is now out of print, but might still be ordered on-line. The author still has a very small supply of copies which he may be induced to part with. The old Combinatorica now runs (more or less) on Mathics! Check it out! A Java-based graph editor for the old Combinatorica has been produced by Miguel Revilla. Look this page up in Google to enable translation from Spanish. The latest release of the package, data bases of interesting graphs, and additional files which may be of interest are available by anonymous FTP from ftp.cs.sunysb.edu. Animations produced using Combinatorica by Joan Trias are also available. |