Tree homomorphism

In computer science, a tree homomorphism is a type of homomorphism defined on trees.

Definition

Given a pair of node-labeled trees $T_1$ and $T_2$ , a mapping $\phi$ from the nodes of $T_1$ to the nodes of $T_2$ is a tree homomorphism if the following conditions hold:

$\phi$ maps the root of $T_1$ to the root of $T_2$ ,
if node $n_2$ is a child of node $n_1$ in $T_1$ , then $\phi(n_2)$ is a child of $\phi(n_1)$ in $T_2$ , and
for every node $n \in T_1$ , the label of $n$ in $T_1$ is the same as the label of $\phi(n)$ in $T_2$ .

Tree homomorphism

Definition

See also