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]はそのような集合をすべて求める．
必ずしも最大ではない独立頂点集合は，FindIndependentVertexSetを使って直接求めることはできないが，すべての最大独立頂点集合の部分集合の集合の和集合を取ることで，単純化して列挙することができる．
IndependentVertexSetQを使い，頂点集合が独立かどうかを（それが極大であるという条件なしに）調べることができる．独立頂点集合は，頂点被覆（FindVertexCoverを参照のこと）の補集合に対応する．グラフの極大頂点集合は，GraphComplement上の極大クリークに等しい（FindCliqueを参照のこと）．FindIndependentEdgeSetはFindIndependentVertexSetと同じ概念を辺に適用する．結果の独立辺集合もまた「マッチング」として知られている．

例題

すべて開くすべて閉じる

例 (2)

グラフ中の独立頂点集合を求める：

Wolfram Language code: g = [image];

Wolfram Language code: FindIndependentVertexSet[g]

頂点集合を示す：

Wolfram Language code: HighlightGraph[g, %, GraphHighlightStyle -> "Thick"]

すべての独立集合を求める：

Wolfram Language code: g = ExampleData[{"NetworkGraph", "ZacharyKarateClub"}];

Wolfram Language code: FindIndependentVertexSet[g, Infinity, All]//Short