Main Content

isisomorphic

确定两个图是否同构

说明

如果图 G1G2 之间存在图的同构tf = isisomorphic(G1,G2) 将返回逻辑值 1 (true);否则,将返回逻辑值 0 (false)。

示例

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

示例

示例

全部折叠

创建并绘制两个有向图,然后确定它们是否同构。

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.

isisomorphic(G1,G2)
ans = logical
   1

创建并绘制两个图形 G1G2

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.

确定 G1G2 之间是否存在同构。结果表明,两个图尽管具有不同的标签和布局,但具有相同的结构。

tf = isisomorphic(G1,G2)
tf = logical
   1

通过两种不同的比较,确定两个图之间是否存在同构关系。一种比较保留节点属性,另一种比较忽略节点属性。

创建两个类似的图。在每个图中添加节点属性 Color

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

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

在同一个图窗中并排绘制两个图。将 Color = 'red' 的节点标为红色。

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

subplot(1,2,2)
p2 = plot(G2);
highlight(p2,'c','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 属性。

tf = isisomorphic(G1,G2)
tf = logical
   1

确定两个图是否同构,并在比较中保留 Color 属性的值。在这种情况下,由于每个图的 Color 属性包含不同数量的 'red''blue' 值,所以二者之间不存在同构关系。

tf = isisomorphic(G1,G2,'NodeVariables','Color')
tf = logical
   0

输入参数

全部折叠

输入图,指定为 graphdigraph 对象的单独参量。可使用 graph 创建一个无向图,或使用 digraph 创建一个有向图。

G1G2 必须同为 graph 对象,或者同为 digraph 对象。

示例: G1 = graph(1,2)

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

名称-值参数

将可选的参量对组指定为 Name1=Value1,...,NameN=ValueN,其中 Name 是参量名称,Value 是对应的值。名称-值参量必须出现在其他参量之后,但参量对组的顺序无关紧要。

在 R2021a 之前,使用逗号分隔每个名称和值,并用引号将 Name 引起来。

示例: tf = isisomorphic(G1,G2,'NodeVariables',{'Var1' 'Var2'})

要保留的边变量,指定为逗号分隔的对组,其中包含 'EdgeVariables' 和一个字符向量、字符串标量、字符向量元胞数组或字符串数组。使用此选项指定同时位于 G1.EdgesG2.Edges 中的一个或多个边变量。同构比较必须保留指定的边变量才有效。对于相同的两个节点之间具有多条边的多重图来说,同一个节点对的边变量的排序不受影响。

数据类型: char | string | cell

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

数据类型: char | string | cell

详细信息

全部折叠

图的同构

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

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

扩展功能

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

版本历史记录

在 R2016b 中推出