3
$\begingroup$

I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:

Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$. Namely, the size of the subtree of $u$. Now Let $L_{i}$ = {$S_{u}$ : $lvl(u)$ = $i$}. Here, $lvl(v)$ denotes the level of $v$. Also the height of a tree is the maximum level of any of its nodes.

Now the conjecture:

Let $H_{1}$ and $H_{2}$ be the heights of the rooted trees $T_{1}$ and $T_{2}$, respectively. $T_{1}$ and $T_{2}$ are isomorphic if and only if $H_{1} = H_{2}$ and for every integer $i \in [ \,1,H_{1}] \, $, the multiset $L_{i}$ of $T_{1}$ and that of $T_{2}$ are the same.

Apparently this conjecture is false because i implemented a C++ program (to solve a competitive programming task) that is based on it, but it failed system tests. Still, it may be an implementation fault, so i'd like to know if there are any counterexamples to this conjecture.

Improve this question
$\endgroup$
1
  • $\begingroup$ Yeah, that`s what i meant. $\endgroup$
    – Mateus Buarque
    Commented Mar 13, 2019 at 14:36

1 Answer 1

Reset to default
3
$\begingroup$

Nice conjecture on tree isomorphism.

However, here is a counterexample.

rooted tree made possible by graphonline by authors of Graphanalyzer

rooted tree made possible by graphonline by authors of Graphanalyzer

Exercise. Construct a counterexample using a binary tree.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, guess i'll have to code AHU anyways. $\endgroup$
    – Mateus Buarque
    Commented Mar 13, 2019 at 15:34
  • $\begingroup$ I don't think it's possible to do so, at least not with the same approach you used on your counterexample. That's because at the level above the leafs you can only have 1 or 2 as a subtree size, so any shuffling between those that maintains the sum of the subtree of nodes above would result in two parts that are congruent to the previous two (before you shuffled). $\endgroup$
    – Mateus Buarque
    Commented Mar 13, 2019 at 15:51
  • $\begingroup$ @MateusBuarque Here is a hint for the exercise. The answer is simple based on the given counterexample. $\endgroup$
    – John L.
    Commented Mar 13, 2019 at 16:08
  • 1
    $\begingroup$ Finally found it! $\endgroup$
    – Mateus Buarque
    Commented Mar 13, 2019 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.