patternMinor
Rooted Tree Isomorphism Algorithm
Viewed 0 times
isomorphismalgorithmrootedtree
Problem
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.
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.
Solution
Nice conjecture on tree isomorphism.
However, here is a counterexample.
Exercise. Construct a counterexample using a binary tree.
However, here is a counterexample.
Exercise. Construct a counterexample using a binary tree.
Context
StackExchange Computer Science Q#105529, answer score: 3
Revisions (0)
No revisions yet.