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 [math]\displaystyle{ T_1 }[/math] and [math]\displaystyle{ T_2 }[/math], a mapping [math]\displaystyle{ \phi }[/math] from the nodes of [math]\displaystyle{ T_1 }[/math] to the nodes of [math]\displaystyle{ T_2 }[/math] is a tree homomorphism if the following conditions hold:

• [math]\displaystyle{ \phi }[/math] maps the root of [math]\displaystyle{ T_1 }[/math] to the root of [math]\displaystyle{ T_2 }[/math],
• if node [math]\displaystyle{ n_2 }[/math] is a child of node [math]\displaystyle{ n_1 }[/math] in [math]\displaystyle{ T_1 }[/math], then [math]\displaystyle{ \phi(n_2) }[/math] is a child of [math]\displaystyle{ \phi(n_1) }[/math] in [math]\displaystyle{ T_2 }[/math], and
• for every node [math]\displaystyle{ n \in T_1 }[/math], the label of [math]\displaystyle{ n }[/math] in [math]\displaystyle{ T_1 }[/math] is the same as the label of [math]\displaystyle{ \phi(n) }[/math] in [math]\displaystyle{ T_2 }[/math].

See also

• Homomorphism