Main Content

isomorphism

计算两个图之间的同构

全页折叠

语法

P = isomorphism(G1,G2)
P = isomorphism(___,Name,Value)
[P,edgeperm] = isomorphism(___)

说明

P = isomorphism(G1,G2) 计算图 G1 和 G2 之间的图同构等价关系（如果存在）。如果不存在同构，则 P 为空数组。

示例

P = isomorphism(___,Name,Value) 使用一个或多个名称-值对组参量指定其他选项。例如，您可以指定 'NodeVariables' 和一个节点变量列表，以指示同构必须保留这些变量才有效。

示例

[P,edgeperm] = isomorphism(___) 还返回边置换 edgeperm 的向量。此输出使您能够在处理多重图时保留边变量。

示例

全部折叠

打开实时脚本

创建并绘制两个有向图，然后计算它们之间的同构关系。

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)

Figure contains 2 axes objects. Axes object 1 contains an object of type graphplot. Axes object 2 contains an object of type graphplot.

p = isomorphism(G1,G2)
p = 4×1

     3
     1
     4
     2

结果表明 reordernodes(G2,p) 与 G1 具有相同的结构。

打开实时脚本

创建并绘制两个图形 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])

Figure contains an axes object. The axes object contains an object of type graphplot.

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])

Figure contains an axes object. The axes object contains an object of type graphplot.

计算两个图之间的同构关系（如果存在）。结果表明，图节点可以置换以表示相同的图，尽管它们具有不同的标签和布局。

p = isomorphism(G1,G2)
p = 8×1

     1
     2
     5
     3
     4
     7
     6
     8
打开实时脚本

计算两个图之间两种不同的同构关系。一种关系保留节点属性，另一种关系忽略节点属性。

创建两个类似的图。在每个图中添加节点属性 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'}';

在同一个图窗中并排绘制两个图。将 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')

Figure contains 2 axes objects. Axes object 1 contains an object of type graphplot. Axes object 2 contains an object of type graphplot.

计算两个图之间的同构关系，并忽略 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 = 3x2 cell
    {'d'}    {'c'}
    {'e'}    {'a'}
    {'f'}    {'b'}

输入参数

全部折叠

输入图，指定为 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' 和一个字符向量、字符串标量、字符向量元胞数组或字符串数组。使用此选项指定同时位于 G1.Edges 和 G2.Edges 中的一个或多个边变量。同构必须保留指定的边变量才有效。

如果 G 是多重图，则您可以指定第二个输出 edgeperms，以允许重新排序边变量。

数据类型: char | string | cell

要保留的节点变量，指定为逗号分隔的对组，其中包含 'NodeVariables' 和一个字符向量、字符串标量、字符向量元胞数组或字符串数组。使用此选项指定同时位于 G1.Nodes 和 G2.Nodes 中的一个或多个节点变量。同构必须保留指定的节点变量才有效。

数据类型: 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);

详细信息

全部折叠

图的同构

两个图 G1 和 G2，如果存在一种节点置换 P，使得 reordernodes(G2,P) 与 G1 具有相同的结构，则说明二者是同构图。

同构的两个图具有类似的结构。例如，如果一个图包含一个圆，则与其同构的所有图也都会包含一个圆。

扩展功能

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2016b 中推出

另请参阅

| | |

主题