Tree homomorphism

From Wikipedia, the free encyclopedia

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

[edit] Definition

Given a pair of node-labeled trees $T 1$ and $T 2$ , a mapping $φ$ from the nodes of $T 1$ to the nodes of $T 2$ is a tree homomorphism if the following conditions hold:

$φ$ 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 $φ(n 2)$ is a child of $φ(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 $φ(n)$ in $T 2$ .