From 0fe30fc2bafc5cb7c04806b29bb84634daba451d Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 11 Dec 2021 13:44:39 +0100 Subject: Clarify order --- mgr.tex | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index a9d75cb..fe6aaec 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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]$. -- cgit v1.2.3