algorithm - 如何使用最大二分匹配来解决子树同构？

如何确定给定树t是否包含同构于另一树s的子树？
如果两棵树中的一棵可以通过一系列翻转（即交换多个节点的左、右子节点）从另一棵树中获得，则称之为同构树。任何级别的任意数量的节点都可以交换其子节点。两棵空树是同构的。
我在一些地方读到过两部分匹配算法可以用来解决这个问题，但我找不到任何非付费来源的细节。关于这个问题的研究论文似乎很多，大多数都是在paywall之后，但是我目前对这个问题的最新研究算法不感兴趣。我的问题是二分匹配如何应用于这个问题？
附言：互联网上似乎有一些关于什么是“同构”的混淆。上面是我在大多数地方找到的定义，但有些地方提到的“同构”意味着无论节点值如何，树的形状都是相同的。如果有人能澄清这种困惑，那也太好了。

最佳答案

我将讨论有根子树同构；无根的情况可以通过尝试所有根来处理，而不考虑效率。
基本思想是如果你有树

    A            B
   /|\          /|\
  / | \        / | \
 /  |  \      /  |  \
a1 ...  am   b1 ...  bn
/\      /\   /\      /\

想知道A是否是B的子树，以便A映射到B，那么对于所有i和j，递归地计算根在ai的子树是否是根在bj的树的子树，以便ai映射到bj。（基本情况是当A或B是一片叶子时）现在，每个子树都是可映射的还不够，因为如果有些bj有一个特别丰富的结构，那么几个ai可能是子树，但是同构的要求不会让它们共享这个bj。这就是最大匹配出现的地方：我们尝试将所有的ai s与bj s匹配，从而可以映射子树。
要解决一般的根问题，请尝试所有可能的B选项。

关于algorithm - 如何使用最大二分匹配来解决子树同构？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29873740/