树同构（Tree Isomorphism）

树同构（Tree Isomorphism）​​ 是图论中的一个经典问题，主要研究两棵树在结构上是否“相同”或“等价”，即是否存在一种节点的一一对应关系，使得两棵树的结构完全一致（不考虑节点的具体标签或位置）。以下是关于树同构问题的详细说明：

​1. 问题定义​

• ​输入​：两棵树 T1​ 和 T2​（通常是无向、无权、连通的树，但也可以扩展到有向树或带权树）。
• ​问题​：判断 T1​ 和 T2​ 是否同构，即是否存在一个双射（一一对应）函数 f，将 T1​ 的节点映射到 T2​ 的节点，使得任意两节点 u,v 在 T1​ 中相邻当且仅当 f(u),f(v) 在 T2​ 中相邻。

​2. 树同构的核心​

• ​结构等价性​：同构的树在拓扑结构上完全相同，只是节点的“名字”或编号可能不同。
• ​不关心节点属性​：除非特别说明（如带标签的树同构），否则默认只比较树的连接方式。

​3. 常见变体​

• ​无标号树同构​：节点没有标签，仅比较结构。
• ​有标号树同构​：节点有标签（如字母或数字），要求对应节点的标签也相同。
• ​有向树同构​：考虑边的方向（如根树、二叉树）。
• ​动态树同构​：支持树的动态修改（如添加/删除边）并快速判断同构。

​4. 解决方法​

​​(1) 朴素方法（暴力枚举）​​

• 尝试所有可能的节点映射，检查是否满足同构条件。
• ​复杂度​：O(n!)(不可行，仅理论存在)。

​​(2) 基于树哈希（Tree Hashing）​​

• 为每棵树计算一个“哈希值”，若哈希值相同则可能同构（需处理哈希冲突）。
• ​常用哈希方法​：
  • ​AHU算法​（递归编码）：通过子树的结构编码生成唯一标识符。
  • ​重心分解​：利用树的重心性质简化问题（树最多有两个重心）。

​​(3) 基于树的中心和编码​

• ​步骤​：
  1. 找到两棵树的重心（1个或2个）。
  2. 以重心为根，递归生成子树的规范编码（如括号序列表示）。
  3. 比较两棵树的编码是否相同。
• ​复杂度​：O(n)（线性时间）。

​5. 应用场景​

• ​生物信息学​：比较分子结构（如RNA二级结构）是否同构。
• ​计算机网络​：判断网络拓扑结构是否等价。
• ​化学​：分析分子图的同构性。
• ​密码学​：某些加密算法依赖树结构的唯一性。

​6. 相关概念​

• ​图同构​：更一般化的问题（判断任意两图是否同构），目前无已知多项式时间算法（可能是NP问题）。
• ​子树同构​：判断一棵树的子树是否与另一棵树同构。
• ​森林同构​：多棵树的同构问题。

​7. 示例​

• ​同构的树​：
  • 树1：1-2-3
  • 树2：a-b-c
    （结构均为链状，节点标签不同但同构）。
• ​非同构的树​：
  • 树1：星形（中心连接3个叶子）
  • 树2：链状（4个节点依次连接）。

​总结​

树同构问题本质是判断两棵树的结构是否可以通过重新标记节点变得完全相同，是算法设计和复杂性理论中的重要问题，广泛应用于多个领域。其高效解决方案（如AHU算法）通常依赖于树的递归性质和哈希技术。