Гомоморфизм дерева - Tree homomorphism

В Информатика, а гомоморфизм деревьев это тип гомоморфизм определено на деревья.

Определение

Учитывая пару корневых деревьев с метками узлов ${\displaystyle T_{1}}$ и ${\displaystyle T_{2}}$, а отображение ${\displaystyle \phi }$ из узлов ${\displaystyle T_{1}}$ к узлам ${\displaystyle T_{2}}$ это гомоморфизм деревьев если выполняются следующие условия:

• ${\displaystyle \phi }$ отображает корень ${\displaystyle T_{1}}$ к корню ${\displaystyle T_{2}}$,
• если узел ${\displaystyle n_{2}}$ является дочерним элементом узла ${\displaystyle n_{1}}$ в ${\displaystyle T_{1}}$, тогда ${\displaystyle \phi (n_{2})}$ ребенок ${\displaystyle \phi (n_{1})}$ в ${\displaystyle T_{2}}$, и
• для каждого узла ${\displaystyle n\in T_{1}}$, этикетка ${\displaystyle n}$ в ${\displaystyle T_{1}}$ такое же, как ярлык ${\displaystyle \phi (n)}$ в ${\displaystyle T_{2}}$.

Смотрите также

• Гомоморфизм