树同构

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

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

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

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

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

有根树的0-1编码

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

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

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

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

• 所有非根叶结点都赋值为01；
• 假设点v的子结点${\displaystyle w_{1},w_{2},\dots ,w_{k}}$ 都已经完成编码，编码为${\displaystyle A(w_{1}),A(w_{2}),\dots ,A(w_{k})}$ ，且有${\displaystyle A(w_{1})\leq A(w_{2})\leq \dots \leq A(w_{k})}$ ，则v结点的编码${\displaystyle A(v)=0A(w_{1})A(w_{2})\dots A(w_{k})1}$ 

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

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

判定定理的简单证明

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

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

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

定义树的中心点集合${\displaystyle C(T):\{v\in T(V,E)|v{\text{ 是使 }}\max _{u\in T}d(u,w){\text{ 最小的点 }}\}}$ 。由于${\displaystyle C(T)}$ 至多包含两个顶点，且若${\displaystyle C(T)=2}$ ，那么该两点必定相邻，故可以选择${\displaystyle C(T)}$ 中的点为根。

树同构的判定算法中，首先通过删叶子结点的方式，算出${\displaystyle C(T)}$ 。

• 若${\displaystyle C(T)=\{r\}}$ ，那么${\displaystyle \#(T,r)}$ 即为树T的编码。
• 若${\displaystyle C(T)=\{r_{1},r_{2}\}}$ ，那么分别计算${\displaystyle \#(T,r_{1})}$ 与${\displaystyle \#(T,r_{2})}$ ，以其中较小的作为树T的编码。

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

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