algorithm - n個の頂点を持つグラフ-すべての可能なグラフの組み合わせを印刷する方法

Question

グラフの頂点の数をnに設定するとします。（ユーザー入力などで設定できます）

エッジを使用して頂点を接続する可能性のあるすべてのケースを印刷したいと思います。（したがって、n個の頂点のすべての可能な（単純な）接続されたグラフを印刷したいと思います。）

また、それぞれの場合について、それぞれの頂点の次数を印刷したいと思います。

Answer 1

素朴ですが単純な解決策は、考えられるすべてのグラフを作成し、接続されていないグラフを除外することです。

可能なすべてのエッジのセットを作成します。それらがありn(n-1)/2、これがセットのサイズになります。

必要なセットのべき集合を見つけます。このべき集合は、作成できるすべての可能なグラフを表します。

ウィキペディアの記事には、セットのべき集合を計算するためのアルゴリズムも記載されています。この投稿では、この問題についても説明しています（java）

作成されたサブセットごとに、接続されているかどうかを確認します。これは、 BFSなどの検出アルゴリズムを使用して実行できます。グラフは、単一の（ランダムな）ソースから開始したときに、BFSがすべての頂点を検出した場合にのみ接続されます。