Mercurial > latex
changeset 142:c7e07d48caee
fix tree metrics inequality; give nodes a name in bisection argument
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Mon, 02 Jun 2014 22:00:43 +0200 |
| parents | b0f1f2800dce |
| children | 533cc8f9e627 |
| files | minimum_bisection/presentation.pdf minimum_bisection/presentation.tex |
| diffstat | 2 files changed, 6 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/minimum_bisection/presentation.tex Mon Jun 02 12:17:38 2014 +0200 +++ b/minimum_bisection/presentation.tex Mon Jun 02 22:00:43 2014 +0200 @@ -590,7 +590,7 @@ \addtolength{\jot}{.5em} \begin{alignat}{2} d_\ell(u, v) &\leq M_{uv} & \forall u, v \in V\\ - \sum_{u, v \in V} c_{uv} \ell_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} M_{uv} + \sum_{u, v \in V} c_{uv} M_{uv} &\leq \Oh(\log n) \sum_{u, v \in V} c_{uv} d_\ell(u, v) \end{alignat} \endgroup \end{theorem} @@ -911,7 +911,7 @@ \frametitle{Tree Bisections} \begin{lemma}[] - For any tree $T$ and any $S \subseteq V$ we have + For any spanning tree $T$ and any $S \subseteq V$ we have \begin{align} c(\delta(S)) \leq c_T(\delta(S)) \end{align} @@ -932,6 +932,10 @@ \path (el) ++ (-30:2.3) node {\structure{$S$}}; + \draw + (b) node[below=0.05] {\structure{u}} + (j) node[below=0.05] {\structure{v}}; + \begin{pgfonlayer}{marked} \foreach \source/\dest in {b/j,f/c,e/c,e/g} \draw [tree edge, tumblue, dash pattern=on 7pt off 7pt] (\source.center) -- (\dest.center);