DiscreteMath`Combinatorica`

DiscreteMath`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 グラフィックスのエディタ，興味深い追加ファイルなどがある．

これでパッケージをロードする．

In[1]:= <<DiscreteMath`Combinatorica`

並べ換えと組み合わせ

並べ換えと部分集合は，組み合わせ論的な対象で最も基本的なものである．DiscreteMath`Combinatorica`はランダムに，または規則的に対象を構成したり，その対象を番号付け・番号呼びしたり，その不変量を計算するための関数を提供している．ここではこのような関数の使用方法の例を示す．

このような並べ換えは，隣合う並べ換えがちょうど1つの互換だけ異なっている最小変化順序で生成される．組み込みジェネレータのPermutationsは辞書式順序で並べ換えを構成する．

In[2]:= MinimumChangePermutations[{a,b,c}]

Out[2]=

番号付け関数により，組込み関数のPermutationsが辞書式整列法を用いていることがわかる．

In[3]:= Map[RankPermutation, Permutations[{1,2,3,4}]]

Out[3]=

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

In[4]:= Table[RandomPermutation[3], {20}]

Out[4]=

並べ換えの固定点は，においても，恒等並べ換えにおけるのと同じ位置にある要素である．例えば，この並べ換えの唯一の固定点は７である．

In[5]:= InversePermutation[{4,8,5,2,1,3,7,6}]

Out[5]=

恒等並べ換えは個の単身サイクル，すなわち固定点からなっている．

In[6]:= ToCycles[{1,2,3,4,5,6,7,8,9,10}]

Out[6]=

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

In[7]:= NecklacePolynomial[8,m,Cyclic]

Out[7]=

並べ換えの転倒数は逆元のそれに等しい．

In[8]:= (p=RandomPermutation[50]; {Inversions[p], Inversions[InversePermutation[p]]})

Out[8]=

目的が，与えられた性質を持つ最初の部分集合を見つけることなら，すべての部分集合を構成する必要はないので，部分集合を増加の順に生成するのが効率がよい．

In[9]:= Table[UnrankSubset[n,{a,b,c,d}], {n,0,15}]

Out[9]=

グレイ符号では，各部分集合は隣のものからちょうど1元だけ異なっている．最後の8つの部分集合はすべて1を含み，最初の8つはどれも含んでいないことに注目しよう．

In[10]:= GrayCodeSubsets[{1,2,3,4}]

Out[10]=

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

In[11]:= KSubsets[{1,2,3,4,5},3]

Out[11]=

Combinatoricaの並べ換え関数

Combinatoricaの部分集合関数

Combinatoricaの群論関数

分割，結合，ヤング盤

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

ここにあるのは6の分割11個である．逆辞書式順序で与えられていることに注目しよう．

In[12]:= Partitions[6]

Out[12]=

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

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

Out[13]=

フェラーズ図形は，分割をドット・パターンとして表す．ドットをあちこちと動かすことにより分割のクラスの間の全単射を証明するメカニズムが得られるので，フェラーズ図形は分割を視覚化する有用な道具となる．ここでは100のランダムな分割を構成する．

In[14]:= FerrersDiagram[RandomPartition[100]]

Out[14]=

ここで3個の成分への5の各結合はちょうど1度ずつ生成されている．

In[15]:= Compositions[5,3]

Out[15]=

集合分割は整数の分割とは異なり，異なる要素を部分集合に分割することができる方法を示す．これは彩色や群化に便利である．

In[16]:= SetPartitions[3]

Out[16]=

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

In[17]:= Tableaux[{2,2,1}]

Out[17]=

相異なる整数分割を型として反復することにより，一定のサイズの盤全体が構成できる．

In[18]:= Tableaux[3]

Out[18]=

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

In[19]:= NumberOfTableaux[10]

Out[19]=

この型の盤117，123，756，750個すべてが同様の確からしさで選ばれることになる．

In[20]:= TableForm[ RandomTableau[{6,5,5,4,3,2}] ]

Out[20]//TableForm=

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

In[21]:= LongestIncreasingSubsequence[
RandomPermutation[50] ]

Out[21]=

Combinatoricaの整数分割関数

Combinatoricaの集合分割関数

Combinatoricaのヤング盤関数

Combinatoricaの数を返す関数

グラフの表現

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

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

In[22]:= ShowGraph[ CompleteGraph[5] ];

グラフ表現の内部構造はユーザには見えない．辺や頂点の数に続いてグラフが有向か無向かが示されるだけである．

In[23]:= CompleteGraph[5]

Out[23]=

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

In[24]:= TableForm[ToAdjacencyMatrix[CompleteGraph[5]]]

Out[24]//TableForm=

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

In[25]:= Vertices[ CompleteGraph[5] ]

Out[25]=

グラフの頂点の個数はそのグラフの位数と呼ばれる．

In[26]:= V[ CompleteGraph[5] ]

Out[26]=

Mはグラフの中の辺の個数を返す．

In[27]:= M[ CompleteGraph[5] ]

Out[27]=

辺・頂点の色やスタイルは大域的に変更できるので，グラフの外観を完全に変えることのできる柔軟性を提供する．

In[28]:= g = SetGraphOptions[CompleteGraph[4], VertexColor -> Red,
EdgeColor -> Blue]

Out[28]=

各頂点や辺の色・スタイル・ラベル・ウェイトは，グラフの面白い性質をひきたてるように，個々について変更することができる．

In[29]:= ShowGraph[ SetGraphOptions[ CompleteGraph[4],
{{1, 2, VertexColor -> Green, VertexStyle -> Disk[Large]},
{3, 4, VertexColor -> Blue}},
EdgeColor -> Red
] ];

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

In[30]:= ShowGraph[ AddEdge[Star[10], {1,2}] ];

多重辺や自己ループをもつグラフもサポートされている．これは星の各辺が重複している．

In[31]:= ShowGraph[ GraphSum[Star[10], Star[10]] ];

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

In[32]:= TableForm[ ToAdjacencyLists[CompleteGraph[5]] ]

Out[32]//TableForm=

位置の完全グラフにおいて定義される順序対は個ある．

In[33]:= ToOrderedPairs[ CompleteGraph[5] ]

Out[33]=

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

In[34]:= ShowGraph[ InduceSubgraph[CompleteGraph[20],
RandomSubset[Range[20]]] ];

2-部グラフの頂点は，2つの集合に分割し，同じ集合に属する2つの頂点は決して辺で結ばれないようにすることができるという性質がある．2-部グラフの辺を縮退すると，もはや2-部グラフではなくなることがある．縮退によってできた自己ループに注目のこと．

In[35]:= ShowGraph[ Contract[ CompleteGraph[6,6],{1,7} ] ];

グラフの広さ優先探索は，現在の頂点に隣接するすべての頂点を「探検」してから次に移る．単純サイクルでの広さ優先探索は交互に往来を繰り返しながらこのサイクルをとり囲んでいく．

In[36]:= BreadthFirstTraversal[Cycle[20],1]

Out[36]=

深さ優先探索では，頂点の長男の子供たちを訪問してからその兄弟のところを訪れる．深さ優先探索は上述の広さ優先探索とは異なり，サイクルをまっすぐに進む．

In[37]:= DepthFirstTraversal[Cycle[20], 1]

Out[37]=

グラフの描画や埋め込みの相異は，そのグラフの構造の異なった部分を示すことがある．格子グラフのデフォルトの埋め込みは1辺の上の頂点全体からのランク付き埋め込みである．中央の頂点からのランク付けはこれとは異なる．しかし興味深い描画を生ずる．

In[38]:= ShowGraph[
RankedEmbedding[GridGraph[5,5],{13}]];

木の放射状埋め込みは平面グラフであることが保証されているが，放射状埋め込みはそれ以外の任意のグラフにも用いることができる．これはランダムな木についての放射状埋め込みである．

In[39]:= ShowGraph[ RandomTree[10] ];

任意に根を選ぶことにより，どんな木も根付き木として表現できる．

In[40]:= ShowGraph[ RootedEmbedding[RandomTree[10],1] ];

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

In[41]:= ShowGraph[
SpringEmbedding[
GraphJoin[EmptyGraph[2], CompleteGraph[7]]]];

Combinatoricaのグラフ変更関数

Combinatoricaのグラフ形式解釈関数

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

Combinatoricaのグラフラベル・ウェイト関数

Combinatoricaのグラフ描画関数

グラフの生成

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

2つの連結グラフの合併は2つの連結成分を持つ．

In[42]:= ShowGraph[ GraphUnion[ CompleteGraph[3],
CompleteGraph[5,5] ] ];

グラフの積は非常に興味深いものとなりうる．積の埋め込みはその構造をよく表すように設計されており，第1のグラフを縮めて第2にグラフの中の各頂点の位置へこれを平行移動することでつくられる．

In[43]:= ShowGraph[ GraphProduct[ CompleteGraph[3],
CompleteGraph[5] ] ];

グラフの線グラフは，の各辺に対しての頂点があり，の2つの辺が頂点を共有するとき，そのときに限っての辺がある．

In[44]:= ShowGraph[ LineGraph[CompleteGraph[5]] ];

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

In[45]:= ShowGraph[ CirculantGraph[21,
RandomKSubset[Range[10],3]]];

グラフジェネレータの中には，バイナリアルファベットの長さ5の部分文字列をすべてコード化する下のde Bruijnグラフあるいはシフトレジスタグラフのような，自己ループをもつ有向グラフを生成するものもある．

In[46]:= ShowGraph[ DeBruijnGraph[2,5] ];

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

In[47]:= ShowGraph[ Highlight[Hypercube[4],
{Partition[HamiltonianCycle[Hypercube[4]], 2, 1]}] ];

いくつかの組込みのグラフ構成関数にはパラメータがなく，1つの面白いグラフのみを構成する．FiniteGraphsはそのような関数を1つのリストにまとめるので便利である．ShowGraphArrayを使うと，1つのウィンドウに複数のグラフが表示できる．

In[48]:= ShowGraphArray[Partition[FiniteGraphs,5,5]]

Combinatoricaのグラフ構成関数

グラフの性質

グラフ理論は，グラフに固有の性質，すなわち，グラフの不変量の研究である．興味深い性質には，連結度，サイクル構造，および彩色数などがある．ここでは，グラフの不変量の計算方法を論じる．

無向グラフが連結であるとは，頂点の任意のペア（対）の間に路が存在するときである．連結グラフから辺を1本除去すると連結でなくなることがある．そのような辺は橋と呼ばれる．

In[49]:= ConnectedQ[ DeleteEdge[ Star[10], {1,10} ] ]

Out[49]=

GraphUnionを用いると不連結グラフがつくれる．

In[50]:= ConnectedComponents[ GraphUnion[CompleteGraph[3],
CompleteGraph[4]] ]

Out[50]=

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

In[51]:= ShowGraph[ OrientGraph[Wheel[10]] ];

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

In[52]:= BiconnectedComponents[
RealizeDegreeSequence[{4,4,3,3,3,2,1}] ]

Out[52]=

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

In[53]:= ArticulationVertices[ Star[10] ]

Out[53]=

木のすべての辺は橋である．

In[54]:= Bridges[ RandomTree[10] ]

Out[54]=

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

In[55]:= VertexConnectivity[Wheel[10]]

Out[55]=

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

In[56]:= EdgeConnectivity[CompleteGraph[3,4]]

Out[56]=

2つの団の位数が単に逆転されているだけなので，これら2つの完全2-部グラフは同型である．ここでは同型のものがすべて返される．

In[57]:= Isomorphism[CompleteGraph[3,2], CompleteGraph[2,3], All]

Out[57]=

グラフが自己補充的であるとは，それがそれ自身の補グラフに同型であるときをいう．最小の自明でない自己補充的グラフは4頂点の上の路，および5頂点の上のサイクルである．

In[58]:= SelfComplementaryQ[ Cycle[5] ] &&
SelfComplementaryQ[ Path[4] ]

Out[58]=

可能な辺のうち半数を持つ有向グラフは，ほとんど確実にサイクルを含む．有向無サイクル・グラフは，しばしばDAGと呼ばれる．

In[59]:= AcyclicQ[
RandomGraph[100, 0.5, Type -> Directed]
]

Out[59]=

グラフの内周は最短サイクルの長さである．籠は指定された内周をもつ最小の正則（ここでは3）グラフである．

In[60]:= Girth[ CageGraph[3, 6] ]

Out[60]=

オイラー・サイクルは，グラフのすべての辺を完全に巡る周遊路である．2-部グラフのオイラー・サイクルは，2つの団の間を飛び跳ねて，行ったり来たりする．

In[61]:= EulerianCycle[ CompleteGraph[4,4] ]

Out[61]=

Combinatoricaのグラフ叙述関数

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

In[62]:= HamiltonianCycle[CompleteGraph[3,3], All]

Out[62]=

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

In[63]:= ShowGraph[
g = MakeGraph[Range[8],(Mod[#1,#2]==0)&],
VertexNumber -> True
];

整除関係は反射的，推移的，かつ反対称的であるので，それは反順序である．

In[64]:= PartialOrderQ[g]

Out[64]=

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

In[65]:= ShowGraph[TransitiveReduction[g], VertexNumber -> True];

ハッセ図形は，部分集合の上の包含によって定められる半順序であるブール代数の格子構造を明らかに示している．

In[66]:= ShowGraph[
HasseDiagram[MakeGraph[Subsets[4],
((Intersection[#2,#1]===#1)&&(#1 != #2))&]]
];

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

In[67]:= TopologicalSort[
MakeGraph[Range[10],(#1 > #2)&] ]

Out[67]=

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

In[68]:= ChromaticPolynomial[
GraphUnion[CompleteGraph[2,2], Cycle[3]], z ]

Out[68]=

Combinatoricaのグラフ不定量関数

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

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

格子グラフの最短路生成木はManhattan距離を用いて定義される．ここで，座標との点の間の距離はである．

In[69]:= ShowGraph[
ShortestPathSpanningTree[
GridGraph[5,5],1] ];

重みのないグラフにおいては，どの頂点のペアの間にも多くの異なる最短路がありうる．2つの向かい合った角の間のこの路はずっと右まで進み，そのあとずっと上まで進む．

In[70]:= ShortestPath[GridGraph[5,5],1,25]

Out[70]=

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

In[71]:= ShowGraph[ MinimumSpanningTree[ CompleteGraph[6,6,6] ] ];

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

In[72]:= NumberOfSpanningTrees[CompleteGraph[10]]

Out[72]=

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

In[73]:= NetworkFlow[ CompleteGraph[4,4], 1, 8 ]

Out[73]=

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

In[74]:= BipartiteMatching[ Cycle[8] ]

Out[74]=

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

In[75]:= MaximalMatching[CompleteGraph[8]]

Out[75]=

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