アップグレード情報：

Combinatorica`

バージョン10の時点で，Combinatorica に装備されている機能のほとんどがWolframシステムに実装された．

Combinatorica はグラフ理論や置換等の分野における多数の機能を提供してきた．バージョン10では，そのような機能のほとんどがネイティブにWolframシステムに実装されている．名称で多少重なる部分があるが，ネイティブの実装では，基本的に多くの点で異なっている．

例えば，Combinatorica のGraphオブジェクトはPartのような式の操作関数で直接引き離すことのできる通常の Mathematica 式であった．しかし，Wolframシステムへの実装では，原子オブジェクトであり，アクセサ関数からしか変更できない．この機能により，Wolframシステムは描画のヒントおよびインタラクティブなグラフ操作をサポートする他の情報を透過的に添付することができる．

上記のような基本的な違いにより，Combinatorica をロードすると新機能がオーバーライドされ，昔のGraph式との互換性を提供する．これは新しい関数を隠蔽するため，昔のコードが実行できるようになる．ほとんどの場合，新しい実装と Combinatorica を混用すべきではない．混用が必要な場合は，System`GraphまたはCombinatorica`Graphのように完全なコンテキスト名を使うことで同時に2つのバージョンが使えるようになる．

Wolframシステムの機能の概要はグラフとネットワークガイドを参照されたい．

グラフ表現と操作

グラフは有向および無向辺のリストにより入力されるようになった．表示関数は必要とされない．Graphicsオブジェクトのように，フロントエンドで直接描画される．

Version 7.0 << Combinatorica` ShowGraph[Graph[{{{1, 2}}, {{2, 3}}}, {{{0, 0}}, {{1, 1}}, {{2, 0}}}]]

頂点の位置はオプションである．

有向辺は辺のリストで指定される．

Version 7.0 << Combinatorica` ShowGraph[ Graph[{{{1, 2}}, {{2, 3}}}, {{{0, 0}}, {{1, 1}}, {{2, 0}}}, Directed -> True]]

グラフは部分を強調するためにスタイルを変更して描画することができる．シンタックスは同一ではないが，簡単に適用することができる．

Version 7.0 << Combinatorica` ShowGraph[ Highlight[CompleteGraph[5], {{1, 2, 3, {1, 2}, {2, 3}}, {{1, 3}}}, HighlightedEdgeColors -> {Red, Orange}]]

グラフは隣接行列として入力することができる．

Version 7.0 << Combinatorica` ShowGraph[ FromAdjacencyMatrix[{{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0}}]]

隣接行列は疎な配列である．

Version 7.0 << Combinatorica` ToAdjacencyMatrix[Wheel[5]]

現時点では，多重グラフ（頂点間に2つ以上の辺があるもの）は有向グラフの特殊な場合以外はサポートされていない．この特殊な場合とは，それぞれの向きの単独の辺が指定できる場合である．非対称行列は自動的に有向であると理解される．理解されない場合はオプションDirectedEdgesを使う．

Version 7.0 << Combinatorica` ShowGraph[ FromAdjacencyMatrix[{{0, 1, 1, 1}, {1, 0, 1, 0}, {1, 1, 0, 1}, {1, 0, 1, 0}}, Type -> Directed]]

重み付きの隣接行列の場合はWeightedAdjacencyGraphを使う．辺が存在しない場合は，ゼロではなく無限の重みにより指定する．

Version 7.0 << Combinatorica` GetEdgeWeights[ SetEdgeWeights[ FromAdjacencyMatrix[{{0, 1, 1}, {1, 0, 1}, {1, 1, 0}}], {2, 1, 2}]]

Combinatoricaバージョン 10
AddEdge[g, e]EdgeAdd[g,e]
AddEdges[g,{e1,e2,…}]EdgeAdd[g, {e1,e2,…}]
AddVertex[g,v]VertexAdd[g,v]
AddVertices[g, {v1,v2,…}]VertexAdd[g,{v1,v2,…}]
DeleteEdge[g,e]EdgeDelete[g,e]
DeleteEdges[g,{e1,e2,…}]EdgeDelete[g,{e1,e2,…}]
DeleteVertex[g,v]VertexDelete[g,v]
DeleteVertices[g,{v1,v2,…}]VertexDelete[g,{v1,v2,…}]
InduceSubgraph[g,{v1,v2,…}]Subgraph[g,{v1,v2,…}]
MakeDirected[g]DirectedGraph[g]
MakeSimple[g]UndirectedGraph[SimpleGraph[g]]
MakeUndirected[g]UndirectedGraph[g]
ReverseEdges[g]ReverseGraph[g]

Wolframシステムでは通常グラフ機能は頂点の名前を指しているが，Combinatorica では使用される頂点の指標あるいは座標である．

Version 7.0 << Combinatorica` ShowGraph[AddEdges[AddVertex[Wheel[5]], {{2, 6}, {3, 6}}]]

Combinatorica のMakeSimpleによりグラフは無向になる．これはWolframシステムでは別の操作である．

Combinatoricaバージョン 10
GraphComplement[g]GraphComplement[g]
GraphDifference[g1,g2]GraphDifference[g1,g2]
GraphIntersection[g1,g2,…]GraphIntersection[g1,g2,…]
MakeSimple[GraphPower[g,n]]GraphPower[g,n]
MakeSimple[GraphSum[g1,g2,…]]GraphUnion[g1,g2,…]
GraphUnion[g1,g2,…]GraphDisjointUnion[g1,g2,…]
LineGraph[g]LineGraph[g]

グラフを組み合せる操作のほとんどが実装されている．その中には，Wolframシステムが，対応する Combinatorica での操作の簡単なグラフを作成するものもある．Wolframシステムでは和集合および総和は定義が異なる点に注意すること．グラフは同じ数の頂点から始まらなければならないという条件はなくなった．

Version 7.0 << Combinatorica` ShowGraph[MakeSimple[GraphSum[Cycle[6], AddVertex[Cycle[5]]]]]

グラフ特性

Combinatoricaバージョン 10
AcyclicQ[g]AcyclicGraphQ[g]
BipartiteQ[g]BipartiteGraphQ[g]
CompleteQ[g]CompleteGraphQ[g]
ConnectedQ[g]ConnectedGraphQ[g]
EmptyQ[g]EmptyGraphQ[g]
EulerianQ[g]EulerianGraphQ[g]
HamiltonianQ[g]HamiltonianGraphQ[g]
IndependentSetQ[g,{v1,v2,…}]IndependentVertexSetQ[g,{v1,v2,…}]
IsomorphicQ[g]IsomorphicGraphQ[g]
SelfLoopsQ[g]!LoopFreeGraphQ[g]
SimpleQ[g]SimpleGraphQ[g]
TreeQ[g]TreeGraphQ[g]
UndirectedQ[g]UndirectedGraphQ[g]
UnweightedQ[g]!WeightedGraphQ[g]
VertexCoverQ[g,{v1,v2,…}]VertexCoverQ[g,{v1,v2,…}]

グラフの属性の多くは，現在異なる名前でサポートされているが，中にはWeightedGraphQのように属性の反対の意味を使っているものもある．

Version 7.0 << Combinatorica` EulerianQ[CompleteGraph[5]]

Combinatoricaバージョン 10
ConnectedComponents[g]ConnectedComponents[g]
Degrees[g]VertexDegree[g]
DegreeSequence[g]Reverse[Sort[VertexDegree[g]]]
Diameter[g]GraphDiameter[g]
Eccentricity[g]VertexEccentricity[g]
GraphCenter[g]GraphCenter[g]
InDegree[g,v]VertexInDegree[g,v]
M[g]EdgeCount[g]
OutDegree[g,v]VertexOutDegree[g,v]
Radius[g]GraphRadius[g]
V[g]VertexCount[g]

Version 7.0 << Combinatorica` Diameter[ButterflyGraph[5]]

グラフアルゴリズム

Combinatoricaバージョン 10
EulerianCycle[g]FindEulerianCycle[g]
HamiltonianCycle[g]FindHamiltonianCycle[g]
MaximumClique[g]FindClique[g]
MaximumIndependentSet[g]FindIndependentVertexSet[g]
ShortestPath[g,s,e]FindShortestPath[g,s,e]
MinimumVertexCover[g]FindVertexCover[g]

Wolframシステムは巡回セールスマン問題の機能も実装しているが，シンタックスはグラフの表現に対して指向されているものではない．FindShortestTourを参照のこと．

経路と閉路ガイドも参照のこと．

出力も形式が異なる場合がある．例えば，FindEulerianCycleは辺のリストを返すが，EulerianCycleは頂点のリストを返す．

標準グラフ

Combinatoricaバージョン 10
ButterflyGraph[n]ButterflyGraph[n]
CirculantGraph[n,j]CirculantGraph[n,j]
CompleteBinaryTree[n]KaryTree[n]
CompleteGraph[n]CompleteGraph[n]
CompleteKPartiteGraph[n1,n2,…]CompleteGraph[{n1,n2,…}]
CompleteKaryTree[n,k]KaryTree[n,k]
Cycle[n]CycleGraph[n]
DeBruijnGraph[n, m]DeBruijnGraph[n, m]
EmptyGraph[n]Graph[Range[n],{}]
ExactRandomGraph[n,m]RandomGraph[{n,m}]
FunctionalGraph[f,v]Graph[(#f[#])&/@v]
GeneralizedPetersenGraph[n,k]PetersenGraph[n,k]
GridGraph[n,m]GridGraph[{n,m}]
Harary[k,n]HararyGraph[k,n]
Hypercube[n]HypercubeGraph[n]
KnightsTourGraph[n,m]KnightTourGraph[n,m]
Path[n]PathGraph[Range[n]]
RandomGraph[n,p]RandomGraph[BernoulliGraphDistribution[n,p]]
RealizeDegreeSequence[s]RandomGraph[DegreeGraphDistribution[s]]
RegularGraph[k,n]RandomGraph[DegreeGraphDistribution[Table[k,{n}]]]
Star[n]StarGraph[n]
Turan[n,p]TuranGraph[n,p-1]
Wheel[n]WheelGraph[n]

値によりパラメータ化される名前付きの標準グラフはいろいろある．Combinatorica のものにはWolframシステムにも同等のものがある．名前とシンタックスはわずかに異なる場合がある．頂点の指標も異なる場合がある．

Version 7.0 << Combinatorica` ShowGraph[Turan[5, 3]]

Combinatoricaバージョン 10
CageGraph[k,r]GraphData[{"Cage",{k,r}}]
ChvatalGraphGraphData["ChvatalGraph"]
CoxeterGraphGraphData["CoxeterGraph"]
CubicalGraphGraphData["CubicalGraph"]
CubeConnectedCycle[n]GraphData[{"CubeConnectedCycle", n}]
DodecahedralGraphGraphData["DodecahedralGraph"]
FolkmanGraphGraphData["FolkmanGraph"]
FranklinGraphGraphData["FranklinGraph"]
FruchtGraphGraphData["FruchtGraph"]
GroetzschGraphGraphData["GroetzschGraph"]
HeawoodGraphGraphData["HeawoodGraph"]
HerschelGraphGraphData["HerschelGraph"]
IcosahedralGraphGraphData["IcosahedralGraph"]
LeviGraphGraphData["LeviGraph"]
McGeeGraphGraphData["McGeeGraph"]
MeredithGraphGraphData["MeredithGraph"]
MycielskiGraph[n]GraphData[{"Mycielski",n}]
NoPerfectMatchingGraphGraphData["NoPerfectMatchingGraph"]
NonLineGraphsGraphData["Beineke","Graph"]
OctahedralGraphGraphData["OctahedralGraph"]
OddGraph[n]GraphData[{"Odd",n}]
PetersenGraphGraphData["PetersenGraph"]
RobertsonGraphGraphData["RobertsonGraph"]
SmallestCyclicGroupGraphGraphData["SmallestCyclicGroupGraph"]
TetrahedralGraphGraphData["TetrahedralGraph"]
ThomassenGraphGraphData["ThomassenGraph34"]
TutteGraphGraphData["TutteGraph"]
Uniquely3ColorableGraphGraphData["UniquelyThreeColorableGraph"]
UnitransitiveGraphGraphData["DesarguesGraph"]
WaltherGraphGraphData["WaltherGraph"]

他の標準グラフの多くはパラメータを取らない（CageGraphの場合は限られた範囲のパラメータしか取らない）．これらはバージョン10のGraphDataデータベースで見付けることができる．

Version 7.0 << Combinatorica` ShowGraph[FruchtGraph]

場合によってはパラメータ化されたものがWolframシステムにはまだ実装されていないこともあるが，GraphDataに部分集合がある．例えば，CubeConnectedCycleは値4から8まではGraphDataで定義されており，MycielskiGraphは値5から11まで定義されている．

Version 7.0 << Combinatorica` ShowGraph[MycielskiGraph[5]]

Combinatorica 関数のFiniteGraphsはパラメータ化されていない名前付きグラフのリストを返す．GraphData[]はGraphDataが知っている名前のリストを返すので，同等のものと考えることができる．しかし，これはFiniteGraphs!よりもわずかに長いリストである．

BooleanAlgebra
CodeToLabeledTree
HasseDiagram
IntervalGraph
LabeledTreeToCode
ListGraphs
MakeGraph
PermutationGraph
RandomTree
ShuffleExchangeGraph
VertexConnectivityGraph

名前付きグラフの一部にはまだWolframシステムに直接対応するものがない．（乱数木生成の例についてはTreeGraphのドキュメントを参照のこと．まだ可能であるが，Combinatorica が使用するメソッドではまだである．）