9.21. Теорема

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

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

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

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

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

• является деревом (очевидно)
• его корень совпадает с корнем T⚪, что следует из смысла работы алгоритма 9.7.А, при неизменности полученного корня последующими шагами алгоритма 9.8. (алгоритмов 9.7Б, 9.7В, 9.7Г)
• его листья совпадают с листьями T⚪, что следует из смысла работы алгоритмов 9.7А и 9.7Б, при неизменности полученных листьев последующими шагами алгоритма 9.8. (алгоритмов 9.7В, 9.7Г)
• его узлы совпадают с узлами T⚪, что следует из смысла работы алгоритма 9.7В, и алгоритма 9.7Г,

█

Назад Вперёд