diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-11-25 17:15:53 +0100 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-11-25 17:15:53 +0100 |
commit | c43e27dfc3418da034eb0601cbc557d61c4083a2 (patch) | |
tree | 4dd1b4393ceacfdc0bf53e5fc085590622327cd3 | |
parent | 1145ace49ac081704bf1a357d74bc9c89a6ed7b7 (diff) |
Reword partitioning
-rw-r--r-- | mgr.tex | 47 |
1 files changed, 34 insertions, 13 deletions
@@ -734,17 +734,37 @@ answering the question in the promised time. Consider a set of tree vertices $W \subseteq V(T)$. We'll say that $W$ is \definedterm{LCA closed} if for every pair of vertices $v, w \in W$, it is the case that $\mathlca(v, w) \in W$ (note that one of $v$ or $w$ might be their -LCA). We also require that the tree's root is in $W$ (just to ensure the -partition we define next covers the whole tree). +LCA). -The \definedterm{subtree of $v$} is $v$ along with all its descendants. -We also consider subtrees with holes: the \definedterm{subtree of $v$ with hole -$w$} is the subtree of $v$ minus the subtree of $w$ (for $w$ a descendant of -$v$). +$W \subseteq V(T)$ is \definedterm{partition ready} if -For an LCA closed set $W$ in tree $T$, we define the \definedterm{LCA partition -with respect to $W$} to be a partition of $T$'s vertices into subtrees, subtrees -with holes, and individual vertices created according to the following rules: +\begin{enumerate} + \item it is LCA closed; + \item it contains the root of the tree; + \item\label{both-subtrees-property} for every $v \in W$, either it has descendants in $W$ in at most one + of its subtrees, or both of its children are elements of $W$. +\end{enumerate} + +We will define the \definedterm{LCA partition with respect to $W$} for a +partition ready subset $W$ of $T$'s vertices. The partition will assign each +vertex to a unique part, and each part will be rooted in an element of $W$ (in +particular, there will be as many parts as elements in $W$). + +Each part will be of one of three types: + +\begin{description} + \item[subtree] A \definedterm{subtree of $v$} is $v$ along with all its descendants; + it is rooted in $v$. + \item[subtree with hole] A \definedterm{subtree of $v$ with hole $w$} is the subtree of $v$ + minus the subtree of $w$ (for $w$ a descendant of $v$); it is rooted in + $v$. + \item[singleton] A singleton vertex $v$, which is the root of such a part. +\end{description} + + +Now, for a partition ready set $W \subseteq V(T)$, the LCA partition of $T$ with +respect to $W$ is a partition into subtrees, subtrees with holes, and +singletons constructed according to the following rules: \begin{enumerate} \item If $v \in W$ is a maximal in $W$ with respect to the ancestor @@ -756,10 +776,11 @@ with holes, and individual vertices created according to the following rules: 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, let - $v_l$ and $v_r$ be $v$'s left and right child, respectively. Treat $v_l$ - and $v_r$ as if they were in $W$ for the purposes of defining the - partition. Put $v$ into a singleton part on its own. + \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 + 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. \end{enumerate} Note that in the last rule, both $v_l$ and $v_r$ will either themselves be |