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>T_1</math> and <math>T_2</math>, a mapping <math>\phi</math> from the nodes of <math>T_1</math> to the nodes of <math>T_2</math> is a tree homomorphism if the following conditions hold:
* <math>\phi</math> maps the root of <math>T_1</math> to the root of <math>T_2</math>,
* if node <math>n_2</math> is a child of node <math>n_1</math> in <math>T_1</math>, then <math>\phi(n_2)</math> is a child of <math>\phi(n_1)</math> in <math>T_2</math>, and
* for every node <math>n \in T_1</math>, the label of <math>n</math> in <math>T_1</math> is the same as the label of <math>\phi(n)</math> in <math>T_2</math>.

Main Menu

See Also

Main Menu