21.9. Теорема

Пусть даны деревья

T0 = (ND0, A0),

T1 = (ND1, A1),

..

TN = (NDN, AN)

такие, что T0 является результатом применения алгоритма 21.6 к деревьям T1 .. TN.

Тогда для каждой дуги a0 = (ndb, nde) из T0, в T1 .. TN найдётся дерево Ti, чья дуга ai совпадает с a0.

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

Если предположить обратное – существование такой дуги a0 = (ndb, nde) дерева T0, которая не принадлежащая ни одному из исходных T1 .. TN, то:

• сумма T1 .. TN также не должна содержать а (следования между ndb и nde), следовательно

o замыкание по транзитивности такой суммы, то есть по сути T0, также не должно содержать никакого следования между ndb и nde,

что говорит об ошибочности предположения. █

Назад Вперёд