FindIndependentVertexSet

FindIndependentVertexSet[g]
グラフ g で頂点数が最大の独立頂点集合を求める.

FindIndependentVertexSet[g,n]
最高で n 個の頂点を持つ独立頂点集合を求める.

FindIndependentVertexSet[g,{n}]
厳密に n 個の頂点を持つ独立頂点集合を求める.

FindIndependentVertexSet[g,{nmin,nmax}]
個から 個までの頂点を持つ独立頂点集合を求める.

FindIndependentVertexSet[g,nspec,s]
最高で s 個の独立頂点集合を求める.

FindIndependentVertexSet[{g,v},]
頂点 v のみを含む独立集合を求める.

詳細詳細

予備知識
予備知識

  • FindIndependentVertexSetは,グラフ中の1つあるいは複数の最大独立頂点集合を求め,それらを頂点リストのリストとして返す.ここで,独立頂点集合は集合中のどの頂点ペアも辺で結ばれていないような頂点集合である.独立頂点集合は,金融,符号化理論,地図のラベル付け,パターン認識,ソーシャルネットワーク,分子生物学,スケジューリング等に応用される.
  • 独立頂点集合には,最大と極大の特に重要な2つのタイプがある.これらは等価ではない点に注意のこと.最大独立頂点集合は,指定されたグラフの可能な最大数の頂点を含む頂点集合のことである.これに対し,極大独立頂点集合は,1つあるいは複数の隣接頂点を含むことで拡張することができない,つまり,より大きな独立頂点集合の部分集合ではない頂点集合のことである.最大独立頂点集合は,したがって,常に極大であるが,逆は必ずしも真ではない.
  • FindIndependentVertexSetは,異なるサイズの最大独立頂点集合を求めることができる.FindIndependentVertexSetは,指定されたサイズの単一の最大独立頂点集合,指定された数の極大独立頂点集合,あるいはそのようなすべての集合も求めることができる.
  • FindIndependentVertexSet[g]は,グラフ g の単一の最大独立頂点集合を,FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],s]は最高で s 個の.FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All]はそのようなすべての集合を求める.グラフ g の最大独立頂点集合の大きさは,その(頂点)独立数として知られている.指定されたグラフの最大独立頂点集合(したがって独立数)を求める問題は,NP完全である.つまり,計算が指数的に遅くなる.
  • FindIndependentVertexSet[g,Infinity]は,グラフ g の単一の最大独立頂点集合を求め,FindIndependentVertexSet[g,Infinity,s]は最高で s 個,FindIndependentVertexSet[g,Infinity,All]はそのような集合をすべて求める.
  • IndependentVertexSetQを使い,頂点集合が独立かどうかを(それが最大であるという条件なしに)調べることができる.独立頂点集合は,頂点被覆(FindVertexCoverを参照のこと)の補集合に対応する.グラフの最大頂点集合は,GraphComplement上の最大クリークに等しい(FindCliqueを参照のこと).FindIndependentEdgeSetFindIndependentVertexSetと同じ概念を辺に適用する.結果の独立辺集合もまた「マッチング」として知られている.
2010年に導入
(8.0)
| 2014年に修正
(10.0)