a~tree $C(v)$ selects an adjacent edge~$xy$ and gets merged with some other trees to form
a~component $C(u)$, we add an~edge $uv$ to~$B(T)$ and set its weight to $w(xy)$.
+\figure{bortree.eps}{\epsfxsize}{An octipede and its Bor\o{u}vka tree}
+
\obs
As the algorithm finishes with a~single component after the last phase, the Bor\o{u}vka tree
is really a~tree. All its vertices are on the same level and each internal vertex has
at least two sons. Such trees will be called \df{complete branching trees.}
\lemma
-For every pair of vertices $x,y\in V(T)$, the heaviest edge of the path $T[x,y]$
-has the same weight as the heaviest edge of~$B(T)[x,y]$.
+For every tree~$T$ and every pair of its vertices $x,y\in V(T)$, the heaviest edge
+of the path $T[x,y]$ has the same weight as the heaviest edge of~the path
+$B(T)[x,y]$.
\proof
+Let us denote the path $T[x,y]$ by~$P$ and its heaviest edge by~$h=ab$. Similarly,
+let us use $P'$ for $B(T)[x,y]$ and $h'$ for the heaviest edge of~$P'$.
+
+We will first prove that~$h$ has its counterpart of the same weight in~$P'$,
+so $w(h') \ge w(h)$. Consider the lowest vertex $u$ of~$T$ such that the
+component $C(u)$ contains both $a$ and~$b$, and consider the sons $v_a$ and $v_b$ of~$u$
+for which $a\in C(v_a)$ and $b\in C(v_b)$. As the edge~$h$ must have been
+selected by at least one of these components, assume without loss of generality that
+it was $C(v_a)$, and hence we have $w(uv_a)=w(h)$. We will show that the
+edge~$uv_a$ lies in~$P'$, because exactly one of the endpoints of~$h$ lies
+in~$C(v_a)$. Both endpoints cannot lie there, since it would imply that $C(v_a)$,
+being connected, contains the whole path~$P$, including~$h$. On the other hand,
+if $C(v_a)$ contained neither~$x$ nor~$y$, it would have to be incident with
+another edge of~$P$ different from~$h$, so this lighter edge would be selected
+instead of~$h$.
+
+For the other direction: for any edge~$uv\in P'$, the tree~$C(v)$ is incident
+with at least one edge of~$P$, so the selected edge must be lighter or equal
+to this edge and hence also than~$h$.
\qed
\para
We will make one more simplification: For an~arbitrary tree~$T$, we split each
query path $T[x,y]$ to two half-paths $T[x,a]$ and $T[a,y]$ where~$a$ is the
-lowest common ancestor of~$x$ and~$y$ in~$T$. It is therefore sufficient to
+\df{lowest common ancestor} of~$x$ and~$y$ in~$T$. It is therefore sufficient to
consider only paths which connect a~vertex with one of its ancestors.
Finding the common ancestors is not trivial, but Harel and Tarjan have shown
paths on~$T'$, such that the weights of the heaviest edges of the new paths can
be transformed to the weights of the heaviest edges of the paths in~$Q$ in
linear time.
-The tree $T$ has at most $2n(T)$ vertices. The set~$Q'$ contains
+The tree $T$ has at most $2n(T)$ vertices and $\O(\log n(T))$ levels. The set~$Q'$ contains
at most~$2\vert Q\vert$ paths and each of them connects a~vertex of~$T'$ with one
of its ancestors.
for example because trees are planar (Theorem \ref{planarbor}). The construction of~$T'$
itself adds only a~constant overhead to every step of the algorithm. As~$T'$ has~$m(T)=n(T)-1$
leaves and it is a~complete branching tree, it has at most~$m(T)$ internal vertices,
-so~$n(T')\le 2n(T)$ as promised.
+so~$n(T')\le 2n(T)$ as promised. Since all internal vertices have at least two sons,
+the depth must be logarithmic.
-For each query path $T[x,y]$ we find the lower common ancestor of~$x$ and~$y$
+For each query path $T[x,y]$ we find the lowest common ancestor of~$x$ and~$y$
using Theorem \ref{lcathm} and replace the path by the two half-paths. This
produces a~set~$Q'$ of at most~$2\vert Q\vert$ paths. If we remember the origin
of each of the new paths, the reconstruction of answers to the original queries
\qed
+
+\FIXME{GHT}
+
+
%--------------------------------------------------------------------------------
\section{Special cases and related problems}
projects / saga.git / blobdiff