About: 独立集合

グラフ理論における独立集合（どくりつしゅうごう、英: independent set）または安定集合（英: stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。 最大独立集合 (maximum independent set) は与えられたグラフ G の最も大きな独立集合であり、その大きさを α(G) と表記する。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。 最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。