連結な単純無向グラフにおいて,頂点が7つのグラフをすべて出力するにはどうすればよいですか?
10 views (last 30 days)
Show older comments
・実現したいこと
私がしたいことは,連結な単純無向グラフにおいて,頂点が7つのときのグラフをすべて出力することです.
具体的にすべて出力するというのがどういうことかというと,例えば頂点が3つの場合,以下の4つを出力するということです.
![](https://www.mathworks.com/matlabcentral/answers/uploaded_files/673163/image.png)
頂点が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を使い始めたばかりで,どのようにプログラムを書けばいいのかわかりませんでした.
よろしくお願いします.
0 Comments
Accepted Answer
Atsushi Ueno
on 3 Jul 2021
Edited: Atsushi Ueno
on 4 Jul 2021
V = 1:3
E = 2
C = nchoosek(V,E)
この方法も良いかなと思ったのですが、7頂点の内から何個取って繋ぐかを機械的に判断する事は難しいと思いました。網羅的にするなら隣接行列で指定した方が簡単に実装できそうだと思いました。
graph関数によるグラフの定義方法は大きく分けて「始点と終点の指定」と「隣接行列の指定」の2種類あります。私は「隣接行列の指定」を選び、対角成分(ループ)を除く上三角部に1(辺有り)と0(辺無し)の組み合わせを網羅しグラフを定義しました。
連結グラフの判定アルゴリズムは大変ですが、グラフの連結要素を返す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頂点間が連結されたグラフ(全組み合わせと比較して組み合わせ数が少ない)
× ラベル無グラフ:ノードを特定しないグラフ(ラベル有グラフと比較して組み合わせ数が少ない)
More Answers (0)
See Also
Categories
Find more on Directed Graphs in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!