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 ${\displaystyle \phi (n_{2})}$ is a child of ${\displaystyle \phi (n_{1})}$ in $T_{2}$, and
• for every node ${\displaystyle 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