この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月）翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。

英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。

万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。

信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。

履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。

翻訳後、{{翻訳告知|en|Independent set (graph theory)|…}}をノートに追加することもできます。

Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

24個の頂点からなるこのグラフで、青い9個の頂点の集合が極大独立集合である。

グラフ理論における独立集合（どくりつしゅうごう、英: independent set）または安定集合（英: stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。

極大独立集合 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。

最大独立集合 (maximum independent set) は与えられたグラフ G の最も大きな独立集合であり、その大きさを α(G) と表記する[1]。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。

与えられたグラフが特定の大きさの独立集合を持つかどうかを判定する問題を独立集合問題と呼ぶ。これは計算上、そのグラフが特定の大きさのクリークを持つかどうかの判定と等価である。このことは、グラフが大きさ k の独立集合を持つとき、その補グラフ（頂点は同じだが、辺が相補的なグラフ）は大きさ k のクリークを持つという事実から導かれる。独立集合（およびクリーク）の決定問題は、NP完全問題であることが知られている。

最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。
特性
他のグラフ関連パラメータとの関係

ある集合が独立であるとは、そのグラフの補グラフのクリークと同値であり、2つの概念は相補的である。実際、十分大きなグラフで大きなクリークがない場合、独立集合は大きくなる。このあたりはラムゼー理論の主要研究テーマである。

ある集合が独立であるとき、その補集合は頂点被覆である。最大独立集合の大きさ α(G) と最小頂点被覆の大きさ β(G) の合計はそのグラフの頂点数となる。

2部グラフでは、最大独立集合の頂点数は最小辺被覆の辺数と等しい。
極大独立集合

他の独立集合の部分集合になっていない独立集合を「極大 (maximal)」であるという。そのような集合は支配集合 (dominating set) でもある。グラフは最大で 3n/3 個の極大独立集合を持つが、多くのグラフの極大独立集合の個数はそれより少ない。

n-頂点の閉路グラフでの極大独立集合の個数はペラン数列で与えられ、n-頂点の道での極大独立集合の個数はパドヴァン数列で与えられる[2]。したがって、どちらの個数もプラスチック数 1.324718 のべき乗と比例する。NP困難な問題を扱うアルゴリズムでは、極大独立集合をリストアップする処理をサブルーチンとして使うことが多い。
関連項目

辺独立集合をマッチングと呼ぶ。

脚注・出典^ Godsil, Chris; Gordon Royle (2004) [1949]. Algebraic Graph Theory. New York: Springer. p. 3. .mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation.cs-ja1 q,.mw-parser-output .citation.cs-ja2 q{quotes:"「""」""『""』"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free a,.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited a,.mw-parser-output .id-lock-registration a,.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription a,.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:#d33}.mw-parser-output .cs1-visible-error{color:#d33}.mw-parser-output .cs1-maint{display:none;color:#3a3;margin-left:0.3em}.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}ISBN 0-387-95220-9