tree_isomorphism

tree_isomorphism(t1, t2)

给定两个无向（或自由）树 t1 和 t2 ， 此程序将确定它们是否同构。 它返回一个同构映射，即将 t1 的节点映射到 t2 的节点上，使得两棵树完全相同。

请注意，两棵树可能有多个同构映射，此程序仅返回一个有效的映射。

Parameters:

t1无向 NetworkX 图

被比较的其中一棵树

t2无向 NetworkX 图

被比较的另一棵树

Returns:

isomorphism列表

一个由成对元素组成的列表，其中左元素是 t1 中的节点， 右元素是 t2 中的节点。这些成对元素的顺序是任意的。 如果一棵树的节点被映射到另一棵树的节点名称上，那么这两棵树将完全相同。 请注意，同构映射不一定是唯一的。

如果 t1 和 t2 不同构，则返回空列表。

Notes

对于具有 n 个节点的树，此程序的运行时间为 O(n*log(n))。