tree_isomorphism#
- tree_isomorphism(t1, t2)[源代码]#
给两棵无向(或自由)树
t1
和t2
,此例程将确定它们是否同构。它返回同构,即t1
在的节点上t2
,这样两棵树就完全相同了。注意,两棵树可能有多个同构,这个例程只返回一个有效的映射。
- 参数
- t1无向网络X图
其中一棵树被比较
- t2无向网络X图
正在比较的另一棵树
- 返回
- isomorphism列表
其中左侧元素是中的节点的对的列表
t1
右边的元素是中的节点t2
。配对的顺序是任意的。如果一个树中的节点映射到另一个树中的名称,则树将是相同的。请注意,同构不一定是唯一的。如果
t1
和t2
不同构,则返回空列表。
笔记
对于具有n个节点的树,这将在O(n*log(n))时间内运行。