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

\frametitle{Lecture 32: Weighted Graphs and Minimum Spanning Trees}

{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi 13.2

\vspace{1cm}
\hspace{1.5cm} \includegraphics[height=3.75cm]{weighted.png}

\vspace{1cm}
\end{frame}


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

\begin{definition}[ Weighted Graph ] 
A {\bf weighted graph} $G=(V,E)$ is a multigraph together with
a function $w: E \rightarrow \RR^+$ is called an {\bf edge-weighting}.
\end{definition}

\medskip
Examples
\vspace{7cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ Minimum Spanning Tree ]
Let $G=(V,E)$ be a connected multigraph with edge-weighting $w$. \\
For any subgraph $H=(V',E')$ of $G$, the {\bf weight} of $H$ is 
$$ w(H) = \sum_{e \in E'} w(e). $$
A {\bf minimum spanning tree} is a spanning tree of $G$ of minimum weight. 
\end{definition}

Example.

\vspace{7cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{lemma}[ property of minimum spanning trees ]
Let $G=(V,E)$ be a weighted connected graph.
Let $V_1$ and $V_2$ be a partition of $V$.  Amongst the edges in $G$ with
one vertex in $V_1$ and the other in $V_2$ let $e$ one of minimum weight.
There is a minimum spanning tree in $G$ with $e$ as one of it's edges.
\end{lemma}

\medskip
Proof.

\vspace{8cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Kruskal's algorithm to compute a minimum spanning tree}

Input: a connected multigraph $G=(V,E)$ with an edge-weighting $w$. \\
Output: a mimimal spanning tree of $G$.
\begin{itemize}
\item[1.] Set $E'=\phi$.
\item[2.] Sort the edges in $E$ from least weight to highest weight.
\item[3.] While $(V,E')$ is not connected do \\
\quad  Let $e$ be the next heaviest edge in $E$. \\
\quad  If $(V,E'\cup \{e\})$ does not have a cycle set $E' = E' \cup \{e\}$.
\item[4.] Return the tree $(V,E')$.
\end{itemize}

\medskip
Example

\medskip
\hspace{1.5cm} \includegraphics[height=3.75cm]{weighted.png}

\vspace{1cm}
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Additional Space.

\vspace{12cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
Additional Space.

\vspace{12cm}
\end{frame}
