\normalsize
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\frametitle{Lecture 30: Rooted Trees}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

Grimaldi 12.2

\vspace{1cm}
\quad
\includegraphics[height=4.5cm]{formula.png}

\bigskip
What formula does this tree encode?
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{ Ordered rooted trees }

For some applications it is essential to have not just a rooted tree,
but also an ordering of the children for each internal vertex.  

\bigskip
Example
\bigskip
{

\quad Thesis \\
\quad \quad Ch1 \\
\quad \quad \quad S1.1 \\
\quad \quad \quad S1.2 \\
\quad \quad Ch2 \\
\quad \quad \quad S2.1 \\
\quad \quad \quad S2.2 \\
\quad \quad \quad \quad S2.2.1 \\
\quad \quad \quad S2.3 \\
\quad \quad Ch3
}

\vspace{1cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
How do we walk through and process a rooted tree?


\begin{definition}[ preorder, postorder tree traversals ]

A {\bf preorder traversal} of a tree $T$ first visits the root vertex then
visits, in preorder, the vertices of the subtrees $T_1, T_2, \dots, T_k$ of $T$.

A {\bf postorder traversal} of a tree $T$ visits, in postorder, the vertices of
the subtrees $T_1, T_2, \dots, T_k$ of $T$ then visits the root.
\end{definition}

Example

\vspace{6cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Exercise \ Draw the expression tree for {\bf $\color{blue} (3\times 5)+((7-4)\times 2)$}
and give the postorder traversal.

\vspace{3.5cm}
Preorder is also called Polish notation and postorder is also called
reverse Polish notation.  HP calculators used postorder
and a stack to evaluate expressions.  
\vspace{3.5cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ spanning tree ]
Let $G$ be a connected multigraph.  A subgraph $T$ of $G$ is a {\bf spanning tree} if
$T$ spans $G$ (so $T$ contains all vertices in $G$) and $T$ is a tree.
\end{definition}

\medskip
Example
\vspace{5cm}

Question \ How many spanning trees does $C_n$ have?
\vspace{1cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{theorem} [ existence of spanning trees ]
Every connected multigraph $G=(V,E)$ has a spanning tree. \\
Here are three algorithms to construct a spanning tree in $G$:
\begin{itemize}
\item[(1)] Start from $G$. If there is a cycle $C$ in $G$ delete an edge from $C$.
           Repeat this until $G$ has no cycles. Output $G$.
\item[(2)] Create the graph $H=(V,\phi)$.
           For each edge $e$ in $G$ add $e$ to $H$ if it does not make $H$ have a cycle.
           Output $H$.
\item[(3)] The depth-first-search algorithm.
\end{itemize}
\end{theorem}

Proof (1)

\vspace{5cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}
%\frametitle{ Graph Algorithms }
%
%Consider the graph $G=(V,E)$ where $\color{blue} V=\{1,2,3,4,5,6\}$ and 
%$\color{blue} E=\{\{1,5\},\{5,3\},\{4,1\},\{4,3\},\{2,6\}\}$.
%
%\bigskip
%How can a computer test if $G$ is connected? planar?\\
%If $G$ is connected, how can it find a spanning tree in $G$? \\
%If $G$ is planar, how can it find a planar embedding of $G$?
%
%\bigskip
%Most algorithms need to visit the {\bf neighbors} of a vertex. \\
%{\bf Question:} What is a good way to store the edges?
%
%\begin{definition}[ list of neighbors ]
%The {\bf list of neighbors} representation for $E$ is an array $A$
%of size $n=|V|$ where $A_i$ is the set of neighbors of vertex $i$
%(the vertices adjacent to $i$).
%\end{definition}
%
%\medskip
%Example
%\vspace{1.5cm}
%%[ {2,4}, {1,3}, {2,4}, {1,3}, {6}, {5} ]
%
%{\bf Question:} How do algorithms walk through the graph?
%\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\input{DFS}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Extra space.
\vspace{10cm}
\end{frame}
