10.6. Лемма

Любая сумма ячеек дерева T как древо TC является его Д-проекцией.

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

1. вершины TC образуют подмножество всех вершин T (очевидным образом следует из определения суммы ячеек)
2. существование в T пути между любыми вершинами дерева TC очевидно, поскольку в TC любая дуга - это дуга некоторой ячейки T, а любая его ячейка есть Д-проекция T, в котором этот путь существует по её определению
3. то, что некая nd0, являющаяся ближайшей общей вершиной для nd1 .. ndN в TC, таковой является для них и в самом T, доказывается от противного:
   • пусть в T имеется другая вершина nd00, не принадлежащая TC (иначе nd0 не ближайшая в TC), от которой существует такой путь в каждую из nd1 .. ndN, который короче пути к ней от nd0;
   • покажем, что существование такой nd00 противоречит определению суммы ячеек, поскольку говорит о том, что та ячейка TC, у которой корнем служит nd0, таковой являться не должна, так как она оказывается вовсе не ближайшей общей вершиной для своих корней в T - ближайшей оказалась nd00, что противоречит определение ячейки как Д-проекции, сохраняющей отношения с ближайшей общей вершиной;
   • следовательно, исходное предположение неверно, а значит третье условие Д-проекции также истинно

█

Назад Вперёд