How to solve subtree isomorphism using maximum bipartisan correspondence?

Question

How to determine if a given tree T has a subtree isomorphic to another tree S?

Two trees are called isomorphic if one of them can be obtained from the other using a series of upheavals, i.e. by replacing the left and right children of a number of nodes. Any number of nodes at any level can have their children. Two empty trees are isomorphic.

In several places, I read that two-way matching algorithms can be used to solve this problem, but I can’t find non-payment sources for details. It seems that there is a lot of research work on this issue, most of them are again behind paywall, however, at present I am not interested in the latest algorithm for studying this problem. My question is, how does two-way matching apply to this issue?

PS: There seems to be some confusion on the Internet about what is meant by isomorphic. I found the definition above in most places, but some of the places mentioned are “isomorphic” meaning that the trees have the same shape regardless of node values. If someone could eliminate this confusion, that was great too.

Answer 1

I will talk about the root isomorphism of a subtree; an unused case can be handled without regard to efficiency by trying all the roots.

The basic idea is that if you have trees

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

, A B , A B, i j , at ai , bj , ai bj. ( - A B - .) , , bj , ai , bj. : ai bj , .

, B.

Answer 2

. , # . , :) , .