

例えば頂点が3個のグラフの場合、それが単純で無向グラフでラベル無しで連結となると2通りだと直ぐに分かる。でも4個となるとイメージしても厄介だし5個だと紙と鉛筆を使っても怪しい。そこでプログラミングで列挙してみたいと思ったのだけどコレが厄介。連結の判断は兎も角、同型の判別が大変。接続行列だと頂点5個でも単純に2^10通りある。連結だからもう少しは減らせるとしても。頂点が10個だともう数的に大変なわけですが、何とか上手い手はないものでしょうか。  
無闇に接続行列を虱潰しに確認するのは大変そう。だからといって候補を上げる段階で上手く絞り込みながらというのも考えが纏まりません。例えば頂点が5個や6個の場合で良いので上手い手法を教えて下さい。


CC BY-SA 4.0
2023-03-16T11:18:09.137
94205
2023-03-17T00:35:18.237
2023-03-17T00:35:18.237
19110
35515
question
アルゴリズム グラフ理論
ラベル無し連結単純無向グラフの型の列挙は？


難問だと思いますが結果は <https://oeis.org/A001349> にあるので文献を漁るのがよさそうです

頂点数0から10はこうなってます

0 1  
1 1  
2 1  
3 2  
4 6  
5 21  
6 112  
7 853  
8 11117  
9 261080  
10 11716571


CC BY-SA 4.0
2023-03-16T23:20:01.290
94214
2023-03-16T23:20:01.290
292
94205
answer