COMBINATORICA パッケージ チュートリアル
Combinatorica
Combinatorica とは，組合せ論とグラフ理論における450以上の関数によって Mathematica を拡張するものである．このような関数には，グラフやその他の組合せのオブジェクトを構成するもの，これらのオブジェクトの不変量を計算するもの，さらにはその結果を表示するものがある．このドキュメントはこれらの関数の一部をカバーするに過ぎない．このパッケージの最善のガイドブックとなるのは，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 はランダムに，または確定的に規則的にオブジェクトを構築する関数を提供することにより，それらのオブジェクトの順番を付けたり外したり，その対象を番号付け・番号呼びしたり，その不変量を計算したりする．ここではこのような関数の使用方法の例を示す．
このような置換は，隣合う置換がちょうど1つの転置だけ異なっている最小変化順序で生成される．組み込みジェネレータの
Permutationsは辞書式順序で置換を構成する．
| Out[2]= |  |
| Out[3]= |  |
3つの元の相異なる置換は
個あり，20回ランダムに置換を行う間にそれらすべてが見られる公算が高い．最初の6つの置換がすべて異なる公算は低いことに注目しよう．
| Out[4]= |  |
置換
の固定点は，
においても，
の逆置換におけるのと同じ位置にある元である．したがって，この置換の唯一の固定点は7である．
| Out[5]= |  |
恒等置換は元が1つだけの
個の巡回置換，すなわち固定点からなっている．
| Out[6]= |  |
Polya理論における典型的な例題は，
個の選択可能な相異なる玉の形（または色）があるとき，
個の玉からネックレスをつくる相異なる方法が何通りあるかを数えよというものである．2つのネックレスが回転だけで（すなわち，ネックレスを裏返すことなしに）得られるときに同じと見なす場合，対称性は恒等置換を循環的に動かして得られる
個の置換で定義される．色の個数の代わりに変数を指定すれば，1つの多項式が得られる．
| Out[7]= |  |
| Out[8]= |  |
目的が，与えられた性質を持つ最初の部分集合を見つけることなら，すべての部分集合を構成する必要はないので，部分集合を増加の順に生成するのが効率がよい．
| Out[9]= |  |
グレイコードでは，各部分集合は隣のものとちょうど1元だけ異なっている．最後の8つの部分集合はすべて
を含み，最初の8つはどれも含んでいないことに注目しよう．
| Out[10]= |  |
部分集合はその中にちょうど
個の要素を含む部分集合である．先頭の要素が最初の置かれるので，
部分集合は辞書式順序で与えられる．
| Out[11]= |  |
Combinatorica の置換関数
Combinatorica の部分集合関数
Combinatorica の群論関数
分割，合成，ヤング盤
正の整数 
の分割は，合計が 
となるような 
個の厳密に正である整数の集合である．
の合成は，和が 
になる非負整数の配置である．
個の要素の集合分割はすべての要素を，空でなく相交わらない部分集合にグループ分けしたものである．ヤング盤は，整数
からなる構造であり，各行の要素（成分）の個数はある 
の整数分割によって定められる．さらに，各行および各列の要素は増加する順に並び，行は左端にそろっている．この4つの関連した組合せのオブジェクトは，多数の面白い応用法と性質を持つ．
ここにあるのは6の分割11個である．逆辞書式順序で与えられていることに注目しよう．
| Out[12]= |  |
分割の個数は指数関数的に増大するが，置換や部分集合の場合よりは緩やかなので，
のより大きい値まで完全な表を生成できる．
| Out[13]= |  |
フェラーズ図形は，分割をドット・パターンとして表す．ドットをあちこちと動かすことにより分割のクラスの間の全単射を証明するメカニズムが得られるので，フェラーズ図形は分割を視覚化する有用な道具となる．ここでは100のランダムな分割を構成する．
| Out[14]= |  |
ここで3個の成分への5の各合成はちょうど1度ずつ生成されている．
| Out[15]= |  |
集合分割は整数の分割とは異なり，異なる要素を部分集合に分割することができる方法を示す．これは彩色やクラスタリングに便利である．
| Out[16]= |  |
型が
である盤のリストはこの盤の構造に許される自由度を示している．最小要素はつねに左上の隅にあるが，最大要素は，分割の相異なる成分で定まる最後の行の右端の位置をどこでも自由にとることができる．
| Out[17]= |  |
相異なる整数分割を型として反復することにより，一定のサイズの盤全体が構成できる．
| Out[18]= |  |
フック長公式は，任意の与えられた型に対して盤の個数を数えるのに用いることができる．
のすべての分割にわたってフック長の公式を用いることにより，
個の元における盤の総数が計算される．
| Out[19]= |  |
この型の盤117，123，756，750個すべてが等しい尤度で選ばれる．
Out[20]//TableForm= |
| |  |
鳩の巣原理の結果によると，
個の相異なる整数の任意の列は長さ
の飛び飛びの増加部分列または減少部分列を含まなくてはならない．
| Out[21]= |  |
Combinatorica の整数分割関数
Combinatorica の集合分割関数
Combinatorica のヤング盤関数
Combinatorica の数を返す関数
グラフの表現
グラフは，辺の集合を伴った頂点の集合として定義される．つまり，1つの辺は2つの頂点として定義される．グラフの表現は，その意図する相手が人間かマシンかに応じて要求条件が異なる．コンピュータは，隣接行列や隣接リストのようなデータ構造としてのグラフを一番よく理解する．一方，人間たちは，線で結ばれた点の集まりとしての構造の視覚化をより好むが，これはグラフに幾何的な情報を付け加えなければならないことを意味する．
5頂点の上の完全グラフ
では，各頂点は他の全頂点に隣接する．
CompleteGraph[n]は，
頂点の上の完全グラフを構成する関数である．
| Out[22]= |  |
グラフ表現の内部構造はユーザには見えない．辺や頂点の数に続いてグラフが有向か無向かが示されるだけである．
| Out[23]= |  |
の隣接行列は，各頂点がすべてのほかの頂点に隣接することを示している．完全グラフには自己ループ，すなわちある頂点からそれ自身への辺はないので，主対角線は0からなる．
Out[24]//TableForm= |
| |  |
の標準的埋め込みは，円周上に等間隔に置かれた5頂点からなる．
| Out[25]= |  |
| Out[26]= |  |
はグラフの中の辺の個数を返す．
| Out[27]= |  |
辺・頂点の色やスタイルは大域的に変更でき，グラフの外観を変えることのできる完全な柔軟性を提供する．
| Out[28]= |  |
各頂点や辺の色・スタイル・ラベル・重みは，グラフの興味深い性質をひきたてるように，個々について変更することができる．
| Out[29]= |  |
星は次数
の頂点をもつ木である．星にどんな新しい辺を付け加えても，長さ3の閉路ができる．
| Out[30]= |  |
多重辺や自己ループを持つグラフもサポートされている．これは星の各辺が重複している．
| Out[31]= |  |
グラフの隣接リスト表現は，各頂点
(
)に対しそれぞれ
が隣接している頂点を記録する
個のリストからなっている．完全グラフの各頂点は，他のすべての頂点に隣接する．
Out[32]//TableForm= |
| |  |
位数
の完全グラフにおいて定義される，辺を表現する順序対は
個ある．
| Out[33]= |  |
グラフ
の誘導部分グラフは，
の頂点のある部分集合に，両端がともにこの部分集合に含まれるすべての辺を併せたものである．誘導部分グラフであって完全グラフであるものはクリークと呼ばれる．完全グラフにおける任意の頂点部分集合によりクリークが定義される．
| Out[34]= |  |
二部グラフの頂点は，2つの集合に分割し，同じ集合に属する2つの頂点は決して辺で結ばれないようにすることができるという性質がある．二部グラフの辺を縮約すると，もはや二部グラフではなくなることがある．縮約によってできた自己ループに注目のこと．
| Out[35]= |  |
グラフの幅優先探索は，現在の頂点に隣接するすべての頂点を探索してから次に移る．単純閉路での幅優先探索は交互に往来を繰り返しながらこの閉路をとり囲んでいく．
| Out[36]= |  |
深さ優先探索では，頂点の長男の子供たちを訪問してからその兄弟のところを訪れる．深さ優先探索は上述の幅優先探索とは異なり，閉路をまっすぐに進む．
| Out[37]= |  |
グラフの描画や埋込みの相異は，そのグラフの構造の異なった部分を示すことがある．格子グラフのデフォルトの埋込みは1辺の上の頂点全体からのランク付き埋込みである．中央の頂点からのランク付けはこれとは異なる．しかし興味深い描画を生ずる．
| Out[38]= |  |
木の放射状埋込みは平面グラフであることが保証されているが，放射状埋込みはそれ以外の任意のグラフにも用いることができる．これはランダムにラベルを付けられた木についての放射状埋込みである．
| Out[39]= |  |
任意に根を選ぶことにより，どんな木も根付き木として表現できる．
| Out[40]= |  |
グラフを描く興味深い一般性のある発見的方法は，グラフをバネのシステムとしてモデル化し，フックの法則によって頂点の間隔を決める．ここでは，それは接合（join）操作の働きをうまく示してくれ，
の各頂点が2つの不連結な頂点それぞれに連結されているのがよくわかる．最小エネルギー配置を達成する過程で，これらの2頂点は
の異なる側に落ち着いていく．
| Out[41]= |  |
Combinatorica のグラフ変更関数
Combinatorica のグラフ形式解釈関数
Combinatorica のグラフ関数のオプション
Combinatorica のグラフのラベルと重みについての関数
Combinatorica のグラフ描画関数
グラフの生成
多くのグラフは，重要な二項関係のモデルであるという点，あるいは独特なグラフ理論的性質を備えているという点において常に興味深いものとなっている．しばしば，これらのグラフは，
頂点の上の完全グラフ 
のように，パラメータをつけて表すことができ，グラフの無限系列を表現する簡潔な記号が与えられる．まず，グラフに作用していろいろなグラフを与えるいくつかの操作を行う．これらの操作は，私たちが与えるパラメータ付きのグラフとともに，実質的にすべての興味深いグラフを構成する手段となる．
| Out[42]= |  |
グラフの積は非常に興味深いものとなりうる．積の埋め込みはその構造をよく表すように設計されており，第1のグラフを縮めて第2のグラフの中の各頂点の位置へこれを平行移動することで作られる．
| Out[43]= |  |
グラフ
の線グラフ
は，
の各辺に対応する
の頂点を持ち，
の2つの辺が同じ頂点を共有するときに限って
の辺を持つ．
| Out[44]= |  |
循環グラフは隣接行列が1つのベクトルを
回転することによって構成できるグラフで，特殊な場合として完全グラフや閉路を含む．ランダムな循環グラフでさえ興味深い規則的な構造をもつ．
| Out[45]= |  |
グラフジェネレータの中には，バイナリアルファベットの長さ5の部分文字列をすべてコード化する下の
de Bruijn グラフのような，自己ループをもつ有向グラフを生成するものもある．
| Out[46]= |  |
次元の超立方体は，完全グラフ
と
次元の立方体とのグラフの積として定義される．ここでは超立方体のハミルトン閉路が強調されている．色付きのハイライトやグラフのアニメーション化もパッケージで提供されている．
| Out[47]= |  |
いくつかの組込みのグラフ構成関数にはパラメータがなく，単一のおもしろいグラフのみを構成するものがある．
FiniteGraphsはそのような関数を1つのリストにまとめるので便利である．
ShowGraphArrayを使うと，1つのウィンドウに複数のグラフが表示できる．
| Out[48]= |  |
Combinatorica のグラフ構築関数
グラフの性質
グラフ理論は，グラフに固有の性質，すなわち，グラフの不変量についての学問である．興味深い性質には，連結性，循環構造，および彩色数等がある．ここでは，いくつかの異なるグラフの不変量の計算方法を論じる．
無向グラフが連結であるとは，頂点の任意のペア（対）の間に路が存在するときである．連結グラフから辺を1本除去すると連結でなくなることがある．そのような辺は橋と呼ばれる．
| Out[49]= |  |
| Out[50]= |  |
無向グラフ
の向き付けとは，
の各辺にそれぞれ1つだけ方向を定めることである．それぞれの辺の方向を示している矢印は有向グラフの表示の際に自動的に描画されることに注意．
| Out[51]= |  |
グラフ
の接合点は，その頂点を除去すれば
が不連結になるような頂点であり，接合点を持たない任意のグラフは二重連結である．次数1の頂点を持つ任意のグラフは二重連結ではありえない．なぜなら，その唯一の辺を定義するもう一方の頂点を除去すると，グラフが不連結になるからである．
| Out[52]= |  |
星の中心を除去すると
個の連結成分ができるにもかかわらず，星の接合点は中心の1点しかない．葉を除去すると連結な木が残る．
| Out[53]= |  |
| Out[54]= |  |
グラフは，それらを除去するとグラフが不連結となるような
頂点の集合が存在しないとき，
連結であるという．車輪は，基本的な三重連結グラフである．
| Out[55]= |  |
グラフはそれらを除去するとグラフが不連結となるような
本の辺の集合が存在しないとき，
辺連結であるという．グラフの辺連結性は，最大でも最小次数
である．なぜならば，それらの辺を除去するとグラフが不連結となるからである．完全二部グラフはこの上限を実現する．
| Out[56]= |  |
2つのグラフの位数が単に逆転されているだけなので，これら2つの完全2部グラフは同型である．ここでは同型のものがすべて返される．
| Out[57]= |  |
グラフが自己補充的であるとは，それがそれ自身の補グラフに同型であるときをいう．最小の自明でない自己補充的グラフは4頂点の上の路，および5頂点の上の閉路である．
| Out[58]= |  |
可能な辺のうち半数を持つ有向グラフは，ほとんど確実に閉路を含む．有向の非循環グラフは，しばしばDAGと呼ばれる．
| Out[59]= |  |
グラフの内周は最短閉路の長さである．籠は指定された内周をもつ最小の正則（ここでは次数3）グラフである．
| Out[60]= |  |
オイラー閉路は，グラフのすべての辺を完全に巡る周遊路である．二部グラフのオイラー閉路は，2つのグラフの間を行ったり来たりする．
| Out[61]= |  |
Combinatorica のグラフ叙述関数
グラフ
のハミルトン閉路は，
のすべての頂点をちょうど一度ずつ訪れる閉路であり，これは各辺をちょうど一度ずつ訪れるオイラー閉路とは対比をなすものである．
のときの
は唯一のハミルトン完全二部グラフである．
| Out[62]= |  |
整数の間の整除関係は，各整数はそれ自身を割り切るから反射的であり，
ならば，
は
を割り切ることがないから反対称的である．最後に，それは推移的である．というのは，
ならば，ある整数
に対して
となり，したがって
ならば
となるからである．
| Out[63]= |  |
整除関係は反射的，推移的，かつ反対称的であるので，それは半順序である．
| Out[64]= |  |
グラフ
は，任意の3つの頂点
，
，
について
から
が導かれるとき，推移的である．グラフ
の推移縮約は，
となる最小のグラフ
である．推移縮約は整除関係で暗示される
，
，
，
のような辺をすべて除去する．
| Out[65]= |  |
ハッセ図形は，部分集合の上の包含によって定められる半順序であるブール代数の格子構造を明らかに示している．
| Out[66]= |  |
相位的ソートは，グラフの頂点の置換
であって，辺
は，
において
が
よりも前に現れることを意味するものである．他方，有向で非循環の完全グラフは全順序を定めるので，
TopologicalSortからの可能な出力はただ1つである．
| Out[67]= |  |
任意のラベル付きグラフ
は，ちょうど
個の色
によって一定数の方法で彩色できる．この数は，グラフの彩色多項式によって決まる．
| Out[68]= |  |
Combinatorica のグラフ不定量関数
アルゴリズム的グラフ理論
最後にグラフの不定量の中で，それを計算するアルゴリズムのため特におもしろいものを紹介する．
格子グラフの最短経路全域木はマンハッタン距離を用いて定義される．ここで，座標
と
の点の間の距離は
である．
| Out[69]= |  |
重みのないグラフにおいては，どの頂点のペアの間にも多くの異なる最短路がありうる．2つの向かい合った角の間のこの路はずっと右まで進み，そのあとずっと上まで進む．
| Out[70]= |  |
重み付きグラフの最小全域木は，グラフの全域木をなし，重みの合計が最小となる
辺の集合である．グラフが重み付けられていないときは，どの全域木も最小全域木である．
| Out[71]= |  |
Cayleyによって証明されたように，完全グラフの全域木の個数は
である．
| Out[72]= |  |
重みのない完全二部グラフ
を通る最大流は，最小次数
である．
| Out[73]= |  |
グラフ
におけるマッチングとは，
の辺の集合であって，それらのどの2本も頂点を共有していないものである．偶閉路の完全マッチングは，閉路の1つおきの辺からなる．
| Out[74]= |  |
のどの極大マッチングも最大マッチングであり，
が偶数ならば，完全である．
| Out[75]= |  |
Combinatorica のグラフアルゴリズム関数
