21.2. Теорема

Если T0 есть композиция деревьев T1 .. TN, то оно единственное.

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

Предположим обратное - существование дерева T0*, отличного от T0. Такое T0* должно иметь те же вершины, что и T0 согласно определению композиция деревьев. Отличие, следовательно, должно заключаться в наличии/отсутствии дуги между некоторыми вершинами nd1 и nd2. Необходимо поэтому рассмотреть последовательно две противоположных ситуации:

1. Среди T1 .. TN присутствует дерево, содержащее дугу (nd1,nd2); тогда оба дерева T0 и T0* также должны содержать эту дугу, поскольку оба являются его прообразами, то есть содержать не меньше дуг, чем их проекция (см. 9.2); значит, неверным является предположение о различии между T0 и T0* в такой дуге и существования другого T0*
2. Среди T1 .. TN отсутствует дерево, содержащее дугу (nd1,nd2) - в этом случае не может существовать T0 либо T0*, которое содержит эту дугу, поскольку это противоречит определению композиции деревьев

█

Назад Вперёд