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

See also

• Homomorphism