如何使用最大二分匹配解决子树同构？
How to solve Subtree Isomorphism using maximum bipartite matching?
我们如何确定给定树 T 是否包含与另一棵树 S 同构的子树？
如果其中一棵树可以通过一系列翻转从另一棵树中获得，则称两棵树是同构的，即通过交换多个节点的左右子节点。任何级别的任何数量的节点都可以交换它们的子节点。两棵空树是同构的。
我在一些地方读到过可以使用二分匹配算法来解决这个问题，但是我找不到任何非付费资源来了解详细信息。似乎有很多关于这个问题的研究论文，其中大部分都再次落后于付费专区，但是我目前对这个问题的最新研究算法不感兴趣。我的问题是二分匹配如何应用于这个问题？
PS：互联网上似乎对"isomorphic"的含义有些混淆。以上是我在大多数地方找到的定义，但有些地方提到 "isomorphic" 表示无论节点值如何，树都具有相同的形状。如果有人能解决这个困惑，那就太好了。
我要讲的是有根子树同构；通过尝试所有根，可以在不考虑效率的情况下处理无根情况。
基本思想是，如果你有树
A B
/|\ /|\
/ | \ / | \
/ | \ / | \
a1 ... am b1 ... bn
/\ /\ /\ /\
并想知道 A 是否是 B 的子树，使得 A 映射到 B，然后对于所有 i和 j，你递归地计算以 ai 为根的子树是否是以 ai 映射到 bj 的方式以 bj 为根的树的子树. （基本情况是当 A 或 B 是叶子时。）现在，每个子树都可映射是不够的，因为如果某些 bj 具有特别丰富的结构，那么几个 ais 可能是子树，但同构的要求不会让它们共享 bj。这就是最大匹配的用武之地：我们尝试以可以映射子树的方式将所有 ai 与 bj 匹配。
要解决一般的有根问题，请尝试 B 的所有可能选择。
见here，有子树同构的C#实现。一个蛮力的，我是编码器:)
希望对你有帮助。
我们如何确定给定树 T 是否包含与另一棵树 S 同构的子树？
如果其中一棵树可以通过一系列翻转从另一棵树中获得，则称两棵树是同构的，即通过交换多个节点的左右子节点。任何级别的任何数量的节点都可以交换它们的子节点。两棵空树是同构的。
我在一些地方读到过可以使用二分匹配算法来解决这个问题，但是我找不到任何非付费资源来了解详细信息。似乎有很多关于这个问题的研究论文，其中大部分都再次落后于付费专区，但是我目前对这个问题的最新研究算法不感兴趣。我的问题是二分匹配如何应用于这个问题？
PS：互联网上似乎对"isomorphic"的含义有些混淆。以上是我在大多数地方找到的定义，但有些地方提到 "isomorphic" 表示无论节点值如何，树都具有相同的形状。如果有人能解决这个困惑，那就太好了。
我要讲的是有根子树同构；通过尝试所有根，可以在不考虑效率的情况下处理无根情况。
基本思想是，如果你有树
A B
/|\ /|\
/ | \ / | \
/ | \ / | \
a1 ... am b1 ... bn
/\ /\ /\ /\
并想知道 A 是否是 B 的子树，使得 A 映射到 B，然后对于所有 i和 j，你递归地计算以 ai 为根的子树是否是以 ai 映射到 bj 的方式以 bj 为根的树的子树. （基本情况是当 A 或 B 是叶子时。）现在，每个子树都可映射是不够的，因为如果某些 bj 具有特别丰富的结构，那么几个 ais 可能是子树，但同构的要求不会让它们共享 bj。这就是最大匹配的用武之地：我们尝试以可以映射子树的方式将所有 ai 与 bj 匹配。
要解决一般的有根问题，请尝试 B 的所有可能选择。
见here，有子树同构的C#实现。一个蛮力的，我是编码器:) 希望对你有帮助。