\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2552}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Thursday, August 21, 2008 14:03:59}
%TCIDATA{LastRevised=Thursday, October 09, 2014 10:24:51}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}

\title{Math 443/543 Graph Theory Notes 4: Connector Problems}
\author{David Glickenstein}
\maketitle

\section{Trees and the Minimal Connector Problem}

Here is the problem: Suppose we have a collection of cities which we want to
connect by a system of railway lines. Also suppose we know the cost of
constructing lines between pairs of cities. How do we construct the system so
that the cost is minimal, regardless of the inconvenience to the passengers.

\begin{definition}
A \emph{network }(or \emph{weighted graph}) is a graph $G$ together with a map
$\phi:E\rightarrow\mathbb{R}$. The function $\phi$ may represent the length of
an edge, or conductivity, or cross-sectional area or many other things.
\end{definition}

Given a network $\left(  G,\phi\right)  ,$ we can define the weight of a
subgraph $H\subset G$ to be
\[
\phi\left(  H\right)  =\sum_{e\in E\left(  H\right)  }\phi\left(  e\right)  .
\]
The problem is then: given two vertices $u_{0},v_{0}\in V\left(  G\right)  ,$
find a $u_{0}v_{0}$-path of smallest weight (where we consider the path as a subgraph).

NOTE: We will assume that $\phi\left(  e\right)  >0$ for the remainder of the
section, as this simplifies exposition.

We are trying to construct a network of minimal cost. Here are some observations:

\begin{itemize}
\item The solution must be connected.

\item The solution should contain no cycles, for if there were any cycles, we
could remove one of the edges to get a smaller cost, and passengers could
still get from one place to the other. Thus we want every edge to be a bridge.
\end{itemize}

Such a graph is called a tree.

\begin{definition}
A graph with no cycles is called a \emph{forest}. A connected graph with no
cycles is called a \emph{tree}.
\end{definition}

Note that each component of a forest is a tree. Trees kind of look like
branches of a tree, which is where the name comes from.

Here are some properties of trees.

\begin{theorem}
Let $u$ and $v$ be two vertices of a tree $G.$ Then there is exactly one
$uv$-path in $G.$
\end{theorem}

\begin{proof}
Since $G$ is connected, there is at least one $uv$-path. Suppose there were
two $uv$-paths, $P=v_{0},v_{1},v_{2},\ldots,v_{k}$ and $P^{\prime}%
=v_{0}^{\prime},v_{1}^{\prime},v_{2}^{\prime},\ldots,v_{k^{\prime}}^{\prime}$
(note that $k$ need not equal $k^{\prime}$). If $P\neq P^{\prime},$ then we
can define $s$ and $f$ as
\begin{align*}
s  &  =\min\left\{  i:v_{i+1}\neq v_{i+1}^{\prime}\right\} \\
f  &  =\max\left\{  i:v_{i-1}\neq v_{i-1}^{\prime}\right\}  .
\end{align*}
We can then construct two disjoint paths between $v_{s}$ and $v_{f},$
producing a cycle. But there are no cycles in $G,$ so we must have
$P=P^{\prime}.$
\end{proof}

Also, recall the following:

\begin{theorem}
If a $\left(  p,q\right)  $-graph $G$ is a tree, then $q=p-1.$
\end{theorem}

We come back to the minimal connector problem.

\begin{definition}
If $G$ is a connected graph, a subgraph $T$ which is a tree and contains every
vertex of $G$ is called a \emph{spanning tree}.
\end{definition}

We wish to find a spanning tree of minimal value. Let's find a particular tree
called an \emph{economy tree}. We construct the subgraph $T_{E}$ starting with
all of the vertices of $G$ and then add edges one at a time:

\begin{enumerate}
\item First add the edge of minimal weight.

\item Continue to add edges of minimal weight unless they would form a cycle
with the previously added edges.

\item Stop when the graph is connected.
\end{enumerate}

Since no cycles are produced and the graph ends up connected and reaching
every vertex, we produce a spanning tree. One might ask whether we can, in
fact do this; that is, is it possible that no edges can be added that would
not result in a cycle, yet the graph is not connected. If the subgraph $T_{E}$
at some stage is not connected, then consider a path between two different
components (which exists since $G$ was connected). If all edges on the path
not already in $T_{E}$ (there must be some) create a cycle when added, then
the two components were already connected (by the other part of the cycle), a contradiction.

Note that the economy tree is not necessarily unique. We may have many of them.

The theorem is that the economy tree solves the minimal connector problem.

\begin{theorem}
Let $\left(  G,\phi\right)  $ be a network. The economy tree $T_{E}$ has
minimal weight among all spanning trees.
\end{theorem}

\begin{proof}
Let $T_{0}$ be a spanning tree of minimal weight. We will show that
$\phi\left(  T_{E}\right)  \leq\phi\left(  T_{0}\right)  ,$ which implies
equality since $\phi\left(  T_{0}\right)  $ is minimal among all spanning
trees. We can order the edges in $T_{E}$ by the weights, i.e., $E\left(
T_{E}\right)  =\left\{  e_{1},e_{2},\ldots,e_{p-1}\right\}  $ where
\[
\phi\left(  e_{i}\right)  \leq\phi\left(  e_{i+1}\right)  .
\]
Now let $e_{j}$ be the first edge in $T_{E}$ which is not in $T_{0}.$ Let
$G_{0}=T_{0}+e_{j}.$ Since $T_{0}$ is a spanning tree, $G_{0}$ must have a
cycle $C.$ Since $T_{E}$ is a tree, there must be an edge $e_{0}$ in $C$ which
is not in $T_{E}.$ In particular, $e_{0}\in T_{0}.$ We can consider the graph
$T_{0}^{\prime}=G_{0}-e_{0},$ which has no cycles and is connected, so it is
also a spanning tree. We notice that
\[
\phi\left(  T_{0}^{\prime}\right)  =\phi\left(  T_{0}\right)  +\phi\left(
e_{j}\right)  -\phi\left(  e_{0}\right)  .
\]
Since $T_{0}$ is minimal, we have
\[
\phi\left(  T_{0}\right)  \leq\phi\left(  T_{0}^{\prime}\right)  =\phi\left(
T_{0}\right)  +\phi\left(  e_{j}\right)  -\phi\left(  e_{0}\right)
\]
and hence
\[
\phi\left(  e_{0}\right)  \leq\phi\left(  e_{j}\right)  .
\]
However, $\phi\left(  e_{j}\right)  $ was chosen to have minimal weight among
edges in $G$ not in $T_{E}$ in the construction, which means we must have
that
\[
\phi\left(  e_{0}\right)  =\phi\left(  e_{j}\right)  .
\]
Thus
\[
\phi\left(  T_{0}^{\prime}\right)  =\phi\left(  T_{0}\right)  .
\]
So $T_{0}^{\prime}$ is also minimal. We now consider $T_{0}^{\prime}$ instead
of $T_{0}.$ We may do the same construction as before, finding the first edge
$e_{j^{\prime}}$ which is in $T_{E}$ but not $T_{0}^{\prime}.$ We note that
$j^{\prime}\geq j+1.$ We may continue to do this until we construct a minimal
spanning tree which is equal to $T_{E}.$
\end{proof}

See Example in Figure 4.11 in C.

Note, the algorithm of constructing the economy tree is called Kruskal's
algorithm. Kruskal's algorithm can give a minimal spanning forest as well.

\section{Shortest path problems and Dijkstra's algorithm}

We consider the shortest path problem: Given a railway network connecting
various towns, determine the shortest route between a given pair of towns.

Often, we will refer to the the weight of an edge as a length and the value of
the smallest weight as the distance. We will present the algorithm of Dijkstra
and Whiting-Hillier (found independently). In the sequel, we will assume that
$\phi$ is defined on all pairs of vertices and $\phi\left(  uv\right)
=\infty$ if $uv\notin E\left(  G\right)  .$

\begin{definition}
The \emph{distance} between two vertices $u,v\in V\left(  G\right)  $ is equal
to
\[
d\left(  u,v\right)  =d_{G}\left(  u,v\right)  =\min\left\{  \phi\left(
P\right)  :P\text{ is a path from }u\text{ to }v\right\}  .
\]
A path $P$ which attains the minimum is called a \emph{shortest path}.
\end{definition}

We then have the following algorithm, known as Dijkstra's algorithm:

\begin{enumerate}
\item Let $\ell\left(  u_{0}\right)  =0$ and let $\ell\left(  v\right)
=\infty$ for all $v\neq u_{0}.$ Let $S_{0}=\left\{  u_{0}\right\}  $ and let
$i=0.$

\item For each $v\in S_{i}^{c},$ replace $\ell\left(  v\right)  $ with
\[
\min_{u\in S_{i}}\left\{  \ell\left(  v\right)  ,\ell\left(  u\right)
+\phi\left(  uv\right)  \right\}  .
\]


\item Compute $M$ to be
\[
M=\min_{v\in S_{i}^{c}}\left\{  \ell\left(  v\right)  \right\}
\]
and let $u_{i+1}$ be the vertex which attains $M.$

\item Let $S_{i+1}=S_{i}\cup\left\{  u_{i+1}\right\}  .$

\item If $i=p-1,$ stop. If $i<p-1,$ then replace $i$ with $i+1$ and goto step
2.\bigskip
\end{enumerate}

\begin{lemma}
If $v_{0},v_{1},\ldots,v_{k}$ is a shortest path, then $v_{0},v_{1}%
,\ldots,v_{j}$ is a shortest path for any $j\leq k.$
\end{lemma}

\begin{proof}
If there were a shorter path from $v_{0}$ to $v_{j},$ then we could replace
the current path with a shorter beginning and get a shorter path to $v_{k}.$
\end{proof}

Let's prove that at the termination of the algorithm, $\ell\left(  u\right)
=d\left(  u,u_{0}\right)  .$ We will induct on $i.$ Clearly, this is true for
$i=0.$ We will make the following inductive hypothesis:

\begin{itemize}
\item For every $u\in S_{i},$ $\ell\left(  u\right)  =d\left(  u,u_{0}\right)
$.
\end{itemize}

We have the base case, so we need only prove the inductive step. Suppose it is
true for $S_{i}.$ We must show that
\[
d\left(  u_{0},u_{i+1}\right)  =\ell\left(  u_{i+1}\right)  .
\]
Let $P=v_{0},v_{1},v_{2},\cdots,v_{k},$ where $v_{0}=u_{0}$ and $v_{k}%
=u_{i+1},$ be a $u_{0}u_{i+1}$-path such that
\[
d\left(  u_{0},u_{i+1}\right)  =\phi\left(  P\right)  .
\]
If $v_{k-1}\in S_{i},$ then the path $P^{\prime}=v_{0},v_{1},v_{2}%
,\cdots,v_{k-1}$ is a shortest path and by the inductive hypothesis
$\phi\left(  P^{\prime}\right)  =\ell\left(  v_{k-1}\right)  .$ Thus
\[
d\left(  u_{0},u_{i+1}\right)  =\phi\left(  P\right)  =\ell\left(
v_{k-1}\right)  +\phi\left(  v_{k-1}u_{i+1}\right)  \geq\ell\left(
u_{i+1}\right)
\]
but since $d\left(  u_{0},u_{i+1}\right)  $ is the minimum length path and
$\ell\left(  u_{i+1}\right)  $ is the length of some path, then we must have
equality. Thus the inductive step is proven if $v_{k-1}\in S_{i}$.

We now show $v_{k-1}\in S_{i}.$ Take the smallest $j$ such that $v_{j}\notin
S_{i}.$ Then since $P_{j}=v_{0},v_{1},\ldots,v_{j}$ is a shortest path, we
have, since $v_{j-1}\in S_{i},$ that
\[
\ell\left(  v_{j}\right)  \leq\ell\left(  v_{j-1}\right)  +\phi\left(
v_{j-1}v_{j}\right)  =\phi\left(  P_{j}\right)  \leq\phi\left(  P\right)
\leq\ell\left(  u_{i+1}\right)  .
\]
since $\ell\left(  u_{i+1}\right)  =\min\left\{  \ell\left(  u\right)  :u\in
S_{i}^{c}\right\}  ,$ that means that all of the inequalities are equalities
and $j=k$ (since $P_{j}=P$) and $v_{k-1}\in S_{i}.$ By the previous argument,
we are done.

We do not discuss the complexity of this algorithm. It turns out to be a good algorithm.


\end{document}