%  Algorithms to find a low-cost Hamiltonian circuit
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Wednesday, April 14, 2010
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=11truein
\pdfhorigin=1.25truein \pdfvorigin=0truein

\font\titlefont=cmbx12
\font\smfont=cmr8

\headline={\hfil}
\footline={\hfil}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newbox\BOX
\setbox\BOX=\vbox{%
\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Algorithms to find a low-cost Hamiltonian circuit in a weighted complete graph}
\smallskip
\centerline{Wednesday, April~14, 2010}
\bigskip
\noindent{\bf Nearest-neighbor algorithm:}
\nobreak\medskip
\item{1.} Specify a starting vertex.
\smallskip
\item{2.} If unvisited vertices remain, go from the current vertex to the
unvisited vertex that gives the least-cost connecting edge.
\smallskip
\item{3.} If no unvisited vertex remains, return to the starting vertex to
finish forming the low-cost Hamiltonian circuit.
\bigskip
\noindent{\bf Cheapest-link algorithm:}
\nobreak\medskip
\item{1.} In the beginning, all edges are acceptable and no edges have been
selected.
\smallskip
\item{2.} From the set of acceptable edges, select the edge of smallest weight.
If there is a tie, select any of the edges with the smallest weight.
\smallskip
\item{3.} If the selected edges do not form a Hamiltonian circuit, then
determine the set of acceptable edges. $\underline{\it Un\/}$acceptable edges
are those that either share one vertex with two selected edges or that would
close a circuit that is not a Hamiltonian circuit. Now repeat step~2.
\smallskip
\item{4.} If the selected edges form a Hamiltonian circuit, that circuit is
your low-cost Hamiltonian circuit.\par}

\null\vfill

\copy\BOX

\vfill\vfill

\copy\BOX

\vfill\eject

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
