tree_isomorphism

tree_isomorphism(t1, t2)

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

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

参数:

t1无向 NetworkX 图

要比较的其中一棵树

t2无向 NetworkX 图

要比较的另一棵树

返回:

isomorphism列表

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

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

备注

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