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 ${\displaystyle T_{1}}$ and ${\displaystyle T_{2}}$, a mapping ${\displaystyle \phi }$ from the nodes of ${\displaystyle T_{1}}$ to the nodes of ${\displaystyle T_{2}}$ is a tree homomorphism if the following conditions hold:

• ${\displaystyle \phi }$ maps the root of ${\displaystyle T_{1}}$ to the root of ${\displaystyle T_{2}}$,
• if node ${\displaystyle n_{2}}$ is a child of node ${\displaystyle n_{1}}$ in ${\displaystyle T_{1}}$, then ${\displaystyle \phi (n_{2})}$ is a child of ${\displaystyle \phi (n_{1})}$ in ${\displaystyle T_{2}}$, and
• for every node ${\displaystyle n\in T_{1}}$, the label of ${\displaystyle n}$ in ${\displaystyle T_{1}}$ is the same as the label of ${\displaystyle \phi (n)}$ in ${\displaystyle T_{2}}$.

See also

• Homomorphism