このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。
isomorphism
R2026a2 つのグラフ間の同型を計算
説明
P = isomorphism(___,Name,Value)'NodeVariables' およびノード変数のリストを指定して同型が有効であるにはこれらの変数を保持しなくてはならないと指定できます。
例
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'}
入力引数
名前と値の引数
出力引数
詳細
拡張機能
バージョン履歴
R2016b で導入
