跳转到内容

User:LeeeQi/沙盒

维基百科,自由的百科全书

树同构(Tree Isomorphism)描述的是图论中,两个之间的完全等价关系。在图论的观点下,两个同构的可以被当作同一个图来研究。

定义

树同构的概念源于图同构图同构的概念为,两个简单图称为是同构的,当且仅当存在一个将的节点 映射到的节点一一对应,使得中任意两个节点相连接,当且仅当中对应的两个节点相连接。树同构即在以上定义中增加都是的限制条件。两颗树同构可以记作

在此基础上,定义有根树及其同构的概念[1]有根树可表示为(T,r),其中T表示一棵树,是一个有特殊标记的点,称为树的根结点。对于边,若x在根结点到y路径上,称xy父结点yx子结点。有根树的表示形式可以为“种植的树”,即根节点r标有向下箭头;所有结点的子节点都画在该点上方。

有根树同构的定义为,对于两颗有根树,存在一个同构映射,其中同构可记作

由以上定义可知,有根树同构的关系严格强于树同构的关系。

有根树同构判定算法

有根树同构的判定问题是P问题P/NP问题)。这里介绍其中一种算法,该算法将有根树的比较转化为字符串的比较。

有根树的0-1编码

对有根树进行0-1编码,并且采用字典序对编码进行比较。字典序的比较方法为: 对不同序列

  • 如果的初始序列(即),则;
  • 如果的初始序列(即),则;
  • 的最小下标,若,若

例:,

对有根树(T,r)进行如下编码:

  • 所有非根叶结点都赋值为01;
  • 假设点v的子结点都已经完成编码,编码为,且有math>A(w_1)\le A(w_2)\le \dots\le A(w_k)</math>,则v结点的编码

如此递归。r结点的编码即为该有根树的编码,用表示。

,则说明有根树同构。

判定定理的简单证明

该算法的判定定理是:当且仅当他们具有相同的0-1编码。 对该定理进行如下简单证明:

  • 充分性:从有根树同构的定义和编码过程可证。
  • 必要性:对编码进行解码。任意有根树的编码必然有的一般形式,其中中0,1个数相等的最小前缀,是第二个0,1平衡的最小前缀,以此类推,可以解码出唯一形态的有根树。这棵有根树的其他表示形式都与该解码形式同构。

树同构判定算法

树同构的判定算法基于有根树同构的判定算法构成。在前文所述中,有根树相对于树的区别在于,有根树有一个特定标记的根。对于一般的树,我们需要一种找根的算法;在确定这棵树的有根表达形式之后,对于有根树进行编码判定即可。

定义树的中心点集合。由于至多包含两个顶点,且若,那么该两点必定相邻,那么可以选择中的点为根。

树同构的判定算法中,首先通过删叶子结点的方式,算出

  • ,那么即为树T的编码。
  • ,那么分别计算,以其中较小的作为树T的编码。

若两棵树的编码相同,即可认为两棵树是同构的。

参考文献

  1. ^ Jiří Matoušek (mathematician); Jaroslav Nešetřil. Invitation to discrete mathematics 2nd. Oxford. ISBN 9780198570431.