diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-13 16:39:30 +0100 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-13 16:39:51 +0100 |
commit | ee591005f48a9bfd5c3cb8d5f304c86e247ab43c (patch) | |
tree | d55f07da276249cdc40b1a39bce868f4fd62143d /mgr.tex | |
parent | d2b6d18e95a54e9da42bd4be8891bfbc52d168c1 (diff) |
Add subtree with hole figure
Diffstat (limited to 'mgr.tex')
-rw-r--r-- | mgr.tex | 14 |
1 files changed, 14 insertions, 0 deletions
@@ -1059,6 +1059,20 @@ components: doesn't lie on the $w$ to $v$ path. \end{itemize} +\begin{figure} + \centering + \def\svgwidth{0.5\columnwidth} + \input{subtree-with-hole.pdf_tex} + \caption{ + The subtree of $v$ with hole $w$. All its nodes can be partitioned into + the path $u_1, \ldots, u_4 = v$ and the subtrees of $u_1', \ldots, + u_4'$. + }\label{subtree-with-hole-figure} +\end{figure} + +Figure \ref{subtree-with-hole-figure} depicts a subtree with hole labeled +according to this nomenclature. + With our bottom-up computation, we've already computed the new state in $w$. There have been no relabelings in the subtrees of the $u_i'$'s, so we can get their states from the precomputed run of $A$ on the original tree. Now consider |