9. Проекция и сумма деревьев

9.1. Ближайшая общая вершина. Теорема

Для произвольных вершин nd1 .. ndN (N>1), не лежащих на одном пути к корню произвольного дерева, существует единственная вершина nd0, для которой имеется путь минимальной длины в каждую из этих вершин, то есть не существует никакой другой вершины nd00 такой, что:

• из nd00 ведёт путь во все указанные вершины nd1 .. ndN
• nd00 подчинена nd0 (путь от nd0 к любой из nd1 .. ndN проходит через nd00)

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

Построим пути от корня до каждой из указанных nd1 .. ndN.

Если корень - единственная общая их вершина, то это искомая nd0.

В противном случае имеется общий участок (пересечение) этих путей, чей конец, противоположный корню, является искомой nd0. Очевидно, любая другая вершина либо не имеет пути до одной или более указанных nd1 .. ndN, либо этот путь длиннее, чем от выбранной nd0.

Указанная вершина nd0 называется ближайшей общей вершиной для nd1 .. ndN. █

Назад Вперёд