9. Projection and the amount of trees

9.1. Nearest common vertex. Theorem

For arbitrary vertices nd1 .. ndN (N>1), not lying on one path to the root of an arbitrary tree, there is a single vertex nd0, for which there is a path of minimum length to each of these vertices, that is, there is no other vertex nd00 such that:

from nd00 leads the way in all of the top d1 .. dn

nd00 is subordinate to nd0 (the path from d0 to any of nd1 .. ndN goes through nd 00)

Evidence

It can be the following algorithm for finding such nd0.

Build a path from the root to each of these TV1 .. TV.

If the root is the only common vertex, it is the required nd0.

Otherwise, there is a common segment (intersection) of these paths, whose end opposite the root is the sought nd0. Obviously, any other vertex either has no path to one or more of these TV1 .. TV, or this path is longer than the selected tv0.

The specified vertex v0 is called the nearest common vertex for nd1 .. ndN.

Prev Next