10.21. Теорема

Если даны два дерева T⚪ и T◎, находящиеся в отношении Д-прообраза-проекции, то применение к ним алгоритма 10.20 порождает ряд деревьев, в котором:

1. соседние члены сами находятся в отношении Д-прообраза-проекции
2. последний член совпадает с T⚪

Доказательство

Первое утверждение очевидно в силу свойству транзитивности отношения Д-прообраза-проекции, связывающих весь ряд построенных деревьев.

Для доказательства второго утверждения достаточно отметить следующие характерные черты последнего члена ряда:

• является деревом (очевидно)
• его корень совпадает с корнем T⚪, что следует из смысла работы алгоритма 10.8, при неизменности полученного корня последующими шагами алгоритма 10.20 (алгоритмов 10.11, 10.14, 10.18)
• его листья совпадают с листьями T⚪, что следует из смысла работы алгоритмов 10.8 и 10.11, при неизменности полученных листьев последующими шагами алгоритма 10.20 (алгоритмов 10.14, 10.18)
• его узлы совпадают с узлами T⚪, что следует из смысла работы алгоритма 10.14, и алгоритма 10.18,

█

Назад Вперёд