1
$\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.

$\endgroup$
  • $\begingroup$ Yeah, that`s what i meant. $\endgroup$ – Mateus Buarque Mar 13 at 14:36
2
$\begingroup$

Nice conjecture on tree isomorphism. 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.

$\endgroup$
  • $\begingroup$ Thanks, guess i'll have to code AHU anyways. $\endgroup$ – Mateus Buarque Mar 13 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 Mar 13 at 15:51
  • $\begingroup$ @MateusBuarque Here is a hint for the exercise. The answer is simple based on the given counterexample. $\endgroup$ – Apass.Jack Mar 13 at 16:08
  • 1
    $\begingroup$ Finally found it! $\endgroup$ – Mateus Buarque Mar 13 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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