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 はランダムに，または確定的に規則的にオブジェクトを構築する関数を提供することにより，それらのオブジェクトの順番を付けたり外したり，その対象を番号付け・番号呼びしたり，その不変量を計算したりする．ここではこのような関数の使用方法の例を示す．

3つの元の相異なる置換は個あり，20回ランダムに置換を行う間にそれらすべてが見られる公算が高い．最初の6つの置換がすべて異なる公算は低いことに注目しよう．

置換 の固定点は， においても， の逆置換におけるのと同じ位置にある元である．したがって，この置換の唯一の固定点は7である．

恒等置換は元が1つだけの 個の巡回置換，すなわち固定点からなっている．

Polya理論における典型的な例題は， 個の選択可能な相異なる玉の形（または色）があるとき， 個の玉からネックレスをつくる相異なる方法が何通りあるかを数えよというものである．2つのネックレスが回転だけで（すなわち，ネックレスを裏返すことなしに）得られるときに同じと見なす場合，対称性は恒等置換を循環的に動かして得られる 個の置換で定義される．色の個数の代わりに変数を指定すれば，1つの多項式が得られる．

部分集合はその中にちょうど 個の要素を含む部分集合である．先頭の要素が最初の置かれるので， 部分集合は辞書式順序で与えられる．

Combinatorica の置換関数

Combinatorica の部分集合関数

Combinatorica の群論関数

分割，合成，ヤング盤

正の整数 の分割は，合計が となるような 個の厳密に正である整数の集合である． の合成は，和が になる非負整数の配置である． 個の要素の集合分割はすべての要素を，空でなく相交わらない部分集合にグループ分けしたものである．ヤング盤は，整数 からなる構造であり，各行の要素（成分）の個数はある の整数分割によって定められる．さらに，各行および各列の要素は増加する順に並び，行は左端にそろっている．この4つの関連した組合せのオブジェクトは，多数の面白い応用法と性質を持つ．

分割の個数は指数関数的に増大するが，置換や部分集合の場合よりは緩やかなので， のより大きい値まで完全な表を生成できる．

型がである盤のリストはこの盤の構造に許される自由度を示している．最小要素はつねに左上の隅にあるが，最大要素は，分割の相異なる成分で定まる最後の行の右端の位置をどこでも自由にとることができる．

フック長公式は，任意の与えられた型に対して盤の個数を数えるのに用いることができる． のすべての分割にわたってフック長の公式を用いることにより， 個の元における盤の総数が計算される．

鳩の巣原理の結果によると，個の相異なる整数の任意の列は長さ の飛び飛びの増加部分列または減少部分列を含まなくてはならない．

Combinatorica の整数分割関数

Combinatorica の集合分割関数

Combinatorica のヤング盤関数

Combinatorica の数を返す関数

グラフの表現

グラフは，辺の集合を伴った頂点の集合として定義される．つまり，1つの辺は2つの頂点として定義される．グラフの表現は，その意図する相手が人間かマシンかに応じて要求条件が異なる．コンピュータは，隣接行列や隣接リストのようなデータ構造としてのグラフを一番よく理解する．一方，人間たちは，線で結ばれた点の集まりとしての構造の視覚化をより好むが，これはグラフに幾何的な情報を付け加えなければならないことを意味する．

5頂点の上の完全グラフ では，各頂点は他の全頂点に隣接する．CompleteGraph[n]は， 頂点の上の完全グラフを構成する関数である．

の隣接行列は，各頂点がすべてのほかの頂点に隣接することを示している．完全グラフには自己ループ，すなわちある頂点からそれ自身への辺はないので，主対角線は0からなる．

の標準的埋め込みは，円周上に等間隔に置かれた5頂点からなる．

星は次数 の頂点をもつ木である．星にどんな新しい辺を付け加えても，長さ3の閉路ができる．

グラフの隣接リスト表現は，各頂点 ()に対しそれぞれ が隣接している頂点を記録する 個のリストからなっている．完全グラフの各頂点は，他のすべての頂点に隣接する．

位数 の完全グラフにおいて定義される，辺を表現する順序対は 個ある．

グラフ の誘導部分グラフは， の頂点のある部分集合に，両端がともにこの部分集合に含まれるすべての辺を併せたものである．誘導部分グラフであって完全グラフであるものはクリークと呼ばれる．完全グラフにおける任意の頂点部分集合によりクリークが定義される．

グラフを描く興味深い一般性のある発見的方法は，グラフをバネのシステムとしてモデル化し，フックの法則によって頂点の間隔を決める．ここでは，それは接合（join）操作の働きをうまく示してくれ， の各頂点が2つの不連結な頂点それぞれに連結されているのがよくわかる．最小エネルギー配置を達成する過程で，これらの2頂点は の異なる側に落ち着いていく．

Combinatorica のグラフ変更関数

Combinatorica のグラフ形式解釈関数

Combinatorica のグラフ関数のオプション

Combinatorica のグラフのラベルと重みについての関数

Combinatorica のグラフ描画関数

グラフの生成

多くのグラフは，重要な二項関係のモデルであるという点，あるいは独特なグラフ理論的性質を備えているという点において常に興味深いものとなっている．しばしば，これらのグラフは， 頂点の上の完全グラフ のように，パラメータをつけて表すことができ，グラフの無限系列を表現する簡潔な記号が与えられる．まず，グラフに作用していろいろなグラフを与えるいくつかの操作を行う．これらの操作は，私たちが与えるパラメータ付きのグラフとともに，実質的にすべての興味深いグラフを構成する手段となる．

グラフ の線グラフ は， の各辺に対応する の頂点を持ち， の2つの辺が同じ頂点を共有するときに限って の辺を持つ．

循環グラフは隣接行列が1つのベクトルを 回転することによって構成できるグラフで，特殊な場合として完全グラフや閉路を含む．ランダムな循環グラフでさえ興味深い規則的な構造をもつ．

次元の超立方体は，完全グラフ と 次元の立方体とのグラフの積として定義される．ここでは超立方体のハミルトン閉路が強調されている．色付きのハイライトやグラフのアニメーション化もパッケージで提供されている．

Combinatorica のグラフ構築関数

グラフの性質

グラフ理論は，グラフに固有の性質，すなわち，グラフの不変量についての学問である．興味深い性質には，連結性，循環構造，および彩色数等がある．ここでは，いくつかの異なるグラフの不変量の計算方法を論じる．

無向グラフ の向き付けとは， の各辺にそれぞれ1つだけ方向を定めることである．それぞれの辺の方向を示している矢印は有向グラフの表示の際に自動的に描画されることに注意．

グラフ の接合点は，その頂点を除去すれば が不連結になるような頂点であり，接合点を持たない任意のグラフは二重連結である．次数1の頂点を持つ任意のグラフは二重連結ではありえない．なぜなら，その唯一の辺を定義するもう一方の頂点を除去すると，グラフが不連結になるからである．

星の中心を除去すると 個の連結成分ができるにもかかわらず，星の接合点は中心の1点しかない．葉を除去すると連結な木が残る．

グラフは，それらを除去するとグラフが不連結となるような 頂点の集合が存在しないとき， 連結であるという．車輪は，基本的な三重連結グラフである．

グラフはそれらを除去するとグラフが不連結となるような 本の辺の集合が存在しないとき， 辺連結であるという．グラフの辺連結性は，最大でも最小次数 である．なぜならば，それらの辺を除去するとグラフが不連結となるからである．完全二部グラフはこの上限を実現する．

Combinatorica のグラフ叙述関数

グラフ のハミルトン閉路は， のすべての頂点をちょうど一度ずつ訪れる閉路であり，これは各辺をちょうど一度ずつ訪れるオイラー閉路とは対比をなすものである．のときの は唯一のハミルトン完全二部グラフである．

整数の間の整除関係は，各整数はそれ自身を割り切るから反射的であり， ならば， は を割り切ることがないから反対称的である．最後に，それは推移的である．というのは， ならば，ある整数 に対して となり，したがって ならば となるからである．

グラフ は，任意の3つの頂点 ，， について から が導かれるとき，推移的である．グラフ の推移縮約は，となる最小のグラフ である．推移縮約は整除関係で暗示される，，，のような辺をすべて除去する．

相位的ソートは，グラフの頂点の置換 であって，辺は， において が よりも前に現れることを意味するものである．他方，有向で非循環の完全グラフは全順序を定めるので，TopologicalSortからの可能な出力はただ1つである．

任意のラベル付きグラフ は，ちょうど 個の色 によって一定数の方法で彩色できる．この数は，グラフの彩色多項式によって決まる．

Combinatorica のグラフ不定量関数

アルゴリズム的グラフ理論

最後にグラフの不定量の中で，それを計算するアルゴリズムのため特におもしろいものを紹介する．

格子グラフの最短経路全域木はマンハッタン距離を用いて定義される．ここで，座標との点の間の距離はである．

重み付きグラフの最小全域木は，グラフの全域木をなし，重みの合計が最小となる 辺の集合である．グラフが重み付けられていないときは，どの全域木も最小全域木である．

Cayleyによって証明されたように，完全グラフの全域木の個数は である．

重みのない完全二部グラフ を通る最大流は，最小次数 である．

グラフ におけるマッチングとは， の辺の集合であって，それらのどの2本も頂点を共有していないものである．偶閉路の完全マッチングは，閉路の1つおきの辺からなる．

のどの極大マッチングも最大マッチングであり， が偶数ならば，完全である．

Combinatorica のグラフアルゴリズム関数