Tree homomorphism - Alchetron, The Free Social Encyclopedia

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 ϕ 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 ∈ T 1 , the label of n in T 1 is the same as the label of ϕ ( n ) in T 2 .

References

Tree homomorphism Wikipedia

(Text) CC BY-SA