A Tour of Combinatorica

<< DiscreteMath`Combinatorica`

Basic Combinatorial Objects

Permutations[3]

Subsets[4]

Partitions[5]

Timing[Length[Partitions[30]]]

FerrersDiagram[RandomPartition[500]];

SetPartitions[4]

Tableaux[{3, 3}]

Counting

Table[NumberOfTableaux[{i, i}], {i, 1, 10}]

Table[NumberOfGraphs[i], {i, 1, 10}]

ShowGraph[ 
        Highlight[ 
          gg = GridGraph[3, 3, 3], {Edges[
              t = DepthFirstTraversal[ gg, 1, Tree]]}, 
          HighlightedEdgeColors -> {Red}]];

DegreeSequence[t]

NumberOfSpanningTrees[gg]

ds  =  DeBruijnSequence[{0, 1}, 4]

Table[Take[RotateLeft[ds, i], 4], {i, 0, Length[ds] - 1}]

Pretty Graphs

\(\(\(ShowGraph[
        hd\  = HasseDiagram[
            MakeGraph[
              Subsets[6], \((\((Intersection[#2, #1] === #1)\) && \((#1 ≠ #2)\))\) &]], EdgeColor -> Blue];\)\(
\)
    \)\)

ShowGraph[ 
        Highlight[hd,  {Partition[HamiltonianCycle[hd], 2, 1]}, 
          HighlightedEdgeColors -> {Red}], 
        EdgeColor -> Gray];

\(\(\(Isomorphism[
      HasseDiagram[
        MakeGraph[
          Subsets[4], \((\((Intersection[#2, #1] === #1)\) && \((#1 ≠ #2)\))\) &]], Hypercube[4]]\)\(
\)\(
\)
    \)\)

ShowGraph[
        p1 = GraphProduct[K5 = CompleteGraph[5], K3 = CompleteGraph[3]], 
        EdgeColor -> Purple];

ShowGraph[ p2 = GraphProduct[K3, K5], 
        EdgeColor -> Pink];

Isomorphism[p1, p2]

\(\(\(ShowGraph[lg\  = \ LineGraph[LineGraph[CompleteGraph[5]]], 
        EdgeColor -> Orange];\)\(
\)
    \)\)

ShowGraph[PetersenGraph, VertexStyle -> Disk[Large], 
        EdgeColor -> Red, EdgeStyle -> ThickDashed, 
        Background -> LightBlue];

ShowGraph[
        Highlight[
          k = KnightsTourGraph[6, 6], {Partition[HamiltonianCycle[k], 2, 1]}, 
          HighlightedEdgeColors -> {Green}], 
        EdgeColor -> Gray];

Timing[ g = 
          InduceSubgraph[GridGraph[20, 30], 
            RandomKSubset[Range[600], 400]]; ]

Timing[ m = MaximalMatching[g];]

ShowGraph[
        Highlight[g, {m}, HighlightedEdgeColors -> {Purple}]];

Algorithmic Graph Theory

ShowGraph[ 
        Highlight[ 
          ng = GridGraph[5, 5, 5],  {{32, 93}, 
            First[Transpose[NetworkFlow[ng, 32, 93, Edge]]]}], 
        EdgeColor -> Gray];