Теорема 9.17

Пусть N ВС VSi (i = 1..N) имеют такое произведение, что в его j-ый канал попадают состояния sj ∈ Sj

Тогда для Sj существует некое дерево сборки Tj.

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

Текущая задача - определить алгоритм построения Tj для Sj.

Неформально суть такого алгоритма заключается в добавлении к каждому листу уже построенного для VS1 .. VSk дерева его следующего "фрагмента" - дерева сборки Tk+1 (VSk+1).

Теперь надо доказать, что:
произведение всех состояний от корня до произвольного листа Tj есть некоторое состояние sj ∈ Sj;
и наоборот - каждому состоянию sj ∈ Sj можно сопоставить в дереве Tj некий путь от корня до листа так, что произведение всех состояний на нём оказывалось равно этому состоянию

Такое дерево является деревом сборки, поскольку согласно его определению у него дугам, выходящим из одного узла, приписаны разные состояния одного массива (ключи Tij)

Назад Вперёд