グラフがあるとしましょう。
そしてこのグラフから回路Kを作りたいグラフのサイズが2以上の独立した集合を持つ場合、Kの入力が真になるように入力を設定できます。 私はこれをどうやってやるかについてインターネットやYouTubeでいくつかのまともなことを見たことがあります。
私の考えたプロセスは、次のようなものでした。回路に入力としてエッジを取り、少なくとも1つのエッジが欠けている場合は出力1（true）を持つようにします（このエッジは独立集合です）。
しかし、もし私が正直であれば、頭を包み込むのに苦労します。
回答：
回答№1は0あなたのアプローチは概念的には正しいが、そこにはさらに簡単な方法：グラフの辺を数える。 N個のノードで、| E |の場合<N *（N-1）/ 2の場合、少なくとも1つの独立したサイズのセット> = 2があります。
検索するには 最大 独立集合、変換トリックがあります概念を比較するのは比較的簡単です。グラフを反転する：辺以外の辺と辺をすべて切り替えます。たとえば、投稿されたグラフには6つの辺のうち4つが含まれています。 DB そして DC.
結果のグラフを見て、最大のクリークを見つけます（これにはたくさんの資料があります）。その最大のクリークは、最大の独立グラフです。