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

\frametitle{Lecture 23 Graphs: Multigraphs}
{\footnotesize Copyright, Michael Monagan and Jamie Mulholland, 2020.}

\vspace{1cm}
Grimaldi 11.1

\vspace{1cm}

\quad \includegraphics[height=3cm]{pseudo.png}

\end{frame}

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

\begin{definition}[ multigraph ]
A {\bf multigraph} $G=(V,E)$ is a set $V$ of vertices,
and a {\em multiset} $E$ of edges where each edge is in $V \times V$.
\end{definition}

Example: $V=\{1,2,3,4\}$, $E=\{ (1,2),(1,2),(2,3),(3,3),(3,4),(4,1) \}$.

\vspace{6cm} 

Simple graphs are multigraphs with no loops and no parallel edges.
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition} [ walks in multigraphs ]
Let $x$ and $y$ be two vertices in a multigraph $G=(V,E)$.
A {\bf walk} in $G$ is a finite alternating sequence
$$ x \, e_1 \, x_1 \, e_2 \, x_3 \, e_3 \dots e_{n-1} \, x_{n-1} \, e_n \, y$$
of vertices $x_i \in V$ and edges $e_i \in E$ with $n\ge 0$ edges.
The {\bf length of the walk} is $n$, the number of edges.
A walk from $x$ to $y$ is called a {\bf closed walk} if $x=y$
and an {\bf open walk} if $x\ne y$.
Note, vertices and edges in walks need not be distinct.
\end{definition}
Convention: Grimaldi allows walks to have length 0 which he calls {\bf trivial walks}.

\medskip
Examples
\vspace{8cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition} [ trails and circuits ]
Let $G$ be a multigraph and $x$ and $y$ be vertices in $G$. \\
A {\bf trail} from $x$ to $y$ is an open walk in $G$ that has no repeated edges.   \\
A {\bf circuit} from $x$ to $x$ is a closed walk in $G$ that has no repeated edges. \\
\end{definition}
Convention: Grimaldi says circuits must have at least 1 edge and cycles 3 edges. \\
We will allow both circuits and cycles to have 1 or more edges.

\medskip
Examples
\vspace{8cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{theorem} [ trails and paths ]
Let $G=(V,E)$ be a multigraph with vertices $a$ and $b$.
If there is a trail in $G$ from $a$ to $b$ then there is a path
in $G$ from $a$ to $b$.
\end{theorem}

\medskip
Proof.

%Amongst the trails in $G$ from $a$ to $b$ let $T$ be one of shortest length.
%Either $T$ is a path or it is not a path.  Suppose $T$ is not a path.
%Then there is a vertex $c$ in $T$ that is visited twice, so $T$ has the form
%$$(a, x_1,\dots,x_{i}, c, y_1, y_2, \dots, y_j, c, z_1, z_2, \dots, z_k, b)$$
%for some some $i \ge 0$, $k \ge 0$, and $\color{red} j \ge 1$, that is,
%with at least one edge between the two occurences of $c$.
%This means there is a trail 
%$$(a, x_1, \dots, x_i, c, z_1, \dots, z_k, b)$$
%from $a$ to $b$ of length less than $T$ contradicting our choice for $T$. \\
%Therefore $T$ is a path.

\vspace{8cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ degree of a vertex in a multigraph ]
If $G=(V,E)$ is a multigraph and $v\in V$, the {\bf degree} of $v$, denoted
$\deg(v)$, is the number of edges incident to $v$.  Here a loop at $v$ counts
as two incident edges.
\end{definition}

\medskip
Example
\vspace{1.5cm}
\begin{theorem} 
Every multigraph $G=(V,E)$ satisfies $\sum_{v \in V} \deg(v) = 2|E|$.
\end{theorem}

Poof.
\vspace{3cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{The Bridges of K\"onigsberg Problem}

\bigskip

\includegraphics[height=3.5cm]{konigsbergfig.jpg}

\bigskip
Question: Is it possible walk around the city, \\
crossing  each bridge exactly once, and end up \\
where you started?

\vspace{6cm}

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
The definitions {\bf subgraph}, {\bf induced subgraph} and {\bf spanning subgraph}
that we made for simple graphs also work for multigraphs.

\begin{definition}[ connected graph and connected components ]
Let $G=(V,E)$ be a multigraph.
We say $G$ is {\bf connected} if for all pairs $u,v \in V$
there is a path from $u$ to $v$.
The {\bf connected components} of $G$ are the maximal connected subgraphs of $G$.
\end{definition}

\bigskip
Example
\vspace{8cm}
\end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\begin{definition}[ directed graphs ]
A {\bf directed graph} or {\bf digraph} $G=(V,E)$ is a set $V$ of vertices and
a set $E$ of edges where edges are {\em ordered pairs} of vertices.
We draw arrows on edges to indicate direction.  If a graph is not directed,
we say it is an {\bf undirected graph}.
\end{definition}

\medskip
Example.  $V=\{1,2,3,4,5\}$, $E=\{(1,2),(2,3),(3,1),(4,1),(3,5)\}$.


\vspace{5.25cm}
We will not study directed graphs in MACM 201.
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\frametitle{Graph Terminology}

\begin{itemize}

\item Graphs are classified as either {\em directed graphs} or {\em undirected graphs.}

\item Simple graphs are graphs with no parallel edges and no loops.

\item Adjacent vertices are also called {\em neighbors}.

\item Graphs are also called {\em networks}.  Usually a network refers
      to a real physical object whereas a graph could be abstract.
      Mathematicians and Computer Scientists usually use ``graphs'' whereas
      Engineers usually use ``networks''.
      Some terminology is different, for example

\medskip
\quad \quad
\begin{tabular}{c|c} 
Graph Theory & Network Science \\ \hline graph & network \\ vertex & node \\ edge & link
\end{tabular} 
     
\end{itemize}

\vspace{6cm}

\end{frame}
