連結な単純無向グラフ​において，頂点が7つ​のグラフをすべて出力​するにはどうすればよ​いですか？

・実現したいこと

私がしたいことは，連結な単純無向グラフにおいて，頂点が7つのときのグラフをすべて出力することです．

具体的にすべて出力するというのがどういうことかというと，例えば頂点が3つの場合，以下の4つを出力するということです．

頂点が3つの場合は，グラフの総数が少ないため手動でグラフを作成できるのですが，

頂点が7つの場合は，グラフの総数がとても多く手動でグラフをすべて作成するのは難しいので，

プログラミングでどうにか自動化できないか悩んでおります．

・今まで試したこと

そこで私は，頂点が3つの場合にすべてのグラフが出力できないか考えました．

まず，頂点が3つの場合は辺は最大3つあるので，

V = 1:3
E = 2
C = nchoosek(V,E)

として辺を3つ出力しました．結果は下のようになり，各行がグラフの辺を表しています．

C =

     1     2
     1     3
     2     3

ここまではよかったのですが，ここから辺をグラフに代入する方法がわからなくなりました．

求めた行列Cを用いて，下のようなグラフが自動的に出力されるプログラムが書ければいいのですが，

G1=graph([1 1], [2 3])
G2=graph([1 2], [2 3])
G3=graph([1 2], [3 3])

MATLABを使い始めたばかりで，どのようにプログラムを書けばいいのかわかりませんでした．

よろしくお願いします．

Answer 1

[Atsushi Ueno]

V = 1:3
E = 2
C = nchoosek(V,E)

この方法も良いかなと思ったのですが、7頂点の内から何個取って繋ぐかを機械的に判断する事は難しいと思いました。網羅的にするなら隣接行列で指定した方が簡単に実装できそうだと思いました。

無向エッジをもつグラフ - MATLAB - MathWorks 日本

graph関数によるグラフの定義方法は大きく分けて「始点と終点の指定」と「隣接行列の指定」の2種類あります。私は「隣接行列の指定」を選び、対角成分(ループ)を除く上三角部に1(辺有り)と0(辺無し)の組み合わせを網羅しグラフを定義しました。

グラフの連結要素 - MATLAB conncomp - MathWorks 日本

連結グラフの判定アルゴリズムは大変ですが、グラフの連結要素を返すMATLAB関数を使いました。全て同じ所属の要素なら連結グラフであると判定します。

nd = 7;                         % 頂点の数
eg = nd*(nd-1)/2;               % 辺の最大数
egs = dec2bin(0:2^eg-1)-'0';    % 辺の有無組み合わせ
tri = find(triu(ones(nd),1));   % 隣接行列の上三角部のインデックス
adj = zeros(nd);                % 隣接行列の初期化
for i = 1:2^eg                  % 辺の有無組み合わせ数分だけ繰り返す
    adj(tri) = egs(i,:);        % 隣接行列の上三角部を入れ替え
    G = graph(adj,'upper');     % グラフの定義
    if(all(~diff(conncomp(G)))) % 連結グラフだったら
        plot(G);                % 描画する
        drawnow;
    end
end

あとはサブプロットに並べて表示する方法でしょうか(多すぎて全部の表示は困難。ラベル無しでも連結グラフの総数は7ノードで853。Number of Graphs on n unlabelled vertices (yorku.ca))

更に、コメントに頂いたラベル無しグラフの組み合わせも良い方法が無いか探してみます。

下記条件のグラフと認識しています(○×は対応状況)

○ 無向グラフ：辺が向きを持たないグラフ（有向グラフと比較して組み合わせ数が少ない）

○ 単純グラフ：多重辺やループを持たないグラフ（多重辺やループを持つと組み合わせ数が発散する）

○ 連結グラフ：任意の2頂点間が連結されたグラフ（全組み合わせと比較して組み合わせ数が少ない）

× ラベル無グラフ：ノードを特定しないグラフ（ラベル有グラフと比較して組み合わせ数が少ない）

[Gamma1990]

ご返信ありがとうございます．

連結グラフの総数が多いとのことなので，ラベルは指定せずにラベル無しグラフにできないでしょうか？

もともと同型なグラフ(下図の3つのグラフはラベルがなければすべて同じグラフとみなせる)は一つだけわかればいいと思っていたのですが，実装方法がわからなかったためMATLABですべて計算させるつもりでした．

しかし，もしラベル無しグラフとして実装できるなら，同型なグラフは１つだけとなり組み合わせの総数も減るのでラベル無しグラフの方が良いと思いました．

重ねてよろしくお願いします．