21.10. Теорема

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

T0 = (ND0, A0),

T1 = (ND1, A1),

..

TN = (NDN, AN)

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

Тогда этот алгоритм действительно строит дерево композиции, то есть:

1. вершины полученного дерева являются объединением всех вершин исходных деревьев (очевидно)
2. каждая дуга полученного дерева совпадает хотя бы с одной дугой хотя бы одного из исходных деревьев, в силу теоремы 21.3
3. каждое исходное дерево является проекцией полученного, а именно:
   1. вершины каждого исходного дерева являются подмножеством для вершин полученного, что очевидно
   2. каждой дуге исходного в полученном соответствует путь между концами этой дуги, что очевидн
   3. каждая ближайшая общая вершина для некоторых вершин исходного дерева Ti (i=1..N) является таковой для них и в полученном T0, гарантией чего служит алгоритм D

█

Назад Вперёд