树同构

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

树同构的概念源于图同构。图同构的概念为，两个简单图${\displaystyle G}$,)，其中表示一棵树，${\displaystyle r\in <!--\; \in \; -->V(T)}$在根结点到的路径上，称为的父结点，为的子结点。有根树的表示形式可以为“种植的树”，即根节点标有向下箭头；所有结点的子节点都画在该点上方。

有根树同构的定义为，对于两颗有根树${\displaystyle (T_1,r_1)}$,)进行如下编码：

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

若${\displaystyle \mathrm{\#<!--\; \#\; -->}(T_1,r_1)=\mathrm{\#<!--\; \#\; -->}(T_2,r_2)}$，则说明有根树${\displaystyle (T_1,r_1)}$与${\displaystyle (T_2,r_2)}$同构。

该算法的判定定理是：${\displaystyle (T_1,r_1)\simeq <!--\; \simeq \; -->(T_2,r_2)}$当且仅当他们具有相同的0-1编码。对该定理进行如下简单证明：

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

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

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

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