isomorphism
2 つのグラフ間の同型を計算
説明
は、1 つ以上の名前と値のペアの引数を使用して追加オプションを指定します。たとえば、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'}
入力引数
名前と値の引数
オプションの引数のペアを Name1=Value1,...,NameN=ValueN
として指定します。ここで、Name
は引数名で、Value
は対応する値です。名前と値の引数は他の引数の後に指定しなければなりませんが、ペアの順序は重要ではありません。
R2021a より前では、コンマを使用して名前と値をそれぞれ区切り、Name
を引用符で囲みます。
例: P = isomorphism(G1,G2,'NodeVariables',{'Var1' 'Var2'})
保持するエッジ変数。'EdgeVariables'
と、文字ベクトル、string スカラー、文字ベクトルの cell 配列、または string 配列で構成されるコンマ区切りのペアとして指定します。このオプションを使用して、G1.Edges
と G2.Edges
の両方にある 1 つ以上のエッジ変数を指定します。同型が有効であるためには、指定されたエッジ変数を保持しなければなりません。
G
が多重グラフの場合は、エッジ変数の順序の変更を有効にする 2 番目の出力 edgeperms
を指定します。
データ型: char
| string
| cell
保持するノード変数。'NodeVariables'
と、文字ベクトル、string スカラー、文字ベクトルの cell 配列、または string 配列で構成されるコンマ区切りのペアとして指定します。このオプションを使用して、G1.Nodes
と G2.Nodes
の両方にある 1 つ以上のノード変数を指定します。同型が有効であるためには、指定されたノード変数を保持しなければなりません。
データ型: char
| string
| cell
出力引数
同型の置換ベクトル。同型が存在する場合は列ベクトルとして、同型が存在しない場合は空の配列 []
として返されます。P
が空でない場合、reordernodes(G2,P)
は G1
と同じ構造です。
エッジ置換。列ベクトルとして返されます。多重グラフを使用する場合、エッジ置換ベクトルを使用すると、'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 で導入
MATLAB Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
Web サイトの選択
Web サイトを選択すると、翻訳されたコンテンツにアクセスし、地域のイベントやサービスを確認できます。現在の位置情報に基づき、次のサイトの選択を推奨します:
また、以下のリストから Web サイトを選択することもできます。
最適なサイトパフォーマンスの取得方法
中国のサイト (中国語または英語) を選択することで、最適なサイトパフォーマンスが得られます。その他の国の MathWorks のサイトは、お客様の地域からのアクセスが最適化されていません。
南北アメリカ
- América Latina (Español)
- Canada (English)
- United States (English)
ヨーロッパ
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)