X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=lib%2Fexamples%2Fbeamerlyxexample1.lyx;h=b4ee35edf3ae499f0f25da244d8ef1e5351d760b;hb=a1add5e8045905bbeb7747e463f5bb95e221346f;hp=a59c85925fcca9c41243e4d313f395eb6fb4a759;hpb=f037f9bace3e9a436d2acd1f3e84137cd86fda5c;p=lyx.git diff --git a/lib/examples/beamerlyxexample1.lyx b/lib/examples/beamerlyxexample1.lyx index a59c85925f..b4ee35edf3 100644 --- a/lib/examples/beamerlyxexample1.lyx +++ b/lib/examples/beamerlyxexample1.lyx @@ -1,5 +1,5 @@ -#LyX 2.0 created this file. For more info see http://www.lyx.org/ -\lyxformat 413 +#LyX 2.1 created this file. For more info see http://www.lyx.org/ +\lyxformat 474 \begin_document \begin_header \textclass beamer @@ -158,13 +158,13 @@ \font_roman times \font_sans default \font_typewriter default +\font_math auto \font_default_family default \use_non_tex_fonts false \font_sc false \font_osf false \font_sf_scale 100 \font_tt_scale 100 - \graphics default \default_output_format default \output_sync 0 @@ -175,15 +175,24 @@ \use_hyperref false \papersize default \use_geometry false -\use_amsmath 2 -\use_esint 0 -\use_mhchem 1 -\use_mathdots 1 +\use_package amsmath 2 +\use_package amssymb 2 +\use_package cancel 0 +\use_package esint 0 +\use_package mathdots 1 +\use_package mathtools 0 +\use_package mhchem 1 +\use_package stackrel 0 +\use_package stmaryrd 0 +\use_package undertilde 0 \cite_engine basic +\cite_engine_type default +\biblio_style plain \use_bibtopic false \use_indices false \paperorientation portrait \suppress_date false +\justification true \use_refstyle 0 \index Index \shortcut idx @@ -219,12 +228,12 @@ Till Tantau \end_layout \begin_layout Institute -International Computer Schience Institute +International Computer Science Institute \begin_inset Newline newline \end_inset Berkeley, California -\begin_inset Argument +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout @@ -240,10 +249,20 @@ ICSI January 30th, 2004 \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Outline \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset CommandInset toc LatexCommand tableofcontents @@ -264,13 +283,10 @@ status collapsed \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout @@ -279,26 +295,14 @@ status collapsed \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - % of every subsection. \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -AtBeginSubsection[]{ -\end_layout - -\begin_layout Plain Layout - +AtBeginSubsection[]{% \end_layout \begin_layout Plain Layout @@ -310,10 +314,6 @@ frame{ \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash frametitle{Outline} @@ -321,19 +321,11 @@ frametitle{Outline} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash tableofcontents[current,currentsubsection] \end_layout -\begin_layout Plain Layout - -\end_layout - \begin_layout Plain Layout } @@ -341,10 +333,6 @@ tableofcontents[current,currentsubsection] \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - } \end_layout @@ -361,10 +349,20 @@ Introduction What are Tournaments? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Consist of Jousts Between Knights \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -387,90 +385,78 @@ begin{pgfpicture}{1.25cm}{-1cm}{7cm}{4cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodebox{A}[virtual]{ \backslash -pgfxy(2,1)}{ -\backslash -pgfuseimage{knight1}}{2pt}{2pt} +pgfxy(2,1)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight1}}{2pt}{2pt} \end_layout \begin_layout Plain Layout - + \backslash pgfnodebox{B}[virtual]{ \backslash -pgfxy(6,1)}{ -\backslash -pgfuseimage{knight2}}{2pt}{2pt} +pgfxy(6,1)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight2}}{2pt}{2pt} \end_layout \begin_layout Plain Layout - + \backslash pgfnodebox{C}[virtual]{ \backslash -pgfxy(4,-1)}{ -\backslash -pgfuseimage{knight3}}{2pt}{2pt} +pgfxy(4,-1)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight3}}{2pt}{2pt} \end_layout \begin_layout Plain Layout - + \backslash pgfnodebox{D}[virtual]{ \backslash -pgfxy(4,3)}{ -\backslash -pgfuseimage{knight4}}{2pt}{2pt} -\end_layout - -\begin_layout Plain Layout - +pgfxy(4,3)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfuseimage{knight4}}{2pt}{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<3->{ \backslash @@ -481,17 +467,9 @@ pgfarrowto}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -only<2->{ -\end_layout - -\begin_layout Plain Layout - +only<2->{% \end_layout \begin_layout Plain Layout @@ -503,10 +481,6 @@ pgfsetlinewidth{0.6pt} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{B} @@ -514,10 +488,6 @@ pgfnodeconnline{A}{B} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{C} @@ -525,10 +495,6 @@ pgfnodeconnline{A}{C} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{D}{A} @@ -536,10 +502,6 @@ pgfnodeconnline{D}{A} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{C}{B} @@ -547,10 +509,6 @@ pgfnodeconnline{C}{B} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{B}{D} @@ -558,17 +516,14 @@ pgfnodeconnline{B}{D} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -pgfnodeconnline{C}{D}} +pgfnodeconnline{C}{D} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout @@ -588,12 +543,11 @@ end{pgfpicture} \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{What is a Tournament?} +What is a Tournament? \end_layout \end_inset @@ -603,12 +557,11 @@ status collapsed \begin_deeper \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<1-> +1- \end_layout \end_inset @@ -617,12 +570,11 @@ A group of knights. \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<2-> +2- \end_layout \end_inset @@ -631,12 +583,11 @@ Every pair has a joust. \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<3-> +3- \end_layout \end_inset @@ -646,10 +597,25 @@ In every joust one knight wins. \end_deeper \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments are Complete Directed Graphs \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Columns \end_layout @@ -672,33 +638,21 @@ begin{pgfpicture}{1.5cm}{-1cm}{6.5cm}{4cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{A}{ \backslash @@ -707,11 +661,7 @@ pgfxy(2.5,1)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{B}{ \backslash @@ -720,11 +670,7 @@ pgfxy(5.5,1)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{C}{ \backslash @@ -733,11 +679,7 @@ pgfxy(4,-0.5)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{D}{ \backslash @@ -746,30 +688,14 @@ pgfxy(4,2.5)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -780,11 +706,7 @@ pgfbox[center,center]{$v_2$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -795,11 +717,7 @@ pgfbox[center,center]{$v_3$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -810,11 +728,7 @@ pgfbox[center,center]{$v_4$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -825,30 +739,14 @@ pgfbox[center,center]{$v_1$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetendarrow{ \backslash @@ -857,98 +755,62 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepstart{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepend{4pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{B} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{A}{C} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{D}{A} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{C}{B} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{B}{D} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodeconnline{D}{C} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash end{pgfpicture} @@ -964,12 +826,11 @@ end{pgfpicture} \end_layout \begin_layout Definition -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout - -<2-> +2- \end_layout \end_inset @@ -1000,27 +861,41 @@ any two different vertices. \end_deeper \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -[<+>] ++ \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Tournaments Arise Naturally in Different Situations \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Applicatins in Ordering Theory} +Applications in Ordering Theory \end_layout \end_inset @@ -1044,12 +919,11 @@ The comparison relation may be cyclic, however. \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Applications in Sociology} +Applications in Sociology \end_layout \end_inset @@ -1073,12 +947,11 @@ Reviewers decide for any two candidates whom they prefer. \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Applications in Structural Complexity Theory} +Applications in Structural Complexity Theory \end_layout \end_inset @@ -1107,110 +980,154 @@ It chooses from any two words the one more likely to be in . \end_layout +\end_deeper \end_deeper \begin_layout Subsection What Does ``Finding Paths'' Mean? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout ``Finding Paths'' is Ambiguous \end_layout -\begin_layout Block -\begin_inset ERT -status collapsed +\end_inset -\begin_layout Plain Layout -{ -\backslash -strut Input for -\backslash -ignorespaces -\backslash -def -\backslash -par{}% because LyX inserts superfluous paragraphs \end_layout +\begin_deeper +\begin_layout Block +\begin_inset Argument 2 +status open + \begin_layout Plain Layout +Input for +\begin_inset Flex Only +status open -\end_layout +\begin_layout Plain Layout +\begin_inset Argument 1 +status open \begin_layout Plain Layout +1 +\end_layout +\end_inset -\backslash -only<1>{Path Finding Problems} -\backslash -ignorespaces +Path Finding Problems \end_layout +\end_inset + + +\begin_inset Flex Only +status open + \begin_layout Plain Layout +\begin_inset Argument 1 +status open +\begin_layout Plain Layout +2-3 \end_layout -\begin_layout Plain Layout +\end_inset -\backslash -only<2-3>{$ -\backslash -Lang{reach}$} -\backslash -ignorespaces -\end_layout +\begin_inset Formula $\Lang{reach}$ +\end_inset -\begin_layout Plain Layout \end_layout -\begin_layout Plain Layout +\end_inset -\backslash -only<4-5>{the Construction Problem} -\backslash -ignorespaces -\end_layout +\begin_inset Flex Only +status open \begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +4-5 +\end_layout +\end_inset + +the Construction Problem \end_layout +\end_inset + + +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + \begin_layout Plain Layout +6-7 +\end_layout +\end_inset -\backslash -only<6-7>{the Optimization Problem} -\backslash -ignorespaces +the Optimization Problem \end_layout +\end_inset + + +\begin_inset Flex Only +status open + \begin_layout Plain Layout +\begin_inset Argument 1 +status open +\begin_layout Plain Layout +8-9 \end_layout -\begin_layout Plain Layout +\end_inset + + +\begin_inset Formula $\Lang{distance}$ +\end_inset -\backslash -only<8-9>{$ -\backslash -Lang{distance}$} -\backslash -ignorespaces \end_layout +\end_inset + + +\begin_inset Flex Only +status open + \begin_layout Plain Layout +\begin_inset Argument 1 +status open +\begin_layout Plain Layout +10- \end_layout -\begin_layout Plain Layout +\end_inset + +the Approximation Problem +\end_layout + +\end_inset -\backslash -only<10->{the Approximation Problem}} \end_layout \end_inset @@ -1260,12 +1177,11 @@ target \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - - +only@-9| visible@8- \end_layout \end_inset @@ -1301,12 +1217,11 @@ phantom{p} \end_layout \begin_layout Itemize -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - - +only@10- \end_layout \end_inset @@ -1344,19 +1259,25 @@ nointerlineskip \end_layout \begin_layout Overprint +\begin_inset Argument item:1 +status open + +\begin_layout Plain Layout +1,3,5,7,9,11-12 +\end_layout + +\end_inset + \end_layout \begin_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\begin_layout Columns +\begin_inset Argument 1 +status open \begin_layout Plain Layout - - -\backslash -onslide<1,3,5,7,9,11-12> +t,onlytextwidth \end_layout \end_inset @@ -1364,36 +1285,59 @@ onslide<1,3,5,7,9,11-12> \end_layout -\begin_layout Columns -\begin_inset ERT -status collapsed +\begin_deeper +\begin_layout Standard +\begin_inset Flex Alternative +status open \begin_layout Plain Layout +\begin_inset Argument 1 +status open -[t,onlytextwidth] +\begin_layout Plain Layout +1-2 \end_layout \end_inset -\end_layout +\begin_inset Argument 2 +status open -\begin_deeper -\begin_layout Standard +\begin_layout Plain Layout \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout -\backslash -alt<1-2>{ \backslash column{ \backslash -textwidth}}{ +textwidth} +\end_layout + +\end_inset + + +\end_layout + +\end_inset + + +\begin_inset ERT +status open + +\begin_layout Plain Layout + + \backslash -column{5cm}} +column{5cm} +\end_layout + +\end_inset + + \end_layout \end_inset @@ -1402,12 +1346,11 @@ column{5cm}} \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Example Input} +Example Input \end_layout \end_inset @@ -1747,16 +1690,33 @@ end{pgfpicture} \end_deeper \begin_layout Standard +\begin_inset Flex Only +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +3- +\end_layout + +\end_inset + + \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout \backslash -only<3->{ -\backslash -column{5cm}} +column{5cm} +\end_layout + +\end_inset + + \end_layout \end_inset @@ -1765,12 +1725,21 @@ column{5cm}} \end_layout \begin_layout ExampleBlock -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout +only@3- +\end_layout + +\end_inset -{Example Output} + +\begin_inset Argument 2 +status collapsed + +\begin_layout Plain Layout +Example Output \end_layout \end_inset @@ -1792,44 +1761,28 @@ begin{pgfpicture}{2.5cm}{-0.6cm}{7.5cm}{2.6cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -only<5-8,10->{ -\end_layout - -\begin_layout Plain Layout - +only<5-8,10->{% \end_layout \begin_layout Plain Layout - + \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A}{ \backslash @@ -1838,11 +1791,7 @@ pgfxy(3,1)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B}{ \backslash @@ -1851,11 +1800,7 @@ pgfxy(5,1)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C}{ \backslash @@ -1864,11 +1809,7 @@ pgfxy(4,0)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D}{ \backslash @@ -1877,30 +1818,14 @@ pgfxy(4,2)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -1911,11 +1836,7 @@ pgfbox[center,center]{$t$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -1926,30 +1847,14 @@ pgfbox[center,center]{$s$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfsetendarrow{ \backslash @@ -1958,42 +1863,21 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodesetsepstart{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodesetsepend{4pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<7,12>{ \backslash @@ -2002,11 +1886,7 @@ pgfnodeconnline{A}{B}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<5,11>{ \backslash @@ -2015,11 +1895,7 @@ pgfnodeconnline{A}{C}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<5,7,11-12>{ \backslash @@ -2028,11 +1904,7 @@ pgfnodeconnline{D}{A}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash alert<5,11>{ \backslash @@ -2041,42 +1913,26 @@ pgfnodeconnline{C}{B}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B}{D} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{D}{C} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - } -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash only<3,9>{ \backslash @@ -2091,10 +1947,6 @@ alert{``Yes''}}}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash end{pgfpicture} @@ -2107,15 +1959,13 @@ end{pgfpicture} \end_deeper \end_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\end_deeper +\begin_layout Overprint +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - - -\backslash -onslide<2,4,6,8,10> +2,4,6,8,10 \end_layout \end_inset @@ -2123,13 +1973,13 @@ onslide<2,4,6,8,10> \end_layout +\begin_deeper \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Variants of Path Finding Problems} +Variants of Path Finding Problems \end_layout \end_inset @@ -2138,39 +1988,21 @@ status collapsed \end_layout \begin_deeper -\begin_layout Standard -\begin_inset ERT -status collapsed +\begin_layout Description +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - - -\backslash -usedescriptionitemofwidthas{Approximation Problem:} +2- \end_layout \end_inset - -\end_layout - -\begin_layout Description Reachability \begin_inset space ~ \end_inset -Problem: -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -<2-> -\end_layout - -\end_inset - -Is there a path from +Problem: Is there a path from \begin_inset Formula $s$ \end_inset @@ -2183,25 +2015,33 @@ Is there a path from \end_inset ? +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +Approximation Problem: \end_layout -\begin_layout Description -Construction -\begin_inset space ~ \end_inset -Problem: -\begin_inset ERT -status collapsed -\begin_layout Plain Layout +\end_layout + +\begin_layout Description +\begin_inset Argument item:1 +status open -<4-> +\begin_layout Plain Layout +4- \end_layout \end_inset -Construct a path from +Construction +\begin_inset space ~ +\end_inset + +Problem: Construct a path from \begin_inset Formula $s$ \end_inset @@ -2217,22 +2057,20 @@ Construct a path from \end_layout \begin_layout Description -Optimization -\begin_inset space ~ -\end_inset - -Problem: -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -<6-> +6- \end_layout \end_inset -Construct a shortest path from +Optimization +\begin_inset space ~ +\end_inset + +Problem: Construct a shortest path from \begin_inset Formula $s$ \end_inset @@ -2248,22 +2086,20 @@ Construct a shortest path from \end_layout \begin_layout Description -Distance -\begin_inset space ~ -\end_inset - -Problem: -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -<8-> +8- \end_layout \end_inset -Is the distance of +Distance +\begin_inset space ~ +\end_inset + +Problem: Is the distance of \begin_inset Formula $s$ \end_inset @@ -2287,22 +2123,20 @@ Is the distance of \end_layout \begin_layout Description -Approximation -\begin_inset space ~ -\end_inset - -Problem: -\begin_inset ERT -status collapsed +\begin_inset Argument item:1 +status open \begin_layout Plain Layout - -<10-> +10- \end_layout \end_inset -Construct a path from +Approximation +\begin_inset space ~ +\end_inset + +Problem: Construct a path from \begin_inset Formula $s$ \end_inset @@ -2321,6 +2155,7 @@ Construct a path from approximately their distance. \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout Section @@ -2350,7 +2185,11 @@ pgfdeclareimage[height=2cm,mask=computer-mask,interpolate=true]{computer}{beamer \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Classes L and NL are Defined via \begin_inset Newline newline \end_inset @@ -2358,9 +2197,15 @@ The Classes L and NL are Defined via Logspace Turing Machines \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT -status open +status collapsed \begin_layout Plain Layout @@ -2371,67 +2216,67 @@ begin{pgfpicture}{-0.5cm}{0cm}{8cm}{5cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash -pgfxy(0,4)}{ -\backslash -tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} -\end_layout - -\begin_layout Plain Layout - +pgfxy(0,4)}{% \end_layout \begin_layout Plain Layout \backslash -uncover<2->{ +tape{input tape (read only), $n$ symbols}{}{3401234*3143223=}} \end_layout \begin_layout Plain Layout + +\backslash +uncover<2->{% \end_layout \begin_layout Plain Layout - + \backslash pgfputat{ \backslash -pgfxy(0,0.5)}{ -\backslash -tape{}{output tape (write only)}{10690836937182}}} +pgfxy(0,0.5)}{% \end_layout \begin_layout Plain Layout + +\backslash +tape{}{output tape (write only)}{10690836937182}} \end_layout \begin_layout Plain Layout - -\backslash -uncover<3->{ +} \end_layout \begin_layout Plain Layout + +\backslash +uncover<3->{% \end_layout \begin_layout Plain Layout - + \backslash pgfputat{ \backslash -pgfxy(7,2)}{ +pgfxy(7,2)}{% +\end_layout + +\begin_layout Plain Layout + + \backslash shorttape{work tape (read/write), $O( \backslash @@ -2440,67 +2285,44 @@ log n)$ symbols}{}{42}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash -pgfxy(1.75,2.5)}{ -\backslash -pgfbox[center,center]{ -\backslash -pgfuseimage{computer}}} +pgfxy(1.75,2.5)}{% \end_layout \begin_layout Plain Layout + +\backslash +pgfbox[center,center]{ +\backslash +pgfuseimage{computer}}} \end_layout \begin_layout Plain Layout - } +} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{structure} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetendarrow{ \backslash @@ -2509,22 +2331,14 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfxycurve(1.75,3.5)(1.75,3.75)(0,3.5)(0,3.85) \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash uncover<2->{ \backslash @@ -2533,11 +2347,7 @@ pgfxycurve(1.75,1.5)(1.75,1)(0,1.5)(0,1.05)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash uncover<3->{ \backslash @@ -2546,10 +2356,6 @@ pgfxycurve(2.65,2.5)(3.75,2.5)(7,1)(7,1.9)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash end{pgfpicture} @@ -2560,17 +2366,31 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Logspace Turing Machines Are Quite Powerful \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Deterministic logspace machines can compute} +Deterministic logspace machines can compute \end_layout \end_inset @@ -2597,12 +2417,11 @@ reachability in forests. \end_layout \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Non-deterministic logspace machines can compute} +Non-deterministic logspace machines can compute \end_layout \end_inset @@ -2624,20 +2443,45 @@ satisfiability with two literals per clause. \end_layout \end_deeper -\begin_layout BeginFrame -\begin_inset ERT +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout +1 +\end_layout + +\end_inset -<1>[label=hierarchy] + +\begin_inset Argument 3 +status collapsed + +\begin_layout Plain Layout +label=hierarchy \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity Class Hierarchy \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -2651,22 +2495,14 @@ begin{pgfpicture}{-5.4cm}{0cm}{5.4cm}{5.5cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.8pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash heap{5.5}{3.5}{$ \backslash @@ -2675,22 +2511,14 @@ Class P$}{black}{1} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetdash{{2pt}}{0pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<2->{ \backslash @@ -2701,11 +2529,7 @@ Class{NC}^2$}{black!50!structure}{2}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash heap{3.5}{2.5}{$ \backslash @@ -2714,11 +2538,7 @@ Class{NL}$}{black!50!structure}{3} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash heap{2.5}{2}{$ \backslash @@ -2727,109 +2547,85 @@ Class{L}$}{black!50!structure}{4} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<2->{ \backslash heap{1.75}{1.5}{$ \backslash -vphantom{A} +vphantom{A}% +\end_layout + +\begin_layout Plain Layout + + \backslash smash{ \backslash -Class{NC}^1}$}{black!50!structure}{5}} +Class{NC}^1}$}{black!50!structure}{5} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash pgfsetdash{}{0pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<2->{ \backslash heap{1.1}{1}{$ \backslash -vphantom{A} -\backslash -smash{ -\backslash -Class{AC}^0}$}{black}{6}} +vphantom{A}% \end_layout \begin_layout Plain Layout + +\backslash +smash{ +\backslash +Class{AC}^0}$}{black}{6} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{1.0pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{black} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfxyline(-5,0)(5,0) \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash only<1-2>{ \backslash @@ -2840,11 +2636,7 @@ Lang{reach}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<1-2>{ \backslash @@ -2857,19 +2649,7 @@ operatorname{forest}}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash only<2>{ \backslash @@ -2880,11 +2660,7 @@ Lang{addition}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<2>{ \backslash @@ -2903,11 +2679,7 @@ Lang{parity}$}}}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<3-5>{ \backslash @@ -2926,11 +2698,7 @@ Lang{reach}$}}}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<4->{ \backslash @@ -2943,11 +2711,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -2960,11 +2724,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -2977,11 +2737,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -2994,26 +2750,23 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash Lang{reach}_{ \backslash -operatorname{path}}$}}}} +operatorname{path}}$}}} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash only<5->{ \backslash @@ -3026,11 +2779,7 @@ operatorname{tourn}}$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash only<6->{ \backslash @@ -3043,11 +2792,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -3060,11 +2805,7 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash @@ -3075,38 +2816,41 @@ ignorespaces \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash hbox{$ \backslash -Lang{reach}$}}}} +Lang{reach}$}}} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash only<7->{ \backslash -pgfsetdash{{1pt}}{0pt} +pgfsetdash{{1pt}}{0pt}% +\end_layout + +\begin_layout Plain Layout + + \backslash langat{2.375}{``$ \backslash Lang{approx}_{ \backslash -operatorname{tourn}}$''}} +operatorname{tourn}}$''} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout @@ -3121,13 +2865,22 @@ end{pgfpicture} \end_layout -\begin_layout BeginFrame -The Circuit Complexity Classes AC -\begin_inset Formula $^{0}$ -\end_inset +\end_deeper +\begin_layout Separator -, NC -\begin_inset Formula $^{1}$ +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +The Circuit Complexity Classes AC +\begin_inset Formula $^{0}$ +\end_inset + +, NC +\begin_inset Formula $^{1}$ \end_inset , and NC @@ -3141,6 +2894,12 @@ The Circuit Complexity Classes AC Limit the Circuit Depth \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -3156,10 +2915,6 @@ leftmargini{1em} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash nointerlineskip @@ -3171,12 +2926,11 @@ nointerlineskip \end_layout \begin_layout Columns -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -[t] +t \end_layout \end_inset @@ -3190,27 +2944,15 @@ status collapsed \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Circuit Class \begin_inset Formula $\Class{AC}^{0}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3260,27 +3002,15 @@ unbounded fan-in \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Circuit Class \begin_inset Formula $\Class{NC}^{1}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3337,27 +3067,15 @@ bounded fan-in \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Circuit Class \begin_inset Formula $\Class{NC}^{2}$ \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3390,15 +3108,15 @@ bounded fan-in . \end_layout +\end_deeper \end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout - -<2> +2 \end_layout \end_inset @@ -3410,7 +3128,11 @@ hierarchy Standard Complexity Results on Finding Paths \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout All Variants of Finding Paths in Directed Graphs \begin_inset Newline newline \end_inset @@ -3418,6 +3140,12 @@ All Variants of Finding Paths in Directed Graphs Are Equally Difficult \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}$ \end_inset @@ -3475,14 +3203,14 @@ the approximation problem in logspace iff . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout - -<3> +3 \end_layout \end_inset @@ -3490,14 +3218,24 @@ status collapsed hierarchy \end_layout -\begin_layout BeginFrame -FindingPaths in Forests and Directed Paths is Easy, +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout +Finding Paths in Forests and Directed Paths is Easy, \begin_inset Newline newline \end_inset But Not Trivial \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{forest}}$ \end_inset @@ -3532,13 +3270,13 @@ But Not Trivial -complete. \end_layout +\end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout - -<4> +4 \end_layout \end_inset @@ -3554,10 +3292,20 @@ Finding Paths in Tournaments Complexity of: Does a Path Exist? \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of the Tournament Reachability Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition Let \color none @@ -3607,10 +3355,25 @@ there exists a path from \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Tournament Reachability Problem is Very Easy \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem \begin_inset Formula $\Lang{reach}_{\operatorname{tourn}}\in\Class{AC}^{0}$ \end_inset @@ -3623,12 +3386,11 @@ The Tournament Reachability Problem is Very Easy \end_layout \begin_layout AlertBlock -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Implications} +Implications \end_layout \end_inset @@ -3664,14 +3426,14 @@ easier . \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -<5> +5 \end_layout \end_inset @@ -3683,7 +3445,11 @@ hierarchy Complexity of: Construct a Shortest Path \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Finding a Shortest Path Is as Difficult as \begin_inset Newline newline \end_inset @@ -3691,6 +3457,12 @@ Finding a Shortest Path Is as Difficult as the Distance Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition Let \color none @@ -3744,10 +3516,25 @@ the distance of \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Tournament Distance Problem is Hard \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3808,7 +3595,16 @@ in logarithmic space, iff . \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Proof That \begin_inset Formula $\Lang{distance}_{\operatorname{tourn}}$ \end_inset @@ -3816,6 +3612,12 @@ Proof That is NL-complete \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT status collapsed @@ -3833,12 +3635,11 @@ nointerlineskip \end_layout \begin_layout Columns -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -[t,onlytextwidth] +t,onlytextwidth \end_layout \end_inset @@ -3870,16 +3671,10 @@ leftmargini{1.5em} \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Reduce \begin_inset Formula $\Lang{reach}$ \end_inset @@ -3889,12 +3684,6 @@ Reduce \end_inset -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -3904,12 +3693,11 @@ status collapsed \begin_deeper \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - - +alert@1 \end_layout \end_inset @@ -3926,12 +3714,11 @@ Is input \end_layout \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<2-| alert@2-8> +2-| alert@2-8 \end_layout \end_inset @@ -3948,12 +3735,11 @@ Map \end_layout \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<9-| alert@9> +9-| alert@9 \end_layout \end_inset @@ -3975,34 +3761,21 @@ Query: \end_layout \begin_layout Block -\begin_inset ERT -status collapsed +\begin_inset Argument 2 +status open \begin_layout Plain Layout - -{ -\end_layout - -\end_inset - Correctness -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -<10-> +10- \end_layout \end_inset @@ -4012,12 +3785,11 @@ status collapsed \begin_deeper \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<10-| alert@10-11> +10-| alert@10-11 \end_layout \end_inset @@ -4046,12 +3818,11 @@ a length-3 path in \end_layout \begin_layout Enumerate -\begin_inset ERT -status collapsed +\begin_inset Argument item:2 +status open \begin_layout Plain Layout - -<12-| alert@12-13> +12-| alert@12-13 \end_layout \end_inset @@ -4097,33 +3868,21 @@ begin{pgfpicture}{0cm}{-1.25cm}{4.5cm}{3.75cm} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{A}{ \backslash @@ -4132,11 +3891,7 @@ pgfxy(1,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{B}{ \backslash @@ -4145,11 +3900,7 @@ pgfxy(2,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{C}{ \backslash @@ -4158,11 +3909,7 @@ pgfxy(3,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash graphnode{D}{ \backslash @@ -4171,45 +3918,25 @@ pgfxy(4,3.3)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout +\backslash +color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash -color{white} +pgfputat{ +\backslash +pgfnodecenter{A}}{ +\backslash +pgfbox[center,center]{$s$}} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfputat{ -\backslash -pgfnodecenter{A}}{ -\backslash -pgfbox[center,center]{$s$}} -\end_layout - -\begin_layout Plain Layout - -\end_layout -\begin_layout Plain Layout - - \backslash pgfputat{ \backslash @@ -4220,30 +3947,14 @@ pgfbox[center,center]{$t$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash color{beamerexample} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfsetendarrow{ \backslash @@ -4252,33 +3963,21 @@ pgfarrowto} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepstart{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash pgfnodesetsepend{2pt} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<3>{ \backslash @@ -4287,11 +3986,7 @@ pgfnodeconnline{B}{A}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<4>{ \backslash @@ -4300,11 +3995,7 @@ pgfnodeconnline{B}{C}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<5,10-11,13>{ \backslash @@ -4313,11 +4004,7 @@ pgfnodeconnline{C}{D}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - \backslash alert<6,10-11,13>{ \backslash @@ -4326,20 +4013,7 @@ pgfnodeconncurve{A}{C}{45}{135}{15pt}{15pt}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash pgfputat{ \backslash @@ -4352,30 +4026,14 @@ colon$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - \backslash -only<2->{ -\end_layout - -\begin_layout Plain Layout - +only<2->{% \end_layout \begin_layout Plain Layout - + \backslash pgfputat{ \backslash @@ -4388,11 +4046,7 @@ colon$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A1}{ \backslash @@ -4401,11 +4055,7 @@ pgfxy(1,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B1}{ \backslash @@ -4414,11 +4064,7 @@ pgfxy(2,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C1}{ \backslash @@ -4427,11 +4073,7 @@ pgfxy(3,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D1}{ \backslash @@ -4440,19 +4082,7 @@ pgfxy(4,2.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A2}{ \backslash @@ -4461,11 +4091,7 @@ pgfxy(1,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B2}{ \backslash @@ -4474,11 +4100,7 @@ pgfxy(2,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C2}{ \backslash @@ -4487,11 +4109,7 @@ pgfxy(3,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D2}{ \backslash @@ -4500,11 +4118,7 @@ pgfxy(4,1.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A3}{ \backslash @@ -4513,11 +4127,7 @@ pgfxy(1,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B3}{ \backslash @@ -4526,11 +4136,7 @@ pgfxy(2,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C3}{ \backslash @@ -4539,11 +4145,7 @@ pgfxy(3,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D3}{ \backslash @@ -4552,11 +4154,7 @@ pgfxy(4,0.25)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{A4}{ \backslash @@ -4565,11 +4163,7 @@ pgfxy(1,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{B4}{ \backslash @@ -4578,11 +4172,7 @@ pgfxy(2,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{C4}{ \backslash @@ -4591,11 +4181,7 @@ pgfxy(3,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash graphnode{D4}{ \backslash @@ -4604,22 +4190,14 @@ pgfxy(4,-.75)} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - { + { \backslash color{white} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -4630,11 +4208,7 @@ pgfbox[center,center]{$s'$}} \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfputat{ \backslash @@ -4645,1129 +4219,679 @@ pgfbox[center,center]{$t'$}} \begin_layout Plain Layout + } \end_layout \begin_layout Plain Layout - }} +} \end_layout \begin_layout Plain Layout + +\backslash +only<8->{% \end_layout \begin_layout Plain Layout - + +\backslash +pgfsetlinewidth{0.4pt} \end_layout \begin_layout Plain Layout + +\backslash +color{beamerexample!25!averagebackgroundcolor} \end_layout \begin_layout Plain Layout \backslash -only<8->{ +pgfnodeconnline{A2}{C1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{D1} \end_layout \begin_layout Plain Layout - + \backslash -pgfsetlinewidth{0.4pt} +pgfnodeconnline{B2}{A1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{C1} \end_layout \begin_layout Plain Layout - + \backslash -color{beamerexample!25!averagebackgroundcolor} +pgfnodeconnline{B2}{D1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{C2}{D1} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A2}{C1} +pgfnodeconnline{D2}{A1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{D2}{B1} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A2}{D1} +pgfnodeconnline{A3}{C2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A3}{D2} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B2}{A1} +pgfnodeconnline{B3}{A2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{C2} \end_layout \begin_layout Plain Layout - -\backslash -pgfnodeconnline{B2}{C1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{D1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C2}{D1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{D2}{A1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{D2}{B1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A3}{C2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A3}{D2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B3}{A2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B3}{C2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{B3}{D2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{C3}{D2} \end_layout \begin_layout Plain Layout -\end_layout - -\begin_layout Plain Layout - - + \backslash pgfnodeconnline{D3}{A2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{D3}{B2} \end_layout \begin_layout Plain Layout - -\backslash -pgfnodeconnline{D3}{B2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A4}{C3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A4}{D3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B4}{A3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B4}{C3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B4}{D3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C4}{D3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{D4}{A3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{D4}{B3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfsetstartarrow{ -\backslash -pgfarrowto} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A1}{B1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B1}{C1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C1}{D1} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A2}{B2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{C2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C2}{D2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A3}{B3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B3}{C3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C3}{D3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{A4}{B4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B4}{C4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{C4}{D4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfclearstartarrow -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -color{beamerexample} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfsetlinewidth{0.6pt} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - } -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -only<3->{ -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -color<3>{red} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B1}{A2} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B2}{A3} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - -\backslash -pgfnodeconnline{B3}{A4} -\end_layout - -\begin_layout Plain Layout - -\end_layout - -\begin_layout Plain Layout - - } -\end_layout - -\begin_layout Plain Layout - + +\backslash +pgfnodeconnline{A4}{C3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A4}{D3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B4}{A3} \end_layout \begin_layout Plain Layout \backslash -only<4->{ +pgfnodeconnline{B4}{C3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B4}{D3} \end_layout \begin_layout Plain Layout - + \backslash -color<4>{red} +pgfnodeconnline{C4}{D3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{D4}{A3} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B1}{C2} +pgfnodeconnline{D4}{B3} \end_layout \begin_layout Plain Layout + +\backslash +pgfsetstartarrow{ +\backslash +pgfarrowto} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B2}{C3} +pgfnodeconnline{A1}{B1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B1}{C1} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B3}{C4} +pgfnodeconnline{C1}{D1} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{B2} \end_layout \begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{B2}{C2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{C2}{D2} \end_layout \begin_layout Plain Layout +\backslash +pgfnodeconnline{A3}{B3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{C3} \end_layout \begin_layout Plain Layout \backslash -only<5->{ +pgfnodeconnline{C3}{D3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A4}{B4} \end_layout \begin_layout Plain Layout - + \backslash -color<5>{red} +pgfnodeconnline{B4}{C4} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{C4}{D4} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C1}{D2} +pgfclearstartarrow \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{A3}{A1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - -\backslash -alert<11>{ + \backslash -pgfnodeconnline{C2}{D3}} +pgfnodeconncurve{A4}{A2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{A4}{A1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout - -\backslash -alert<12-13>{ + \backslash -pgfnodeconnline{C3}{D4}} +pgfnodeconncurve{B3}{B1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{B4}{B2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - } + +\backslash +pgfnodeconncurve{B4}{B1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{C3}{C1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - + +\backslash +pgfnodeconncurve{C4}{C2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{C4}{C1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout \backslash -only<6->{ +pgfnodeconncurve{D3}{D1}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconncurve{D4}{D2}{135}{-135}{10pt}{10pt} \end_layout \begin_layout Plain Layout - + \backslash -color<6>{red} +pgfnodeconncurve{D4}{D1}{135}{-135}{15pt}{15pt} \end_layout \begin_layout Plain Layout + +\backslash +color{beamerexample} \end_layout \begin_layout Plain Layout - -\backslash -alert<11>{ + \backslash -pgfnodeconnline{A1}{C2}} +pgfsetlinewidth{0.6pt} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - -\backslash -alert<12-13>{ + \backslash -pgfnodeconnline{A2}{C3}} +only<3->{% \end_layout \begin_layout Plain Layout + +\backslash +color<3>{red} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A3}{C4} +pgfnodeconnline{B1}{A2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{A3} \end_layout \begin_layout Plain Layout - } + +\backslash +pgfnodeconnline{B3}{A4} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout + +\backslash +only<4->{% \end_layout \begin_layout Plain Layout + +\backslash +color<4>{red} \end_layout \begin_layout Plain Layout \backslash -only<7->{ +pgfnodeconnline{B1}{C2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B2}{C3} \end_layout \begin_layout Plain Layout - + \backslash -color<7>{red} +pgfnodeconnline{B3}{C4} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - -\backslash -alert<12-13>{ + \backslash -pgfnodeconnline{A1}{A2}} +only<5->{% \end_layout \begin_layout Plain Layout + +\backslash +color<5>{red} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A2}{A3} +pgfnodeconnline{C1}{D2} \end_layout \begin_layout Plain Layout + +\backslash +alert<11>{ +\backslash +pgfnodeconnline{C2}{D3}} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{A3}{A4} +alert<12-13>{ +\backslash +pgfnodeconnline{C3}{D4}} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B1}{B2} +only<6->{% \end_layout \begin_layout Plain Layout + +\backslash +color<6>{red} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B2}{B3} +alert<11>{ +\backslash +pgfnodeconnline{A1}{C2}} \end_layout \begin_layout Plain Layout + +\backslash +alert<12-13>{ +\backslash +pgfnodeconnline{A2}{C3}} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{B3}{B4} +pgfnodeconnline{A3}{C4} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C1}{C2} +only<7->{% \end_layout \begin_layout Plain Layout + +\backslash +color<7>{red} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C2}{C3} +alert<12-13>{ +\backslash +pgfnodeconnline{A1}{A2}} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{A2}{A3} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{C3}{C4} +pgfnodeconnline{A3}{A4} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B1}{B2} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{D1}{D2} +pgfnodeconnline{B2}{B3} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{B3}{B4} \end_layout \begin_layout Plain Layout - + \backslash -pgfnodeconnline{D2}{D3} +pgfnodeconnline{C1}{C2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{C2}{C3} \end_layout \begin_layout Plain Layout - + \backslash -alert<11>{ +pgfnodeconnline{C3}{C4} +\end_layout + +\begin_layout Plain Layout + + \backslash -pgfnodeconnline{D3}{D4}} +pgfnodeconnline{D1}{D2} \end_layout \begin_layout Plain Layout + +\backslash +pgfnodeconnline{D2}{D3} \end_layout \begin_layout Plain Layout - } + +\backslash +alert<11>{ +\backslash +pgfnodeconnline{D3}{D4}} \end_layout \begin_layout Plain Layout +} \end_layout \begin_layout Plain Layout @@ -5782,14 +4906,14 @@ end{pgfpicture} \end_layout +\end_deeper \end_deeper \begin_layout AgainFrame -\begin_inset ERT -status collapsed +\begin_inset Argument 1 +status open \begin_layout Plain Layout - -<6> +6 \end_layout \end_inset @@ -5801,10 +4925,20 @@ hierarchy Complexity of: Approximating the Shortest Path \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Approximators Compute Paths that Are Nearly As Short As a Shortest Path \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition An \color none @@ -5863,7 +4997,16 @@ a path from \end_layout \end_deeper -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout There Exists a Logspace Approximation Scheme for \begin_inset Newline newline \end_inset @@ -5871,6 +5014,12 @@ There Exists a Logspace Approximation Scheme for the Tournament Shortest Path Problem \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem There exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ @@ -5921,13 +5070,13 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \begin_layout AgainFrame -\begin_inset ERT +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout - -<7> +7 \end_layout \end_inset @@ -5935,10 +5084,6 @@ status collapsed hierarchy \end_layout -\begin_layout EndFrame - -\end_layout - \begin_layout Standard \begin_inset Note Note status open @@ -5953,14 +5098,7 @@ fragile \end_inset . - This is not yet supported by LyX, so the frame is created using TeX code. - Note that the -\backslash -begin{frame}[fragile] needs to be preceeded by an -\emph on -EndFrame -\emph default - environment. + LyX has the FragileFrame layout for this. \end_layout \end_inset @@ -5968,42 +5106,12 @@ EndFrame \end_layout -\begin_layout Standard -\begin_inset ERT +\begin_layout FragileFrame +\begin_inset Argument 4 status open \begin_layout Plain Layout - - -\backslash -begin{frame}[fragile] -\end_layout - -\end_inset - - -\end_layout - -\begin_layout Standard -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - - -\backslash -frametitle{ -\end_layout - -\end_inset - Just a frame with a program code listing -\begin_inset ERT -status collapsed - -\begin_layout Plain Layout - -} \end_layout \end_inset @@ -6011,10 +5119,11 @@ status collapsed \end_layout -\begin_layout Standard +\begin_layout FragileFrame This is some program code: \end_layout +\begin_deeper \begin_layout Standard \begin_inset listings lstparams "extendedchars=true,language=Python,numbers=left,stepnumber=3,tabsize=4" @@ -6071,22 +5180,7 @@ pass \end_layout -\begin_layout Standard -\begin_inset ERT -status open - -\begin_layout Plain Layout - - -\backslash -end{frame} -\end_layout - -\end_inset - - -\end_layout - +\end_deeper \begin_layout Section* Summary \end_layout @@ -6095,17 +5189,26 @@ Summary Summary \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Summary \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Summary} +Summary \end_layout \end_inset @@ -6185,12 +5288,11 @@ in tournaments is \end_layout \begin_layout Block -\begin_inset ERT +\begin_inset Argument 2 status collapsed \begin_layout Plain Layout - -{Outlook} +Outlook \end_layout \end_inset @@ -6253,18 +5355,29 @@ beamergotobutton{More Details}} \end_layout +\end_deeper \end_deeper \begin_layout Subsection* For Further Reading \end_layout -\begin_layout BeginFrame +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout For Further Reading \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Standard \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout @@ -6279,7 +5392,6 @@ beamertemplatebookbibitems \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "Moon1968" @@ -6340,7 +5452,6 @@ beamertemplatearticlebibitems \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "NickelsenT2002" @@ -6387,7 +5498,6 @@ Proc. \end_layout \begin_layout Bibliography -\labelwidthstring References \begin_inset CommandInset bibitem LatexCommand bibitem key "Tantau2004b" @@ -6447,20 +5557,17 @@ newblock In press. \end_layout -\begin_layout EndFrame - -\end_layout - +\end_deeper \begin_layout Standard \start_of_appendix \begin_inset ERT -status collapsed +status open \begin_layout Plain Layout \backslash -AtBeginSubsection[]{} +AtBeginSubsection[]{} \end_layout \end_inset @@ -6476,20 +5583,30 @@ Appendix Graphs With Bounded Independence Number \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=independence] +label=independence \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout Definition of Independence Number of a Graph \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Definition The \color none @@ -6519,7 +5636,16 @@ Tournaments have independence number 1. \end_layout -\begin_layout BeginFrame +\end_deeper +\begin_layout Separator + +\end_layout + +\begin_layout Frame +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Results for Tournaments also Apply to \begin_inset Newline newline \end_inset @@ -6527,6 +5653,12 @@ The Results for Tournaments also Apply to Graphs With Bounded Independence Number \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem For each \begin_inset space ~ @@ -6638,21 +5770,36 @@ in graphs with independence number at most . \end_layout +\end_deeper \begin_layout Subsection Finding Paths in Undirected Graphs \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 1 status collapsed \begin_layout Plain Layout +1-2 +\end_layout + +\end_inset + + +\begin_inset Argument 3 +status collapsed -<1-2>[label=undirected] +\begin_layout Plain Layout +label=undirected \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Complexity of Finding Paths in Undirected Graphs \begin_inset Newline newline \end_inset @@ -6660,6 +5807,12 @@ The Complexity of Finding Paths in Undirected Graphs Is Party Unknown. \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Fact \begin_inset Formula $\Lang{reach}_{\operatorname{undirected}}$ \end_inset @@ -6686,20 +5839,43 @@ the reachability problem in logspace iff \begin_layout Itemize the construction problem in logspace iff -\begin_inset ERT -status collapsed +\begin_inset Flex Alternative +status open + +\begin_layout Plain Layout +\begin_inset Argument 1 +status open \begin_layout Plain Layout +1 +\end_layout + +\end_inset + + +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +? +\end_layout + +\end_inset + + +\begin_inset Flex Alert +status open + +\begin_layout Plain Layout +\begin_inset Formula $\Class L=\Class{SL}$ +\end_inset + + +\end_layout + +\end_inset -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{SL}$}} \end_layout \end_inset @@ -6709,20 +5885,43 @@ Class{SL}$}} \begin_layout Itemize the optimization problem in logspace iff -\begin_inset ERT -status collapsed +\begin_inset Flex Alternative +status open \begin_layout Plain Layout +\begin_inset Argument 1 +status open + +\begin_layout Plain Layout +1 +\end_layout + +\end_inset + + +\begin_inset Argument 2 +status open + +\begin_layout Plain Layout +? +\end_layout + +\end_inset + + +\begin_inset Flex Alert +status open + +\begin_layout Plain Layout +\begin_inset Formula $\Class L=\Class{NL}$ +\end_inset + + +\end_layout + +\end_inset -\backslash -alt<1>{?}{ -\backslash -alert{$ -\backslash -Class L = -\backslash -Class{NL}$}} \end_layout \end_inset @@ -6735,25 +5934,36 @@ the approximation problem in logspace iff ?. \end_layout +\end_deeper \end_deeper \begin_layout Subsection The Approximation Scheme is Optimal \end_layout -\begin_layout BeginFrame -\begin_inset ERT +\begin_layout Frame +\begin_inset Argument 3 status collapsed \begin_layout Plain Layout - -[label=optimality] +label=optimality \end_layout \end_inset + +\begin_inset Argument 4 +status open + +\begin_layout Plain Layout The Approximation Scheme is Optimal \end_layout +\end_inset + + +\end_layout + +\begin_deeper \begin_layout Theorem Suppose there exists an approximation scheme for \begin_inset Formula $\Lang{tournament-shortest-path}$ @@ -6837,9 +6047,6 @@ qedhere \end_layout \end_deeper -\begin_layout EndFrame - -\end_layout - +\end_deeper \end_body \end_document