diff options
| -rw-r--r-- | mgr.tex | 16 |
1 files changed, 8 insertions, 8 deletions
@@ -909,14 +909,14 @@ is the LCA closure of $W$. Let's define $u_i := LCA(v_i, v_{i+1})$. By Observation \ref{lca-observation}, each $u_i$ falls between $v_i$ and $v_{i+1}$ in the infix -order, i.e. $W'$ sorted is the sequence $v_1, u_1, v_2, u_2, \ldots, u_{m - 1}, -v_m$ (note that in the way this sequence is written, some vertices might be -repeated, e.g. it might be the case that $LCA(v_2, v_3) = v_2$, in which case -$u_2$ will be equal to $v_2$). We claim that for every pair of vertices in $W'$, -their LCA is also in $W'$. We'll proceed by induction, and it will be easier if -we now rename the sorted $W'$ to $w_1 := v_1, w_2 := u_2, \ldots, w_{2m-2} := -u_{m-1}, w_{2m - 1} := v_m$. As quick recap, the following are properties of the -sequence of $w_i$'s: +order, i.e. $W'$ sorted by infix numbers is the sequence $v_1, u_1, v_2, u_2, +\ldots, u_{m - 1}, v_m$ (note that in the way this sequence is written, some +vertices might be repeated, e.g. it might be the case that $LCA(v_2, v_3) = +v_2$, in which case $u_2$ will be equal to $v_2$). We claim that for every pair +of vertices in $W'$, their LCA is also in $W'$. We'll proceed by induction, and +it will be easier if we now rename the sorted $W'$ to $w_1 := v_1, w_2 := u_2, +\ldots, w_{2m-2} := u_{m-1}, w_{2m - 1} := v_m$. As quick recap, the following +are properties of the sequence of $w_i$'s: \begin{enumerate} \item For $i < j$, $\infixtable[w_i] \leq \infixtable[w_j]$. |