Tree homomorphism

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

Definition

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

• $\varphi$ 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 $\varphi (n_2)$ is a child of $\varphi (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 $\varphi (n)$ in $T_2$.

See also

• Homomorphism