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

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

\vspace{1cm}
Grimaldi 12.1, 12.2
\vspace{6cm}


\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ tree ]
A multigraph $G$ is a {\bf tree} if $G$ is connected and $G$ does not contain a cycle.
\end{definition}

\begin{theorem}[ main properties of trees ]
If $T=(V,E)$ is a tree then $|V|=|E|+1$ and secondly, \\
there is a unique path in $T$ between every pair of vertices.
\end{theorem}

\medskip
Examples
\vspace{5cm}

% Mention acyclic
% List all trees with 5 vertices 
% Mention leaf vertices



\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{theorem}[Characterization of Trees]
Let $G=(V,E)$ be a multigraph.  The following statements are equivalent.
\begin{itemize}
\item[(1)] $G$ is connected and has no cycle. ($G$ is a tree)
\item[(2)] $G$ is connected and $|V| = |E|+1$.
\item[(3)] $G$ has no cycle and $|V| = |E|+1$.
\item[(4)] There is a unique path between every pair of vertices in $G$.
\end{itemize}
\end{theorem}

\medskip
Proof.
\vspace{6cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Proof (cont).

\vspace{12cm}
\end{frame}

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

\begin{definition}[ rooted tree ]
A \textbf{rooted tree} $T = (V,E)$ is a tree with a distinguished vertex called 
the \textbf{root}.  For every vertex $v \in V$ the {\bf level} of $v$ is the
length of the path from $v$ to the root.  
Note: the root is the unique vertex at level 0.
\end{definition}

\medskip
Example

\vspace{8cm}

\end{frame}




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

\begin{definition}[ rooted tree terminology ]

\begin{itemize}

\item[$\bullet$] The \textbf{height} of a rooted tree is the maximum level of a vertex.   \\
       A rooted tree consisting of just a root vertex has height 0. 

\item[$\bullet$] Every non-root vertex $v$ at level $i$ is adjacent to exactly one vertex $u$ at level $i-1$.  We call $u$ \emph{the} \textbf{parent} of $v$ and we say that $v$ is \emph{a} \textbf{child} of $u$.

%\item[$\bullet$] A vertex of a rooted tree is \textbf{internal} if it has a child and otherwise we call it \textbf{external}.  Note the root is always internal unless the tree has just one vertex.  

\item[$\bullet$] For every vertex $v$ there is a walk ``up the tree'' to the root obtained by moving to the parent vertex at each step.  If $u$ is another vertex on this walk, we call $u$ an \textbf{ancestor} of $v$ and $v$ a \textbf{descendant} of $u$.
%Note: the root is an ancestor of every other vertex.

\end{itemize}
\end{definition}

\medskip

\includegraphics[height=4.5cm]{treelevels.png}

\end{frame}



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

We are frequently interested in working with rooted trees recursively.
Therefore, it will be helpful to think of a rooted tree as composed 
out of smaller rooted trees.  %Here we provide a basic definition to facilitate this.  

\begin{definition}[ subtree ]
Let $v$ be a vertex of a rooted tree $T$ with level $i$.  
Define $T'$ to be the subgraph of $T$ induced by $v$ together with its descendants.  
Then $T'$ forms a new rooted tree with root vertex $v$.
We say that $T'$ with root $v$ is the \textbf{subtree} of $T$ at $v$.
\end{definition}

\medskip

\includegraphics[height=4.5cm]{treeexample.png}

\end{frame}


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

\begin{definition}[ isomorphism of rooted trees]
Let $T_1, T_2$ be rooted trees with $T_i = (V_i, E_i)$ for $i=1,2$.  We say that $T_1$ and $T_2$ are \textbf{isomorphic} if there exists a bijection $f : V_1 \rightarrow V_2$ satisfying:
\begin{itemize}
\item[(1)]  $\{ f(u), f(v) \} \in E_2 \Leftrightarrow  \{u,v\} \in E_1 $
\item[(2)]  For every $v \in V_1$ the level of $v$ and $f(v)$ is the same. \\
In particular, $f$ sends the root of $T_1$ to the root of $T_2$.
\end{itemize}
\end{definition}

\medskip
Example.

\vspace{5cm}
\end{frame}

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

\begin{definition}
A rooted tree is $m$-\textbf{ary} if every internal node has at most $m$ children.  
A 2-ary tree is called \textbf{binary} tree.  
\end{definition}

\medskip
Exercise.  Find all binary trees with height 0, 1, and 2 up to isomorphism.
 
\vspace{4.5cm}
Let $b_n$ denote the number of binary trees of height at most $n$.
Find $b_0$, $b_1$, $b_2$.

\vspace{1cm}
\end{frame}

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

Use the recursive structure of rooted trees find a recurrence for $b_n$.

\vspace{9cm}

\end{frame}

