\documentclass[11pt]{article}

\usepackage{precalc}
\usepackage{graphicx}

\begin{document}

\assigntitle{30}{Graph theory}

\term{Graph theory} is the study of \term{graphs}.  But \emph{not} the
kind of ``graphs'' you are used to, like a graph of $y = x^2$---graph
theory graphs are completely different from graphs of
functions.\footnote{Mathematicians seem to have a bad habit of using
  the same word for several different things.  Confusing, isn't it?}

Informally, graphs describe \emph{connections} or \emph{networks}.
But before we say formally what a graph is, let's look at an
example---in fact, \emph{the} example which got graph theory started!

\section{The seven bridges of K\"onigsberg}
\label{sec:bridges}


\begin{figure}[htp]
  \centering
  \includegraphics[width=3in]{diagrams/Konigsberg_bridges.png}
  \caption{The bridges of K\"onigsberg}
  \label{fig:bridges-k}
\end{figure}

The city of Kaliningrad, Russia, is built on both sides of the Pregel
river, and there are two large islands in the middle of the
river. Prior to World War II, the city was called K\"onigsberg, and
there were seven bridges connecting the islands to the rest of the
city, as shown in \pref{fig:bridges-k}. (The bridges are much different
now; some were destroyed in World War II and some were knocked down to
make room for a new highway.)  The story goes that it was a popular
riddle to ask if there was any way to go on a walking tour of the city
in which each bridge was crossed \emph{exactly once}.  Tricky things
like crossing a bridge halfway are not allowed.

\begin{problem}
  It turns out that it isn't possible, so I won't make you try to
  solve it.  But can you make it possible by adding a single bridge?
  Describe where the new bridge could be, and then describe a walking
  tour that crosses each bridge (including the new one) exactly once.
\end{problem}

\topic{Euler and graph theory}
Euler (remember him?) solved the problem of the bridges in 1735, and
in so doing invented the subject of graph theory.

Euler's stroke of genius was to clear away all the detail that didn't
matter and consider the problem in an abstracted setting.  The fact
that the walking tour takes place in a physical city doesn't matter;
for the purposes of the problem, the only things that matter are that
there are four locations (the north bank, the south bank, the west
island, and the east island) and certain connections between them (the
bridges).  Schematically, we can draw the situation as shown in
\pref{fig:bridges}.

\diagramg{pdf}{bridges}{A graph representing the bridges of K\"onigsberg}

N and S represent the north and south banks of the river; W represents
the west island and E represents the east island.  We represent each
separate land area by a dot, and for each bridge we draw a line
between the dots representing the land areas that it connects.

Of course, we haven't really changed anything; but you'd be surprised
how much it helps the human brain to clear away irrelevant detail!  By
making a diagram representing only the relevant information (how the
four land areas are connected by bridges) it becomes a lot easier to
think about the problem.

If you try solving the K\"onigsberg bridge problem, you'll quickly
find that you're getting nowhere---you always seem to end up with one
bridge left to cross but in the totally wrong place.  But this isn't
proof that there's no solution---maybe you just haven't been clever
enough to come up with the solution yet!  How was Euler able to be so
sure that there was no solution?

We'll get to that, but first let's be a bit more formal about what a
graph is.

\section{Graphs}
\label{sec:graphs}

\topic{graph = vertices + edges}
Formally, a graph consists of a collection of \term{vertices} (also
called \term{nodes}), together with a collection of \term{edges}.
Each edge connects two vertices.  The vertices usually are given names
so that you can tell them apart.

\topic{geometry? forget it}
The particular way in which a graph is drawn does not matter; the only
thing that matters is which vertices are connected by edges.  For
example, these two graphs are really the same:

\diagramg{pdf}{bridges-drawings}{Two different drawings of the same graph}

In other words, these are just two different ways to draw the
\emph{same graph}, since they have the same vertices and the same
connections between vertices.  Notice that some of the edges cross
each other in the drawing on the right, but that's perfectly OK.

\begin{problem} \label{prob:graph-equality}
  Which of the following drawings represent the same graph?
  \begin{subproblems}
    \item \includegraphics[height=1.3in]{diagrams/graph1.pdf}
    \item \includegraphics[height=1.3in]{diagrams/graph5.pdf}
    \item \includegraphics[height=1.3in]{diagrams/graph4.pdf}
    \item \includegraphics[height=1.3in]{diagrams/graph2.pdf}
    \item \includegraphics[height=1.3in]{diagrams/graph3.pdf}
  \end{subproblems}
\end{problem}

\subsection{Vertex degree}
\label{sec:degree}

\begin{defn}{degree}
The \term{degree} of a vertex is the number of edges that are
connected to it.
\end{defn}

\begin{problem}
  List the degree of each of the vertices in the graph from part (a)
  of \pref{prob:graph-equality}.
\end{problem}

\begin{problem}
  List the degree of each of the four land areas in K\"onigsberg.
\end{problem}

\begin{problem}
  Graph $G$ has five vertices, and all of the vertices have degree
  $2$.  What does $G$ look like?
\end{problem}

\section{Paths}
\label{sec:paths}

\begin{defn}{path}
A \term{path} in a graph is a sequence of edges whose vertices match
up; that is, a path is any journey that an ant could take as it walks
along edges in the graph.  The \term{length} of a path is the number
of edges in it.
\end{defn}

\diagramg{pdf}{graph6}{An example graph with labeled vertices and
  edges}

For example, consider the graph in \pref{fig:graph6}.  The edges are
labeled so we can easily talk about them.  One example path in this
graph from vertex $1$ to vertex $8$ is the sequence of edges
a-e-f-g-h.  Note that paths can do weird things like reverse
direction, loop back on themselves, and so on---for example,
a-e-d-b-e-f-l is another path from $1$ to $8$; so is a-e-e-e-f-l (the
ant walked back and forth on edge e three times, from $2$ to $5$, then
back to $2$, and then back to $5$).

Note that the graph in \pref{fig:graph6} doesn't have multiple edges
between any vertices, so we can also describe paths by listing the
vertices that the path visits in order: for example, the path
a-e-e-e-f-l can also be described as 1-2-5-2-5-6-8.  Of course, if a
graph has multiple edges between vertices (as, for example, the
K\"onigsberg bridge graph) then you have to actually specify the edges
themselves, because otherwise you wouldn't know which edges to use.

\begin{problem}
  Write down a path from vertex $9$ to vertex $3$.
\end{problem}

\begin{problem}
  Write down a path from vertex $8$ to vertex $4$ which has length $12$.
\end{problem}

\begin{defn}{cycle}
A \term{cycle} is a path which begins and ends at the same vertex. 
\end{defn}

\begin{problem}
  Write down a cycle in the above graph that starts and ends at vertex $3$.
\end{problem}

\subsection{Eulerian paths}
\label{sec:eulerian}

An \term{Eulerian} path, named in honor of Euler, is a path which
includes each edge in a graph exactly once.  Of course, this is
exactly what the K\"onigsberg bridge problem is about: the problem is
to find a walking tour (path) that crosses every bridge (edge) exactly
once.  That's why this kind of path is named after Euler.  So, the
K\"onigsberg bridge problem can be rephrased as, ``Is there an
Eulerian path in the K\"onigsberg bridge graph?''

Interestingly, deciding whether a graph has an Eulerian path is very
easy, as shown by Euler: a graph $G$ has an Eulerian path if and only
if 
\begin{itemize}
\item every vertex in the graph has an even degree, OR
\item exactly two vertices have an odd degree, and all other vertices
  have an even degree.
\end{itemize}

Why is this?  Well, think about visiting some vertex in a graph in the
middle of an Eulerian path.  You come into the vertex along some edge,
and leave along another edge (since you can't use the same edge
twice).  So as long as the vertex has even degree you are OK---every
time you enter the vertex along an unused edge there will be another
unused edge along which you can leave.  If some vertex has an odd
degree then you will get stuck, since at some point there will be
exactly one edge left, and you will be able to enter the vertex but
not leave.  The only exception is if that vertex is at the beginning
or the end of the path, which is why it's OK to have exactly two
vertices with odd degree---those will be the starting and ending
points of the path.

Now that we know this, it's easy to see that the K\"onigsberg bridge
graph is not Eulerian: all four of its vertices have odd degree, which
is too many!

\begin{problem}
  For each graph, write down an Eulerian path, or state that no such
  path exists.
  \begin{subproblems}
    \item \includegraphics{diagrams/graph7.pdf}
    \item \includegraphics{diagrams/graph8.pdf}
    \item \includegraphics{diagrams/graph10.pdf}
    \item \includegraphics{diagrams/graph9.pdf}
  \end{subproblems}
\end{problem}

\subsection{Hamiltonian paths}
\label{sec:hamiltonian}

A \term{Hamiltonian} path, named in honor of the mathematician William
Rowan Hamilton, is a path which visits each \emph{vertex} exactly
once.  Note that it does not matter whether a Hamiltonian path visits
all the edges in a graph.

Interestingly, Hamiltonian paths are \emph{much} harder to find than
Eulerian paths!  There is no efficient way known to tell whether any
given graph has a Hamiltonian path or not, although it is easier for
certain graphs.

\diagramg{pdf}{mystery-graph}{Mystery graph}

\begin{problem}
  What does the graph in \pref{fig:mystery-graph} represent?  What are
  the nodes?  What are the edges?
\end{problem}

\begin{problem}
  Does the graph in \pref{fig:mystery-graph} have a Hamiltonian path?
  If so, write it down; if not, explain how you know there isn't one.
  Explain the significance of your answer as it relates to epic
  roadtrips.
\end{problem}

\end{document}