**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]:= **<<DiscreteMath`Combinatorica`**

**Permutations and Combinations**

Permutations and subsets are the most basic combinatorial objects. DiscreteMath`Combinatorica` provides functions for constructing objects both randomly and deterministically, to rank and unrank them, and to compute invariants on them. Here we provide examples of some of these functions in action.

These permutations are generated in minimum change order, where successive permutations differ by exactly one transposition. The built-in generator Permutations constructs permutations in lexicographic order.
In[2]:= **MinimumChangePermutations[{a,b,c,d}]**

Out[2]=

The ranking function illustrates that the built-in function Permutations uses lexicographic sequencing.
In[3]:= **Map[RankPermutation, Permutations[{1,2,3,4}]]**

Out[3]=

With

distinct permutations of three elements, within 20 random permutations we are likely to see all of them. Observe that it is unlikely for the first six permutations to all be distinct.
In[4]:= **Table[RandomPermutation[3], {20}]**

Out[4]=

A fixed point of a permutation is an element in the same position in as in the inverse of

. Thus, the only fixed point in this permutation is 7.
In[5]:= **InversePermutation[{4,8,5,2,1,3,7,6}]**

Out[5]=

The identity permutation consists of

singleton cycles or fixed points.
In[6]:= **ToCycles[{1,2,3,4,5,6,7,8,9,10}]**

Out[6]=

The classic problem in Polya theory is counting how many different ways necklaces can be made out of beads, when there are different types or colors of beads to choose from. When two necklaces are considered the same if they can be obtained only by rotating the beads (as opposed to turning the necklace over), the symmetries are defined by

permutations, each of which is a cyclic shift of the identity permutation. When a variable is specified for the number of colors, a polynomial results.
In[7]:= **Polya[Table[**

RotateRight[Range[8],i], {i,8}], m]

Out[7]=

The number of inversions in a permutation is equal to that of its inverse.
In[8]:= **(p=RandomPermutation[50]; {Inversions[p], Inversions[InversePermutation[p]]})**

Out[8]=

Generating subsets incrementally is efficient when the goal is to find the first subset with a given property, since every subset need not be constructed.
In[9]:= **Table[NthSubset[n,{a,b,c,d}], {n,0,15}]**

Out[9]=

In a Gray code, each subset differs in exactly one element from its neighbors. Observe that the last eight subsets all contain

, while none of the first eight do.
In[10]:= **GrayCode[{1,2,3,4}]**

Out[10]=

A k-subset is a subset with exactly elements in it. Since the lead element is placed in first, the

-subsets are given in lexicographic order.
In[11]:= **KSubsets[{1,2,3,4,5},3]**

Out[11]=

Combinatorica functions for permutations and combinations.

**Partitions, Compositions, and Young Tableaux**

A partition of a positive integer is a set of strictly positive integers that sum up to . A composition of is a particular arrangement of non-negative integers that sum up to . A Young tableaux is a structure of integers where the number of elements in each row is defined by an integer partition of

. Further, the elements of each row and column are in increasing order, and the rows are left justified. These three related combinatorial objects have a host of interesting applications and properties.

Here are the eleven partitions of 6. Observe that they are given in reverse lexicographic order.
In[12]:= **Partitions[6]**

Out[12]=

Although the number of partitions grows exponentially, it does so more slowly than permutations or subsets, so complete tables can be generated for larger values of

.
In[13]:= **Length[Partitions[20]]**

Out[13]=

Ferrers diagrams represent partitions as patterns of dots. They provide a useful tool for visualizing partitions, because moving the dots around provides a mechanism for proving bijections between classes of partitions. Here we construct a random partition of 100.
In[14]:= **FerrersDiagram[RandomPartition[100]]**

Here every composition of 6 into 3 parts is generated exactly once.
In[15]:= **Compositions[6,3]**

Out[15]=

The list of tableaux of shape illustrates the amount of freedom available to tableaux structures. The smallest element is always in the upper left-hand corner, but the largest element is free to be the rightmost position of the last row defined by the distinct

parts of the partition.
In[16]:= **Tableaux[{3,2,1}]**

Out[16]=

By iterating through the different integer partitions as shapes, all tableaux of a particular size can be constructed.
In[17]:= **Tableaux[3]**

Out[17]=

The hook length formula can be used to count the number of tableaux for any shape. Using the hook length formula over all partitions of computes the number of tableaux on

elements.
In[18]:= **NumberOfTableaux[10]**

Out[18]=

Each of the 117,123,756,750 tableaux of this shape will be selected with equal likelihood.
In[19]:= **TableForm[ RandomTableau[{6,5,5,4,3,2}] ]**

Out[19]//TableForm=

A pigeonhole result states that any sequence of distinct integers must contain either an increasing or a decreasing scattered subsequence of length

.
In[20]:= **LongestIncreasingSubsequence[**

RandomPermutation[50] ]

Out[20]=

Combinatorica functions for partitions, compositions and Young tableaux.

**Representing Graphs**

We define a graph to be a set of vertices with a set of pairs of these vertices called edges. The representation of graphs takes on different requirements depending upon whether the intended consumer is a person or a machine. Computers digest graphs best as data structures such as adjacency matrices or lists. People prefer a visualization of the structure as a collection of points connected by lines, which implies adding geometric information to the graph.

In the complete graph on five vertices, denoted , each vertex is adjacent to all other vertices. CompleteGraph[n] constructs the complete graph on

vertices.
In[21]:= **ShowGraph[ CompleteGraph[5] ];**

The adjacency matrix of shows that each vertex is adjacent to all other vertices. The main diagonal consists of zeros, since there are no self-loops

in the complete graph, meaning edges from a vertex to itself.
In[22]:= **TableForm[ Edges[CompleteGraph[5]] ]**

Out[22]//TableForm=

The standard embedding of

consists of five vertices equally spaced on a circle.
In[23]:= **Vertices[ CompleteGraph[5] ]**

Out[23]=

The number of vertices in a graph is termed the order of the graph.
In[24]:= **V[ CompleteGraph[5] ]**

Out[24]=

With an optional argument to specify whether we count directed or undirected edges, M returns the number of edges in a graph.
In[25]:= **{M[CompleteGraph[5]], M[CompleteGraph[5], Directed]}**

Out[25]=

A star is a tree with one vertex of degree

. Adding any new edge to a star produces a cycle of length 3.
In[26]:= **ShowGraph[ AddEdge[Star[10], {1,2}] ];**

The adjacency list representation of a graph consists of lists, one list for each vertex , , which records the vertices

is adjacent to. Each vertex in the complete graph is adjacent to all other vertices.
In[27]:= **TableForm[ ToAdjacencyLists[CompleteGraph[5]] ]**

Out[27]//TableForm=

There are ordered pairs of edges defined by a complete graph of order

.
In[28]:= **ToOrderedPairs[ CompleteGraph[5] ]**

Out[28]=

An induced subgraph of a graph is a subset of the vertices of together with any edges whose endpoints are both in this subset. An induced subgraph that is complete is called a clique

. Any subset of the vertices in a complete graph defines a clique.
In[29]:= **ShowGraph[ InduceSubgraph[CompleteGraph[20],**

RandomSubset[Range[20]]] ];

The vertices of a bipartite graph have the property that they can be partitioned into two sets such that no edge connects two vertices of the same set. Contracting an edge in a bipartite graph can ruin its bipartiteness.
In[30]:= **ShowGraph[ Contract[ CompleteGraph[6,6],{1,7} ] ];**

A breadth-first search of a graph explores all the vertices adjacent to the current vertex before moving on. A breadth-first traversal of a simple cycle alternates sides as it wraps around the cycle.
In[31]:= **BreadthFirstTraversal[Cycle[20],1]**

Out[31]=

In a depth-first search, the children of the first son of a vertex are explored before visiting his brothers. The depth-first traversal differs from the breadth-first traversal above, proceeding directly around the cycle.
In[32]:= **DepthFirstTraversal[Cycle[20], 1]**

Out[32]=

Different drawings or embeddings of a graph can reveal different aspects of its structure. The default embedding for a grid graph is a ranked embedding from all the vertices on one side. Ranking from the center vertex yields a different but interesting drawing.
In[33]:= **ShowGraph[**

RankedEmbedding[GridGraph[5,5],{13}]];

The radial embedding of a tree is guaranteed to be planar, but radial embeddings can be used with any graph. Here we see a radial embedding of a random labeled tree.
In[34]:= **ShowGraph[ RandomTree[10] ];**

An interesting general heuristic for drawing graphs models the graph as a system of springs and lets Hooke's law space the vertices. Here it does a good job illustrating the join operation, where each vertex of is connected to each of two disconnected vertices. In achieving the minimum energy configuration, these two vertices end up on different sides of

.
In[35]:= **ShowGraph[**

SpringEmbedding[

GraphJoin[EmptyGraph[2], CompleteGraph[7]]]];

Combinatorica functions for representing graphs.

**Generating Graphs**

Many graphs consistently prove interesting, in the sense that they are models of important binary relations or have unique graph theoretic properties. Often, these graphs can be parameterized, such as the complete graph on vertices

, giving a concise notation for expressing an infinite class of graphs. We start off with several operations that act on graphs to give different graphs and which, together with our parameterized graphs, give us the means to construct essentially any interesting graph.

The union of two connected graphs has two connected components.
In[36]:= **ShowGraph[ GraphUnion[ CompleteGraph[3],**

CompleteGraph[5,5] ] ];

Graph products can be very interesting. The embedding of a product has been designed to show off its structure, and is formed by shrinking the first graph and translating it to the position of each vertex in the second graph.
In[37]:= **ShowGraph[ GraphProduct[ CompleteGraph[3],**

CompleteGraph[5] ] ];

The line graph of a graph has a vertex of associated with each edge of and an edge of if and only if the two edges of

share a common vertex.
In[38]:= **ShowGraph[ LineGraph[CompleteGraph[5]] ];**

Circulants are graphs whose adjacency matrix can be constructed by rotating a vector

times, and include complete graphs and cycles as special cases. Even random circulant graphs have an interesting, regular structure.
In[39]:= **ShowGraph[**

CirculantGraph[21,

RandomKSubset[Range[10],3]]];

This random graph can be expected to have half the number of edges of a complete graph, even though all labeled graphs occur with equal probability.
In[40]:= **ShowGraph[ RandomGraph[20,0.5] ];**

Combinatorica functions for generating graphs.

**Properties of Graphs**

Graph theory is the study of properties or invariants of graphs. Among the properties of interest are such things as connectivity, cycle structure, and chromatic number. Here, we demonstrate how to compute several different graph invariants.

An undirected graph is connected if there exists a path between any pair of vertices. Deleting an edge from a connected graph can disconnect it. Such an edge is called a bridge.
In[41]:= **ConnectedQ[ DeleteEdge[ Star[10], {1,10} ] ]**

Out[41]=

GraphUnion can be used to create disconnected graphs.
In[42]:= **ConnectedComponents[ GraphUnion[CompleteGraph[3],**

CompleteGraph[4]] ]

Out[42]=

An orientation of an undirected graph is an assignment of exactly one direction to each of the edges of . This orientation of a wheel directs each edge in the outer cycle in the same direction, and completes it by giving the center an in-degree of

and out-degree of 1.
In[43]:= **ShowGraph[ OrientGraph[Wheel[10]],**

Directed];

An articulation vertex of a graph is a vertex whose deletion disconnects . Any graph with no articulation vertices is said to be biconnected

. A graph with a vertex of degree 1 cannot be biconnected, since deleting the other vertex that defines its only edge disconnects the graph.
In[44]:= **BiconnectedComponents[**

RealizeDegreeSequence[{4,4,3,3,3,2,1}] ]

Out[44]=

The only articulation vertex of a star is its center, even though its deletion leaves

connected components. Deleting a leaf leaves a connected tree.
In[45]:= **ArticulationVertices[ Star[10] ]**

Out[45]=

Every edge in a tree is a bridge.
In[46]:= **Bridges[ RandomTree[10] ]**

Out[46]=

A graph is said to be k-connected if there does not exist a set of

vertices whose removal disconnects the graph. The wheel is the basic triconnected graph.
In[47]:= **VertexConnectivity[Wheel[5]]**

Out[47]=

A graph is k-edge-connected if there does not exist a set of edges whose removal disconnects the graph. The edge connectivity of a graph is at most the minimum degree

, since deleting those edges disconnects the graph. Complete bipartite graphs realize this bound.
In[48]:= **EdgeConnectivity[CompleteGraph[3,4]]**

Out[48]=

These two complete bipartite graphs are isomorphic, since the order of the two stages is simply reversed. Here, all isomorphisms are returned.
In[49]:= **Isomorphism[CompleteGraph[3,2], CompleteGraph[2,3], All]**

Out[49]=

A graph is self-complementary if it is isomorphic to its complement. The smallest non-trivial self-complementary graphs are the path on four vertices and the cycle on five.
In[50]:= **SelfComplementaryQ[ Cycle[5] ] &&**

SelfComplementaryQ[ Path[4] ]

Out[50]=

A directed graph with half the edges is almost certain to contain a cycle. Directed acyclic graphs are often called DAGs.
In[51]:= **AcyclicQ[**

RandomGraph[7,0.5,Directed], Directed]

Out[51]=

The girth of a graph is the length of its shortest cycle. The girth of a complete graph is 3, since it contains a triangle, the smallest possible cycle.
In[52]:= **Girth[ CompleteGraph[5] ]**

Out[52]=

An Eulerian cycle is a complete tour of all the edges of a graph. An Eulerian cycle of a bipartite graph bounces back and forth between the stages.
In[53]:= **EulerianCycle[ CompleteGraph[4,4] ]**

Out[53]=

A Hamiltonian cycle of a graph is a cycle that visits every vertex in exactly once, as opposed to an Eulerian cycle, which visits each edge exactly once. for

are the only Hamiltonian complete bipartite graphs.
In[54]:= **HamiltonianCycle[CompleteGraph[3,3], All]**

Out[54]=

The divisibility relation between integers is reflexive since each integer divides itself and anti-symmetric, since cannot divide if . Finally, it is transitive, as implies for some integer , so implies

.
In[55]:= **ShowLabeledGraph[**

g = MakeGraph[Range[8],(Mod[#1,#2]==0)&] ];

Since the divisibility relation is reflexive, transitive, and anti-symmetric, it is a partial order.
In[56]:= **PartialOrderQ[g]**

Out[56]=

A graph is transitive if any three vertices such that edges imply . The transitive reduction of a graph is the smallest graph such that . The transitive reduction eliminates all implied edges in the divisibility relation, such as , , , and

.
In[57]:= **ShowLabeledGraph[TransitiveReduction[g]]**

The Hasse diagram clearly shows the lattice structure of the Boolean algebra, the partial order defined by inclusion on the set of subsets.
In[58]:= **ShowLabeledGraph[**

HasseDiagram[MakeGraph[Subsets[4],

((Intersection[#2,#1]===#1)&&(#1 != #2))&]],

Subsets[4] ];

A topological sort is a permutation of the vertices of a graph such that an edge implies appears before in . A complete directed acyclic graph defines a total order, so there is only one possible output from TopologicalSort

.
In[59]:= **TopologicalSort[**

MakeGraph[Range[10],(#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.