2

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

1
  • 型の個数を知りたいのではなくて、どんな型があるのか列挙したいという問題であっていますでしょうか?
    – nekketsuuu
    3月17日 0:35

1 件の回答 1

2

難問だと思いますが結果は 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

1
  • ありがとうございます。矢張りというか当然というかとっくに検討されているのですよね。検索が甘かったです。 3月18日 8:44

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。