树同构
Template:Multiple issues 树同构(Tree Isomorphism)描述的是图论中，两个树之间的完全等价关系。在图论的观点下，两个同构的树可以被当作同一个图来研究。
定义
树同构的概念源于图同构。图同构的概念为，两个简单图和称为是同构的，当且仅当存在一个将的节点 映射到的节点的一一对应，使得中任意两个节点和相连接，当且仅当中对应的两个节点和相连接。树同构即在以上定义中增加和都是树的限制条件。两颗树同构可以记作。
在此基础上，定义有根树及其同构的概念[1]。有根树可表示为(T,r)，其中T表示一棵树，是一个有特殊标记的点，称为树的根结点。对于边，若x在根结点到y的路径上，称x为y的父结点，y为x的子结点。有根树的表示形式可以为“种植的树”，即根节点r标有向下箭头；所有结点的子节点都画在该点上方。
有根树同构的定义为，对于两颗有根树，，存在一个同构映射，其中。与同构可记作。
由以上定义可知，有根树同构的关系严格强于树同构的关系。
有根树同构判定算法
有根树同构的判定问题是P问题（P/NP问题）。这里介绍其中一种算法，该算法将有根树的比较转化为字符串的比较。
有根树的0-1编码
对有根树进行0-1编码，并且采用字典序对编码进行比较。字典序的比较方法为： 对不同序列和：
- 如果是的初始序列（即），则;
- 如果是的初始序列（即），则;
- 令是的最小下标，若则，若则。
例：,。
对有根树(T,r)进行如下编码：
- 所有非根叶结点都赋值为01；
- 假设点v的子结点都已经完成编码，编码为，且有，则v结点的编码
如此递归。r结点的编码即为该有根树的编码，用表示。
若，则说明有根树与同构。
判定定理的简单证明
该算法的判定定理是：当且仅当他们具有相同的0-1编码。 对该定理进行如下简单证明：
- 充分性：从有根树同构的定义和编码过程可证。
- 必要性：对编码进行解码。任意有根树的编码必然有的一般形式，其中。是中0,1个数相等的最小前缀，是第二个0,1平衡的最小前缀，以此类推，可以解码出唯一形态的有根树。这棵有根树的其他表示形式都与该解码形式同构。
树同构判定算法
树同构的判定算法基于有根树同构的判定算法构成。在前文所述中，有根树相对于树的区别在于，有根树有一个特定标记的根。对于一般的树，我们需要一种找根的算法；在确定这棵树的有根表达形式之后，对于有根树进行编码判定即可。
定义树的中心点集合。由于至多包含两个顶点，且若，那么该两点必定相邻，故可以选择中的点为根。
树同构的判定算法中，首先通过删叶子结点的方式，算出。
- 若，那么即为树T的编码。
- 若，那么分别计算与，以其中较小的作为树T的编码。
若两棵树的编码相同，即可认为两棵树是同构的。