グラフアルゴリズムですか？

Question

グラフを2つのサブグラフにグループ化できるかどうかを確認したい場合は、どのような方法が最も効率的でしょうか。それぞれのサブグラフで各ノードが他のすべてのノードに接続されています。ここの例では、グラフは4つのノードと5つのノードからなる2つのサブグラフであり、各サブグラフにおいて、各ノードはすべての他のノードに接続されている。私はグラフを与えられていると仮定し、私は上記の事実が成り立つかどうか、それを行うための最も効率的なやり方やアルゴリズムは何かをチェックすることです。

Answer 1

これはclique problemとして知られています。 cliqueは、サブセット内の2つの頂点がすべて元のグラフに接続される（つまり、完全なサブグラフを形成する）頂点のサブセットです。すべての最大クリーク（より大きいクリークの一部ではないクリーク）をリストするアルゴリズムを求めています。これにはさまざまなアルゴリズムがあります。通常使用されるものはBron-Kerbosch algorithmです。グラフの頂点の数がnである最悪ケースの実行時間がOです

グラフに特殊な構造（たとえば、あなたの例ではない平面）がある場合は、他のアルゴリズムも適用できます。

EDIT：実際には、グラフが正確に2つのクリークに分割できるかどうかは、this threadで説明されているように、より効率的なアルゴリズムがあります（質問の重複となります）。