同构性#
|
如果图 G1 和 G2 同构则返回 True，否则返回 False。 |
|
如果图确定不同构则返回 False。 |
|
如果图确定不同构则返回 False。 |
|
如果图确定不同构则返回 False。 |
VF2++#
VF2++ 算法#
VF2++ 算法 [1] 用于图同构测试的实现。
使用此模块最简单的接口是调用以下函数：
vf2pp_is_isomorphic：检查两个图是否同构。vf2pp_isomorphism：如果两个图同构，获取它们之间的节点映射。vf2pp_all_isomorphisms：如果两个图同构，生成所有可能的映射。
引言#
VF2++ 算法遵循与 VF2 类似的逻辑，同时引入了新的易于检查的剪枝规则并确定了节点的最佳访问顺序。与之前的版本相比，它还以非递归方式实现，从而节省了时间和空间。
在考虑了节点的度以及标签稀有性后，可以获得最优的节点排序。这样，我们将更可能匹配的节点放在排序的前面，从而在开始时就检查最有希望的分支。这些规则也考虑了节点标签，使得在过程早期更容易剪枝掉无用的分支。
示例#
假设 G1 和 G2 是同构图。验证如下：
无节点标签
>>> import networkx as nx
>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> nx.vf2pp_is_isomorphic(G1, G2, node_label=None)
True
>>> nx.vf2pp_isomorphism(G1, G2, node_label=None)
{1: 1, 2: 2, 0: 0, 3: 3}
有节点标签
>>> G1 = nx.path_graph(4)
>>> G2 = nx.path_graph(4)
>>> mapped = {1: 1, 2: 2, 3: 3, 0: 0}
>>> nx.set_node_attributes(
... G1, dict(zip(G1, ["blue", "red", "green", "yellow"])), "label"
... )
>>> nx.set_node_attributes(
... G2,
... dict(zip([mapped[u] for u in G1], ["blue", "red", "green", "yellow"])),
... "label",
... )
>>> nx.vf2pp_is_isomorphic(G1, G2, node_label="label")
True
>>> nx.vf2pp_isomorphism(G1, G2, node_label="label")
{1: 1, 2: 2, 0: 0, 3: 3}
参考文献#
Jüttner, Alpár & Madarasi, Péter. (2018). “VF2++—一种改进的子图同构算法”。Discrete Applied Mathematics. 242. https://doi.org/10.1016/j.dam.2018.02.018
|
检查 G1 和 G2 是否同构。 |
|
生成 G1 和 G2 之间所有可能的映射。 |
|
如果存在，返回 |
树同构性#
一种算法，用于查找两棵无向树是否同构，如果同构，则返回两组节点之间的同构映射。
此算法使用一个例程来判断两棵有根树（指定了根节点的树）是否同构，这可能独立有用。
这实现了一个算法，来自：Aho, Hopcroft 和 Ullman 的著作《计算机算法的设计与分析》（Addison-Wesley Publishing 1974）中示例 3.2（第 84-86 页）。
该算法的一个更易于理解的版本描述在：Matthew Suderman 撰写的 McGill University SOCS 308-250B 课程作业 5，2002 年冬季 http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf
|
给定两棵有根树 |
|
给定两棵无向树（或自由树） |