This is documentation for Mathematica 3, which was
based on an earlier version of the Wolfram Language.
 DiscreteMath`Combinatorica` DiscreteMath`Combinatorica` extends Mathematica by over 230 functions in combinatorics and graph theory. It includes functions for constructing graphs and other combinatorial objects, computing invariants of these objects, and finally displaying them. This documentation covers only a subset of these functions. The best guide to this package is the book Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica, by Steven Skiena, published by Addison-Wesley Publishing Company, 1990. This loads the package. In[1]:= < #2)&] ] Out[59]= Any labeled graph can be colored in a certain number of ways with exactly colors . This number is determined by the chromatic polynomial of the graph. In[60]:= ChromaticPolynomial[ GraphUnion[CompleteGraph[2,2], Cycle[3]], z ] Out[60]= Combinatorica functions for properties of graphs. Algorithmic Graph Theory Finally, there are several invariants of graphs which are of particular interest because of the algorithms that compute them. The shortest-path spanning tree of a grid graph is defined in terms of Manhattan distance, where the distance between points with coordinates and is . In[61]:= ShowGraph[ ShortestPathSpanningTree[ GridGraph[5,5],1] ]; In an unweighted graph there can be many different shortest paths between any pair of vertices. This path between two opposing corners goes all the way to the right, then all the way to the top. In[62]:= ShortestPath[GridGraph[5,5],1,25] Out[62]= A minimum spanning tree of a weighted graph is a set of edges of minimum total weight which form a spanning tree of the graph. Any spanning tree is a minimum spanning tree when the graphs are unweighted. In[63]:= ShowGraph[ MinimumSpanningTree[ CompleteGraph[6,6,6] ] ]; The number of spanning trees of a complete graph is , as was proved by Cayley. In[64]:= NumberOfSpanningTrees[CompleteGraph[10]] Out[64]= The maximum flow through an unweighted complete bipartite graph is the minimum degree . In[65]:= NetworkFlow[ CompleteGraph[4,4], 1, 8] Out[65]= A matching in a graph is a set of edges of such that no two of them share a vertex in common. A perfect matching of an even cycle consists of alternating edges in the cycle. In[66]:= BipartiteMatching[ Cycle[8] ] Out[66]= Any maximal matching of a is a maximum matching, and perfect if is even. In[67]:= MaximalMatching[CompleteGraph[8]] Out[67]= Planar graphs are graphs which can be embedded in the plane with no pair of edges crossing. and are the basic nonplanar graphs. In[68]:= PlanarQ[CompleteGraph[5]] || PlanarQ[CompleteGraph[3,3]] Out[68]= Every planar graph on nine vertices has a nonplanar complement. In[69]:= PlanarQ[ GraphComplement[GridGraph[3,3]] ] Out[69]= Combinatorica functions for algorithmic graph theory. Note: For further information about Combinatorica, and to be kept informed about new releases, you may contact the author electronically at skiena@sbcs.sunysb.edu. The latest release of the package and additional files which may be of interest are available by anonymous FTP from cs.sunysb.edu.