WikiDer > Гомоморфизм дерева

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: «Гомоморфизм дерева» – Новости · газеты · книги · ученый · JSTOR (Январь 2007 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Определение

Учитывая пару корневых деревьев с метками узлов ${ 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 (п_ {2})}$ ребенок ${ displaystyle phi (п_ {1})}$ в ${ displaystyle T_ {2}}$, и
• для каждого узла ${ displaystyle n in T_ {1}}$, этикетка ${ displaystyle n}$ в ${ displaystyle T_ {1}}$ такое же, как ярлык ${ Displaystyle фи (п)}$ в ${ displaystyle T_ {2}}$.

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

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