用户:LeeeQi/沙盒

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

定义

树同构的概念源于图同构。图同构的概念为，两个简单图 $G$ 和 $H$ 称为是同构的，当且仅当存在一个将 $G$ 的节点 $1,\ldots ,n$ 映射到 $H$ 的节点 $1,\ldots ,n$ 的一一对应 $\sigma$ ，使得 $G$ 中任意两个节点 $i$ 和 $j$ 相连接，当且仅当 $H$ 中对应的两个节点 $\sigma (i)$ 和 $\sigma (j)$ 相连接。树同构即在以上定义中增加 $G$ 和 $H$ 都是树的限制条件。两颗树 $T_{1},T_{2}$ 同构可以记作 $T_{1}\simeq T_{2}$ 。

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

有根树同构的定义为，对于两颗有根树 $(T_{1},r_{1})$ ， $(T_{2},r_{2})$ ，存在一个同构映射 $f$ ，其中 $f(r_{1})=r_{2}$ 。 $(T_{1},r_{1})$ 与 $(T_{2},r_{2})$ 同构可记作 $(T_{1},r_{1})\simeq (T_{2},r_{2})$ 。

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

有根树同构判定算法

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

有根树的0-1编码

对有根树进行0-1编码，并且采用字典序对编码进行比较。字典序的比较方法为：对不同序列 $s=s_{1}s_{2}\dots s_{n}$ 和 $t=t_{1}t_{2}\dots t_{m}$ ：

如果 $s$ 是 $t$ 的初始序列（即 $t=st_{i}\dots t_{m}$ ），则 $s<t$ ;
如果 $t$ 是 $s$ 的初始序列（即 $s=ts_{i}\dots s_{n}$ ），则 $t<s$ ;
令 $i$ 是 $s_{i}\neq t_{i}$ 的最小下标，若 $s_{i}<t_{i}$ 则 $s<t$ ，若 $t_{i}<s_{i}$ 则 $t<s$ 。

例： $00<001$ , $01{\textbf {0}}11<01{\textbf {1}}0$ 。

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

所有非根叶结点都赋值为01；
假设点v的子结点 $w_{1},w_{2},\dots ,w_{k}$ 都已经完成编码，编码为 $A(w_{1}),A(w_{2}),\dots ,A(w_{k})$ ，且有math>A(w_1)\le A(w_2)\le \dots\le A(w_k)</math>，则v结点的编码 $A(v)=0A(w_{1})A(w_{2})\dots A(w_{k})1$

如此递归。r结点的编码 $A(r)$ 即为该有根树的编码，用 $\#(T,r)$ 表示。

若 $\#(T_{1},r_{1})=\#(T_{2},r_{2})$ ，则说明有根树 $(T_{1},r_{1})$ 与 $(T_{2},r_{2})$ 同构。

判定定理的简单证明

该算法的判定定理是： $(T_{1},r_{1})\simeq (T_{2},r_{2})$ 当且仅当他们具有相同的0-1编码。对该定理进行如下简单证明：

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