isomorphism

2 つのグラフ間の同型を計算

構文

P = isomorphism(G1,G2)

P = isomorphism(___,Name,Value)

[P,edgeperm] = isomorphism(___)

説明

P = isomorphism(G1,G2) は、グラフ G1 および G2 間にグラフ同型同値関係が存在する場合、これを計算します。同型が存在しない場合、P は空の配列になります。

P = isomorphism(___,Name,Value) は、1 つ以上の名前と値のペアの引数を使用して追加オプションを指定します。たとえば、'NodeVariables' およびノード変数のリストを指定して同型が有効であるにはこれらの変数を保持しなくてはならないと指定できます。

さらに、[P,edgeperm] = isomorphism(___) は、エッジ置換のベクトル edgeperm を追加で返します。この出力では、多重グラフを使用するときにエッジ変数を保持できます。

例

同型順列の計算

2 つの有向グラフを作成してプロットし、両者間の同型関係を計算します。

G1 = digraph([1 1 1 2 3 4],[2 3 4 4 4 1]);
G2 = digraph([3 3 3 2 1 4],[1 4 2 3 2 2]);
subplot(1,2,1)
plot(G1)
subplot(1,2,2)
plot(G2)

p = isomorphism(G1,G2)

p = 4×1

     3
     1
     4
     2

結果から、reordernodes(G2,p) は G1 と同じ構造であることがわかります。

異なるラベルとレイアウトをもつグラフ間の同型の計算

2 つのグラフ G1 と G2 を作成してプロットします。

G1 = graph([1 1 1 2 2 3 3 4 5 5 7 7],[2 4 5 3 6 4 7 8 6 8 6 8]);
plot(G1,'XData',[1 4 4 1 2 3 3 2],'YData',[4 4 1 1 3 3 2 2])

G2 = graph({'a' 'a' 'a' 'b' 'b' 'b' 'c' 'c' 'c' 'd' 'd' 'd'}, ...
    {'g' 'h' 'i' 'g' 'h' 'j' 'g' 'i' 'j' 'h' 'i' 'j'});
plot(G2,'XData',[1 2 2 2 1 2 1 1],'YData',[4 4 3 2 3 1 2 1])

グラフ間に同型関係がある場合、これを計算します。結果から、ラベルとレイアウトが異なっていても、グラフ ノードを置換して同じグラフを表せることがわかります。

p = isomorphism(G1,G2)

p = 8×1

     1
     2
     5
     3
     4
     7
     6
     8

同型の計算とノード プロパティの保持

2 つのグラフ間の 2 つの異なる同型関係を計算します。関係の一方ではノード プロパティが保持され、もう一方では無視されます。

2 つの類似したグラフを作成します。ノード プロパティ Color を各グラフに追加します。

G1 = graph({'d' 'e' 'f'},{'e' 'f' 'd'});
G1.Nodes.Color = {'blue' 'red' 'red'}';

G2 = graph({'a' 'b' 'c'},{'b' 'c' 'a'});
G2.Nodes.Color = {'red' 'red' 'blue'}';

グラフを同じ Figure に並べてプロットします。Color = 'red' のノードを赤に着色します。

subplot(1,2,1)
p1 = plot(G1);
highlight(p1,{'e' 'f'},'NodeColor','r')

subplot(1,2,2)
p2 = plot(G2);
highlight(p2,{'a' 'b'},'NodeColor','r')

Color プロパティを無視してグラフ間の同型を計算します。

p = isomorphism(G1,G2)

p = 3×1

     1
     2
     3

次に、比較で Color プロパティの値を保持して、同型をもう一度計算します。isomorphism は Color プロパティを保持した異なる置換を返します。

p = isomorphism(G1,G2,'NodeVariables','Color')

p = 3×1

     3
     1
     2

同型が一致する G1 と G2 のノードを表示します。

[G1.Nodes.Name, G2.Nodes.Name(p)]

ans = 3×2 cell
    {'d'}    {'c'}
    {'e'}    {'a'}
    {'f'}    {'b'}

入力引数

G1,G2 — 入力グラフ (個別の引数として指定)

graph オブジェクト | digraph オブジェクト

入力グラフ。graph オブジェクトまたは digraph オブジェクトの個別の引数として指定します。無向グラフの作成には graph を、有向グラフの作成には digraph を使用します。

G1 および G2 は両方が graph オブジェクトまたは digraph オブジェクトでなければなりません。

例: G1 = graph(1,2)

例: G1 = digraph([1 2],[2 3])

名前と値の引数

オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで、Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後に指定しなければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、コンマを使用して名前と値をそれぞれ区切り、Name を引用符で囲みます。

例: P = isomorphism(G1,G2,'NodeVariables',{'Var1' 'Var2'})

EdgeVariables — 保持するエッジ変数

文字ベクトル | string スカラー | 文字ベクトルの cell 配列 | string 配列

保持するエッジ変数。'EdgeVariables' と、文字ベクトル、string スカラー、文字ベクトルの cell 配列、または string 配列で構成されるコンマ区切りのペアとして指定します。このオプションを使用して、G1.Edges と G2.Edges の両方にある 1 つ以上のエッジ変数を指定します。同型が有効であるためには、指定されたエッジ変数を保持しなければなりません。

G が多重グラフの場合は、エッジ変数の順序の変更を有効にする 2 番目の出力 edgeperms を指定します。

データ型: char | string | cell

NodeVariables — 保持するノード変数

文字ベクトル | string スカラー | 文字ベクトルの cell 配列 | string 配列

保持するノード変数。'NodeVariables' と、文字ベクトル、string スカラー、文字ベクトルの cell 配列、または string 配列で構成されるコンマ区切りのペアとして指定します。このオプションを使用して、G1.Nodes と G2.Nodes の両方にある 1 つ以上のノード変数を指定します。同型が有効であるためには、指定されたノード変数を保持しなければなりません。

データ型: char | string | cell

出力引数

P — 同型の置換ベクトル

列ベクトル | []

同型の置換ベクトル。同型が存在する場合は列ベクトルとして、同型が存在しない場合は空の配列 [] として返されます。P が空でない場合、reordernodes(G2,P) は G1 と同じ構造です。

edgeperm — エッジ置換

列ベクトル

エッジ置換。列ベクトルとして返されます。多重グラフを使用する場合、エッジ置換ベクトルを使用すると、'EdgeVariables' 名前と値のペアで指定されたエッジ変数を保持できます。以下のコマンドを使用して、繰り返されるエッジのエッジ変数を並べ替えます。

[p,edgeperm] = isomorphism(g1,g2,'EdgeVariables',edgevars);
g2perm = reordernodes(g2, p);
g2perm.Edges(:, 2:end) = g2perm.Edges(edgeperm, 2:end);

詳細

グラフ同型

2 つのグラフ G1 および G2 は、ノード P の順列が存在する場合は同型であり、reordernodes(G2,P) は G1 と同じ構造です。

同型である 2 つのグラフは構造が類似しています。たとえば、あるグラフに 1 つの閉路が含まれている場合、そのグラフと同型のすべてのグラフにも 1 つの閉路が含まれています。

拡張機能

スレッドベースの環境
MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

バージョン履歴

R2016b で導入

参考

graph | digraph | isisomorphic | reordernodes

トピック

• 有向および無向グラフ