diff options
| -rw-r--r-- | mgr.tex | 23 |
1 files changed, 13 insertions, 10 deletions
@@ -770,14 +770,14 @@ singletons constructed according to the following rules: \item If $v \in W$ is a maximal in $W$ with respect to the ancestor relation $<$ (i.e. there are no other elements of $W$ in the subtree of $v$), then the subtree of $v$ is a part of the partition. - \item If $v \in W$ has descendants that are in $W$ only in its left subtree, - let $w$ be the highest such descendant (there is a unique highest - descendant because $W$ is LCA closed). The subtree of $v$ with hole $w$ - is a part of the partition. + \item If $v \in W$ has descendants that are in $W$ only in its left child's + subtree, let $w$ be the highest such descendant (there is a unique + highest descendant because $W$ is LCA closed). The subtree of $v$ with + hole $w$ is a part of the partition. \item Symmetrically if $v \in W$ only has descendants that are in $W$ in its - right subtree. - \item If $v \in W$ has descendants that are in $W$ in both its subtrees we - know that $v$'s left and right child are also elements of $W$ by + right child's subtree. + \item If $v \in W$ has descendants that are in $W$ in both its children's + subtrees we know that $v$'s children are also elements of $W$ by property \ref{both-subtrees-property} of being partition ready. Put $v$ into a singleton part on its own, all the other elements of its subtree were assigned to parts when its children were handled. @@ -796,8 +796,9 @@ Take a set of $m$ tree vertices $W$ and consider the following procedure: \begin{enumerate} \item Let $W'$ be $W$ with the tree's root added. \item\label{partition-ready-lca-step} Let $W''$ be the LCA closure of $W'$. - \item\label{partition-ready-last-step} Let $W'''$ be $W''$ plus, for every element of $W''$ that has - elements of $W''$ in both its subtrees, the element's both children. + \item\label{partition-ready-last-step} Let $W'''$ be $W''$ plus, for every + element of $W''$ that has elements of $W''$ in both its children's + subtrees, the element's both children. \end{enumerate} \begin{claim} @@ -819,7 +820,9 @@ of partition readiness won't be satisfied. What we will show is that no other new vertices need to be added. Take $v \in W''$ that had descendants in $W''$ in both its subtrees, let $v_l$ and $v_r$ be its left and right child, respectively. Without loss of generality, suppose $v_l$ was not an element of -$W''$. Then we claim that it has descendants in $W''$ in only one of its +$W''$. The only reason we would need to add even more vertices after adding +$v_l$ would be if $v_l$ had descendants in both its children's subtrees in +$W'''$. First let's show that it has descendants in $W''$ in at most one of its subtrees. Indeed, if it did have descendants from $W''$ in both its subtrees, $W''$ wouldn't have been LCA closed -- $v_l$ would have been the LCA of the topmost members of $W''$ of its left and right subtrees. Note that newly added |