編集24個の頂点からなるこのグラフで、青い9個の頂点の集合が極大独立集合である。set)は、1つのグラフ内で互いに隣接していない頂点の集合である。任意の2つの頂点をつなぐ辺が存在しない場合をいう。独立集合の大きさとはその中の頂点の個数である。任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。与えられたグラフが特定の大きさの独立集合を持つかどうかを判定する問題を独立集合問題と呼ぶ。これは計算上、そのグラフが特定の大きさのクリークを持つかどうかの判定と等価である。クリークを持つという事実から導かれる。独立集合(およびクリーク)の決定問題は、NP完全問題であることが知られている。最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。他のグラフ関連パラメータとの関係編集ある集合が独立であるとは、そのグラフの補グラフのクリークと同値であり、2つの概念は相補的である。実際、十分大きなグラフで大きなクリークがない場合、独立集合は大きくなる。このあたりはラムゼー理論の主要研究テーマである。ある集合が独立であるとき、その補集合は頂点被覆である。合計はそのグラフの頂点数となる。(maximal)」であるという。個の極大独立集合を持つが、多くのグラフの極大独立集合の個数はそれより少ない。n-頂点の閉路グラフでの極大独立集合の個数はペラン数列で与えられ、n-頂点の道での極大独立集合の個数はパドヴァン数列で与えられる[2]。3.0のもとで利用可能です。プライバシーデスクトップ。