\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{} %TCIDATA{} %TCIDATA{} %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}[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