isisomorphic

---

确定两个图是否同构

函数库: TyMath

语法

tf = isisomorphic(G1, G2; EdgeVariable=false, NodeVariable=false)

说明

如果图 G1 和 G2 之间存在图的同构，tf = isisomorphic(G1,G2) 将返回逻辑值 true；否则，将返回逻辑值 false。示例

---

tf = isisomorphic(G1,G2; EdgeVariable=false, NodeVariable=false) NodeVariables 指示同构是否保留节点属性才有效，EdgeVariables 指示同构是否保留边属性才有效。示例

示例

比较图

创建两个有向图，然后确定它们是否同构。

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

isisomorphic(G1,G2)

ans = true

比较具有不同标签和布局的图

创建并绘制两个图形 G1 和 G2。

using TyMath
using TyPlot
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][:]);
plotG(G1, [1 4 4 1 2 3 3 2][:],[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"],
    );
figure()
plotG(G2, [1 2 2 2 1 2 1 1][:], [4 4 3 2 3 1 2 1][:])

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

isisomorphic(G1,G2)

ans = true

在同构比较中保留节点属性

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

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

using TyMath
G1 = Graph(["d", "e", "f"], ["e", "f", "d"]);
G1.Nodes.props = ["red", "red", "blue"];

G2 = Graph(["a", "b", "c"], ["b", "c", "a"]);
G2.Nodes.props = ["blue", "blue", "red"];

确定两个图是否同构，并忽略节点属性。

isisomorphic(G1, G2)

ans = true

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

isisomorphic(G1, G2, NodeVariable=true)

ans = false

输入参数

G - 输入图

Graph 对象 | DiGraph 对象

输入图，指定为 Graph 或 DiGraph 对象。可使用 Graph 创建一个无向图，或使用 DiGraph 创建一个有向图。

示例： G = Graph(1,2)

示例： G = DiGraph([1,2],[2,3])

EdgeVariables - 是否保留的边属性

false （默认） | true

使用此选项指定同时位于 G1.Edges 和 G2.Edges 中的边属性。同构必须保留指定的边属性才有效。

如果 G 是多重图，第二个输出 edgeperms 允许重新排序边变量。

NodeVariables - 是否保留的节点属性

false （默认） | true

使用此选项指定同时位于 G1.Nodes 和 G2.Nodes 中的节点属性。同构必须保留指定的节点属性才有效。

详细信息

图的同构

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

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

另请参阅

Graph | DiGraph | isomorphism | reordernodes