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