Combinatorica
Combinatorica とは，組合せ論とグラフ理論における450以上の関数によってWolfram言語を拡張するものである．このような関数には，グラフやその他の組合せのオブジェクトを構成するもの，これらのオブジェクトの不変量を計算するもの，さらにはその結果を表示するものがある．このドキュメントはこれらの関数の一部をカバーするに過ぎない．このパッケージの最善のガイドブックとなるのは，Steven Skiena，Sriram Pemmaraju共著の「Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica 」（2003年Cambridge University Press）であろう．新しい Combinatorica は1990年のオリジナルバージョンにかなり手を加えたものである．新バージョンでは，以前のものよりもずっと速く実行でき，グラフィックスも改善され新機能も大幅に加得られている．
Webのwww.combinatorica.comには，パッケージの最新リリース，Combinatorica グラフのエディタ，興味深い追加ファイル等が掲載されている．
<<Combinatorica`置換と組合せ
置換と部分集合は，最も基本的な組合せのオブジェクトである．Combinatorica はランダムに，または確定的に規則的にオブジェクトを構築する関数を提供することにより，それらのオブジェクトの順番を付けたり外したり，その対象を番号付け・番号呼びしたり，その不変量を計算したりする．ここではこのような関数の使用方法の例を示す．
MinimumChangePermutations[{a, b, c}]RankPermutation /@ Permutations[{1, 2, 3, 4}]
Table[RandomPermutation[3], {20}]
InversePermutation[{4, 8, 5, 2, 1, 3, 7, 6}]
ToCycles[{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}]
個の選択可能な相異なる玉の形（または色）があるとき，
個の玉からネックレスをつくる相異なる方法が何通りあるかを数えよというものである．2つのネックレスが回転だけで（すなわち，ネックレスを裏返すことなしに）得られるときに同じと見なす場合，対称性は恒等置換を循環的に動かして得られる 
個の置換で定義される．色の個数の代わりに変数を指定すれば，1つの多項式が得られる．NecklacePolynomial[8, m, Cyclic]p = RandomPermutation[50];{Inversions[p], Inversions[InversePermutation[p]]}Table[UnrankSubset[n, {a, b, c, d}], {n, 0, 15}]GrayCodeSubsets[{1, 2, 3, 4}]
KSubsets[{1, 2, 3, 4, 5}, 3]Combinatorica の置換関数
Combinatorica の部分集合関数
Combinatorica の群論関数
分割，合成，ヤング盤
正の整数 
の分割は，合計が 
となるような 
個の厳密に正である整数の集合である．
の合成は，和が 
になる非負整数の配置である．
個の要素の集合分割はすべての要素を，空でなく相交わらない部分集合にグループ分けしたものである．ヤング盤は，整数
からなる構造であり，各行の要素（成分）の個数はある 
の整数分割によって定められる．さらに，各行および各列の要素は増加する順に並び，行は左端にそろっている．この4つの関連した組合せのオブジェクトは，多数の面白い応用法と性質を持つ．
IntegerPartitions[6]
Length[IntegerPartitions[20]]FerrersDiagram[RandomPartition[100]]Compositions[5, 3]SetPartitions[3]
Tableaux[{2, 2, 1}]Tableaux[3]
NumberOfTableaux[10]TableForm[RandomTableau[{6, 5, 5, 4, 3, 2}]]
LongestIncreasingSubsequence[RandomPermutation[50]]| Compositions | DominatingIntegerPartitionQ |
| DominationLattice | DurfeeSquare |
| FerrersDiagram | NextComposition |
| NextPartition | PartitionQ |
| RandomComposition | RandomPartition |
| TransposePartition |
Combinatorica の整数分割関数
Combinatorica の集合分割関数
Combinatorica のヤング盤関数
Combinatorica の数を返す関数
グラフの表現
グラフは，辺の集合を伴った頂点の集合として定義される．つまり，1つの辺は2つの頂点として定義される．グラフの表現は，その意図する相手が人間かマシンかに応じて要求条件が異なる．コンピュータは，隣接行列や隣接リストのようなデータ構造としてのグラフを一番よく理解する．一方，人間たちは，線で結ばれた点の集まりとしての構造の視覚化をより好むが，これはグラフに幾何的な情報を付け加えなければならないことを意味する．
ShowGraph[CompleteGraph[5]]CompleteGraph[5]
TableForm[ToAdjacencyMatrix[CompleteGraph[5]]]
Vertices[CompleteGraph[5]]V[CompleteGraph[5]]M[CompleteGraph[5]]g = SetGraphOptions[CompleteGraph[4], VertexColor -> Red, EdgeColor -> Blue]ShowGraph[SetGraphOptions[CompleteGraph[4], {{1, 2, VertexColor -> Green, VertexStyle -> Disk[Large]}, {3, 4, VertexColor -> Blue}}, EdgeColor -> Red]]
ShowGraph[AddEdge[Star[10], {1, 2}]]ShowGraph[GraphSum[Star[10], Star[10]]]
TableForm[ToAdjacencyLists[CompleteGraph[5]]]
ToOrderedPairs[CompleteGraph[5]]
の誘導部分グラフは，
の頂点のある部分集合に，両端がともにこの部分集合に含まれるすべての辺を併せたものである．誘導部分グラフであって完全グラフであるものはクリークと呼ばれる．完全グラフにおける任意の頂点部分集合によりクリークが定義される．ShowGraph[InduceSubgraph[CompleteGraph[20], RandomSubset[Range[20]]]]ShowGraph[Contract[CompleteGraph[6, 6], {1, 7}]]BreadthFirstTraversal[Cycle[20], 1]DepthFirstTraversal[Cycle[20], 1]ShowGraph[RankedEmbedding[GridGraph[5, 5], {13}]]ShowGraph[RandomTree[10]]ShowGraph[RootedEmbedding[RandomTree[10], 1]]
の各頂点が2つの不連結な頂点それぞれに連結されているのがよくわかる．最小エネルギー配置を達成する過程で，これらの2頂点は 
の異なる側に落ち着いていく．ShowGraph[SpringEmbedding[GraphJoin[EmptyGraph[2], CompleteGraph[7]]]]Combinatorica のグラフ変更関数
| Edges | FromAdjacencyLists |
| FromAdjacencyMatrix | FromOrderedPairs |
| FromUnorderedPairs | IncidenceMatrix |
| ToAdjacencyLists | ToAdjacencyMatrix |
| ToOrderedPairs | ToUnorderedPairs |
Combinatorica のグラフ形式解釈関数
Combinatorica のグラフ関数のオプション
| GetEdgeLabels | GetEdgeWeights |
| GetVertexLabels | GetVertexWeights |
| SetEdgeLabels | SetEdgeWeights |
| SetGraphOptions | SetVertexLabels |
| SetVertexWeights |
Combinatorica のグラフのラベルと重みについての関数
Combinatorica のグラフ描画関数
グラフの生成
多くのグラフは，重要な二項関係のモデルであるという点，あるいは独特なグラフ理論的性質を備えているという点において常に興味深いものとなっている．しばしば，これらのグラフは，
頂点の上の完全グラフ 
のように，パラメータをつけて表すことができ，グラフの無限系列を表現する簡潔な記号が与えられる．まず，グラフに作用していろいろなグラフを与えるいくつかの操作を行う．これらの操作は，私たちが与えるパラメータ付きのグラフとともに，実質的にすべての興味深いグラフを構成する手段となる．
ShowGraph[GraphUnion[CompleteGraph[3], CompleteGraph[5, 5]]]ShowGraph[GraphProduct[CompleteGraph[3], CompleteGraph[5]]]
ShowGraph[LineGraph[CompleteGraph[5]]]
ShowGraph[CirculantGraph[21, RandomKSubset[Range[10], 3]]]ShowGraph[DeBruijnGraph[2, 5]]
次元の超立方体は，完全グラフ 
と 
次元の立方体とのグラフの積として定義される．ここでは超立方体のハミルトン閉路が強調されている．色付きのハイライトやグラフのアニメーション化もパッケージで提供されている．ShowGraph[Highlight[Hypercube[4], {Partition[HamiltonianCycle[Hypercube[4]], 2, 1]}]]ShowGraphArray[Partition[FiniteGraphs, 5, 5]]Combinatorica のグラフ構築関数
グラフの性質
グラフ理論は，グラフに固有の性質，すなわち，グラフの不変量についての学問である．興味深い性質には，連結性，循環構造，および彩色数等がある．ここでは，いくつかの異なるグラフの不変量の計算方法を論じる．
ConnectedQ[DeleteEdge[Star[10], {1, 10}]]ConnectedComponents[GraphUnion[CompleteGraph[3], CompleteGraph[4]]]
ShowGraph[OrientGraph[Wheel[10]]]
の接合点は，その頂点を除去すれば 
が不連結になるような頂点であり，接合点を持たない任意のグラフは二重連結である．次数1の頂点を持つ任意のグラフは二重連結ではありえない．なぜなら，その唯一の辺を定義するもう一方の頂点を除去すると，グラフが不連結になるからである．BiconnectedComponents[RealizeDegreeSequence[{4, 4, 3, 3, 3, 2, 1}]]
ArticulationVertices[Star[10]]Bridges[RandomTree[10]]
VertexConnectivity[Wheel[10]]
本の辺の集合が存在しないとき，
辺連結であるという．グラフの辺連結性は，最大でも最小次数 
である．なぜならば，それらの辺を除去するとグラフが不連結となるからである．完全二部グラフはこの上限を実現する．EdgeConnectivity[CompleteGraph[3, 4]]Isomorphism[CompleteGraph[3, 2], CompleteGraph[2, 3], All]SelfComplementaryQ[Cycle[5]] && SelfComplementaryQ[Path[4]]AcyclicQ[RandomGraph[100, 0.5, Type -> Directed]]Girth[CageGraph[3, 6]]EulerianCycle[CompleteGraph[4, 4]]Combinatorica のグラフ叙述関数
のハミルトン閉路は，
のすべての頂点をちょうど一度ずつ訪れる閉路であり，これは各辺をちょうど一度ずつ訪れるオイラー閉路とは対比をなすものである．
のときの 
は唯一のハミルトン完全二部グラフである．HamiltonianCycle[CompleteGraph[3, 3], All]
ならば，
は 
を割り切ることがないから反対称的である．最後に，それは推移的である．というのは，
ならば，ある整数 
に対して 
となり，したがって 
ならば 
となるからである．ShowGraph[g = MakeGraph[Range[8], Mod[#1, #2] == 0&], VertexNumber -> True]PartialOrderQ[g]
ShowGraph[TransitiveReduction[g], VertexNumber -> True]ShowGraph[HasseDiagram[MakeGraph[Subsets[4], #2⋂#1 === #1 && #1 ≠ #2&]]]
であって，辺
は，
において 
が 
よりも前に現れることを意味するものである．他方，有向で非循環の完全グラフは全順序を定めるので，TopologicalSortからの可能な出力はただ1つである．TopologicalSort[MakeGraph[Range[10], #1 > #2&]]
ChromaticPolynomial[GraphUnion[CompleteGraph[2, 2], Cycle[3]], z]Combinatorica のグラフ不定量関数
アルゴリズム的グラフ理論
最後にグラフの不定量の中で，それを計算するアルゴリズムのため特におもしろいものを紹介する．
ShowGraph[ShortestPathSpanningTree[GridGraph[5, 5], 1]]ShortestPath[GridGraph[5, 5], 1, 25]
ShowGraph[MinimumSpanningTree[CompleteGraph[6, 6, 6]]]
NumberOfSpanningTrees[CompleteGraph[10]]
NetworkFlow[CompleteGraph[4, 4], 1, 8]
BipartiteMatching[Cycle[8]]
MaximalMatching[CompleteGraph[8]]Combinatorica のグラフアルゴリズム関数