|
グラフ理論における独立集合（どくりつしゅうごう、）または安定集合（）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 ''V'' で、''V'' の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが ''V'' の元である。独立集合の大きさとはその中の頂点の個数である。 極大独立集合 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。 最大独立集合 (maximum independent set) は与えられたグラフ ''G'' の最も大きな独立集合であり、その大きさを ''α''(''G'') と表記する。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。 与えられたグラフが特定の大きさの独立集合を持つかどうかを判定する問題を独立集合問題と呼ぶ。これは計算上、そのグラフが特定の大きさのクリークを持つかどうかの判定と等価である。このことは、グラフが大きさ ''k'' の独立集合を持つとき、その補グラフ（頂点は同じだが、辺が相補的なグラフ）は大きさ ''k'' のクリークを持つという事実から導かれる。独立集合（およびクリーク）の決定問題は、NP完全問題であることが知られている。 最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。 == 特性 == === 他のグラフ関連パラメータとの関係 === ある集合が独立であるとは、そのグラフの補グラフのクリークと同値であり、2つの概念は相補的である。実際、十分大きなグラフで大きなクリークがない場合、独立集合は大きくなる。このあたりはラムゼー理論の主要研究テーマである。 ある集合が独立であるとき、その補集合は頂点被覆である。最大独立集合の大きさ ''α''(''G'') と最小頂点被覆の大きさ ''β''(''G'') の合計はそのグラフの頂点数となる。 2部グラフでは、最大独立集合の頂点数は最小辺被覆の辺数と等しい。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「独立集合」の詳細全文を読む スポンサード リンク
|