はじめに
Matlabで指定した頂点数の連結無向グラフを全パターン生成するプログラムを作成しました。
動作環境
Matlab R2019a
Win10
方法
プログラム作成にあたっての考え方やコードを記載します。
考え方
頂点数$n$の連結無向グラフを作成するための考え方としては、頂点数$n-1$の連結無向グラフに頂点を1つ追加して辺の組み合わせを全パターン試すという方法を使用しています。
図を用いて詳しく説明します。
まず、頂点数3の連結無向グラフが作りたいとします。
その際には、上の頂点数2の連結無向グラフに頂点を追加して辺の組み合わせを全パターン負荷すればよいので、
このような考え方になります。結果として、頂点数3の連結無向グラフは、
が得られます。
この作業を繰り返すことで求めたい頂点数の連結無向グラフを全パターン生成することができます。
しかし、この作業だけでは頂点のナンバリングを変えたり辺や頂点の場所を入れ替えるだけで同じグラフが生成されてします。
例として、以下の2つのグラフはナンバリングや位置が違うだけで同じグラフだといえます。
これらの判別法としては、グラフの隣接行列の固有値ベクトルで判別する方法があります。
隣接行列とは、グラフの頂点や辺の接続情報、重みを行列で表したものです。
ナンバリングや位置が違うだけで同じグラフの場合、固有値ベクトルは同じ値をとります。
この方法を用いて同じグラフかどうかフィルターをかけていきます。
実行コード
MATLABで実行したコードを以下に示します。
function A_list = graphgene(A_before_list)
A_size = size(A_before_list);
before_n = A_size(1);%前の頂点数
now_n = before_n + 1;%今回作りたいグラフの頂点数
bin_range = 2^before_n;
gene_num = 1;%保存したグラフの数
check_flag = true; %同じ隣接行列が存在しているか
for i = 1:A_size(3)%前の頂点数でできたグラフの数
target_before_A = A_before_list(:,:,i);%基にするグラフの隣接行列
for j = 1:bin_range-1%前のグラフに頂点を一つ加えるループ(全部ビンのパターン)
check_flag = true;
add_binStr = dec2bin(j,before_n);
add_ary = add_binStr;
%%%%%%%%%%%%%%%グラフ作る%%%%%%%%%%%%%%%%%%
for k = 1:before_n
add_col = zeros(1,now_n);
add_col = target_before_A(k,:);
add_col(1,now_n) = str2double(add_ary(k));
target_after_A(k,:) = add_col; %今回作るグラフ
add_fin_col(k) = str2double(add_ary(k));
end
add_fin_col(now_n) = 0;
target_after_A(now_n,:) = add_fin_col;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%同じ固有値ベクトルがあるか%%%%%%%%%%%%%%
now_e = eig(target_after_A);
now_e = round(now_e,4);
if(isequal(now_e,0) || isequal(now_e,-0))
now_e = 0;
end
if (gene_num ~= 1)
for j_2 = 1:gene_num-1
if (isequal(e_list(:,:,j_2),now_e))
check_flag = false;
end
end
else
e_list(:,:,1) = now_e;
check_flag = true;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%生成したグラフを追加%%%%%%%%%%%%%%%
if (check_flag == true)
A_list(:,:,gene_num) = target_after_A;
if(gene_num ~= 1)
e_list(:,:,gene_num) = now_e;
end
gene_num = gene_num + 1;
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
end
end
end
上記の関数の入力引数は、求めたい連結無向グラフの頂点数を$n$とすると、頂点数$n-1$の連結無向グラフの隣接行列のリストです。
返り値は、頂点数$n$の連結無向グラフの隣接行列のリストになっています。
先ほど考え方で説明した通りの流れを実行しています。
この関数を自分が求めたい頂点数になるまで繰り返し呼び出すことで連結無向グラフを作成することができます。
おわりに
この方法は、頂点数が数十くらいであればそんなに処理が重くならず、計算時間もかからないのですが、とても大きな頂点数の場合だとどのくらい時間がかかるのか不安です。
もっといい方法がある気もするので是非教えてほしいです。