isomorphism
计算两个图之间的同构
说明
示例
计算同构置换
创建并绘制两个有向图,然后计算它们之间的同构关系。
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
具有相同的结构。
计算具有不同标签和布局的图之间的同构关系
创建并绘制两个图形 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
计算同构关系并保留节点属性
计算两个图之间两种不同的同构关系。一种关系保留节点属性,另一种关系忽略节点属性。
创建两个类似的图。在每个图中添加节点属性 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')
计算两个图之间的同构关系,并忽略 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'}
输入参数
名称-值参数
将可选的参量对组指定为 Name1=Value1,...,NameN=ValueN
,其中 Name
是参量名称,Value
是对应的值。名称-值参量必须出现在其他参量之后,但参量对组的顺序无关紧要。
在 R2021a 之前,使用逗号分隔每个名称和值,并用引号将 Name
引起来。
示例: P = isomorphism(G1,G2,'NodeVariables',{'Var1' 'Var2'})
EdgeVariables
— 要保留的边变量
字符向量 | 字符串标量 | 字符向量元胞数组 | 字符串数组
要保留的边变量,指定为逗号分隔的对组,其中包含 'EdgeVariables'
和一个字符向量、字符串标量、字符向量元胞数组或字符串数组。使用此选项指定同时位于 G1.Edges
和 G2.Edges
中的一个或多个边变量。同构必须保留指定的边变量才有效。
如果 G
是多重图,则您可以指定第二个输出 edgeperms
,以允许重新排序边变量。
数据类型: char
| string
| cell
NodeVariables
— 要保留的节点变量
字符向量 | 字符串标量 | 字符向量元胞数组 | 字符串数组
要保留的节点变量,指定为逗号分隔的对组,其中包含 'NodeVariables'
和一个字符向量、字符串标量、字符向量元胞数组或字符串数组。使用此选项指定同时位于 G1.Nodes
和 G2.Nodes
中的一个或多个节点变量。同构必须保留指定的节点变量才有效。
数据类型: 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);
详细信息
图的同构
两个图 G1
和 G2
,如果存在一种节点置换 P
,使得 reordernodes(G2,P)
与 G1
具有相同的结构,则说明二者是同构图。
同构的两个图具有类似的结构。例如,如果一个图包含一个圆,则与其同构的所有图也都会包含一个圆。
扩展功能
基于线程的环境
使用 MATLAB® backgroundPool
在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool
加快代码运行速度。
版本历史记录
在 R2016b 中推出
MATLAB 命令
您点击的链接对应于以下 MATLAB 命令:
请在 MATLAB 命令行窗口中直接输入以执行命令。Web 浏览器不支持 MATLAB 命令。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- 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)