0
$\begingroup$

Who has published an answer to these problems?

An isomorphism signature is a function s on the set of all trees with the property that s(T1) = s(T2) if and only if T1 and T2 are isomorphic. Define such a signature.

Many thanks Keith Paton Independent researcher

$\endgroup$
3
  • 1
    $\begingroup$ Are you interested in rooted or in unrooted trees? $\endgroup$
    – Steven
    Commented Mar 19, 2020 at 22:37
  • 2
    $\begingroup$ Can you share what context you encountered this in, what research you've done, and what you've found so far? Also, the title doesn't appear to match the body of the question, so it would be helpful to identify which you are asking about. $\endgroup$
    – D.W.
    Commented Mar 19, 2020 at 22:50
  • $\begingroup$ Might be usefeul: oeis.org/A000055 $\endgroup$
    – frabala
    Commented Mar 20, 2020 at 9:45

1 Answer 1

1
$\begingroup$

If you just want to define such a function, then you can just consider the equivalence relation $\rho$ where $T_1 \rho T_2$ iff $T_1$ and $T_2$ are isomorphic. Partition the set of all trees w.r.t. $\rho$. Let $C(T)$ be the equivalence class in which $T$ belongs and select one representative $T^C$ for each equivalence class $C$. Define $s(T) = T^{C(T)}$.

If you want a signature that can be easily/quickly computed, you can define one recursively. For simplicity I am going to define it over binary strings, but you can interpret this string as an integer. I am also going to assume that you are interested in rooted trees (see below if this is not the case). If $T$ is a singleton let $s(T)=\epsilon$, where $\epsilon$ is the empty string. Otherwise let $r$ be the root of $T$ and $u_1, u_2, \dots, u_\ell$ be the children of $u$ sorted in nondecreasing order of $s(u_i$). Define: $s(T) = \bigcirc_{i=1}^\ell (1 \circ s(u_i) \circ 0)$, where $\circ$ denotes concatenation.

Algorithmically, this amounts to starting with $s(T)=\epsilon$ and performing a DFS visit of $T$: every time that an edge $e$ is traversed append a $0$ (resp. $1$) to $s(T)$ iff $e$ is traversed away (resp. towards) the root. The order in which the children $u_1, \dots, u_\ell$ of a vertex are visited is determined by the values of $s(u_i)$ themselves.

If you are interested in unrooted trees, then you can use the same approach by first rooting $T$ in one of its centers. If $T$ has only one center, then $s(T)$ is unique. If $T$ has two centers, you can select the one that results in the smallest value of $s(T)$ (w.r.t. the lexicographical order).

This has been used, e.g., here in Section 3.1.

$\endgroup$

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.