% Problem set 5: solutions
% Combinatorial Optimization, SUAMI, summer 2015
% Brian Kell
\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein
% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
\setbox0=\hbox{\fig{#1}}%
\dimen0=0.5\ht0%
\advance\dimen0 by-0.3\ht\strutbox
\lower\dimen0\box0%
}}
% AMSFonts
\input amssym.tex
\font\titlefont=cmbx12 \font\smfont=cmr8 \font\transposefont=cmss8 at6pt
\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent\llap{$\triangleright$\bf\phantom.\enspace}{\bf Solution.}\enspace\ignorespaces}
% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
\parfillskip=0pt \finalhyphendemerits=0 \par}}
\newdimen\pivotwidth \newdimen\pivotdepth
\def\pivot#1{%
\setbox0=\hbox{\vphantom/$#1$}
\pivotdepth=\dp0
\setbox0=\hbox{\vbox{\vskip1pt\hbox{\hskip2pt\box0\hskip2pt}\vskip1pt}}%
\pivotwidth=\wd0 \advance\pivotwidth by0.8pt
\lower\pivotdepth\hbox{\vbox{%
\vskip-1.4pt
\hrule width\pivotwidth height0.4pt depth0.0pt
\hbox{%
\vrule height\ht0 depth\dp0 width0.4pt
\copy0
\vrule height\ht0 depth\dp0 width0.4pt
}%
\hrule width\pivotwidth height0.4pt depth0.0pt
\vskip-1.4pt
}\hskip-2.4pt}%
}
\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\R{{\mathord{\Bbb R}}} \def\Q{{\mathord{\Bbb Q}}}
\def\Z{{\mathord{\Bbb Z}}} \def\N{{\mathord{\Bbb N}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|} \def\rabs{\mathclose|} \def\abs#1{\labs#1\rabs}
\def\implies{\Longrightarrow}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~5: solutions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Consider the problem of determining the least expensive way to
complete a project by a given deadline. When the linear program is formulated,
the objective function has a constant term. For instance, if activities A,~B,
and~C have usual times of 8,~5, and 7~days and can be sped up at a cost of
\$200,~\$150, and \$225 per day, respectively, then the objective function
(i.e., the total speedup cost) is
$$200(8-d_{\rm A})+150(5-d_{\rm B})+225(7-d_{\rm C}),$$
where $d_{\rm A}$,~$d_{\rm B}$, and~$d_{\rm C}$ are duration variables for the
three activities. When expanded, this objective function becomes
$$3925-200d_{\rm A}-150d_{\rm B}-225d_{\rm C},$$
which has the constant term~3925. Describe a way to handle an objective
function with a constant term in the simplex algorithm.
\solution Here are three possible ways to handle an objective function with a
constant term in the simplex algorithm. For an illustration, we will use the
following maximization LP (because we discussed the simplex algorithm as a
maximization algorithm):
$$\eqalign{
{\rm maximize}\quad3x_1+5x_2+17&\cr
{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2\phantom{{}+00}&\le\phantom08\cr
2x_1+\phantom1x_2\phantom{{}+00}&\le12\cr
&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$}.\cr
}$$
\smallskip
\item{1.} Replace the constant term with a variable~$K$ and add an equality
constraint to force $K$ to have the correct value:
$$\eqalign{
{\rm maximize}\quad3x_1+5x_2+K&\cr
{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2\phantom{{}+K}&\le\phantom08\cr
2x_1+\phantom1x_2\phantom{{}+K}&\le12\cr
K&=17\cr
&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$,\quad$K\ge0$}.\cr
}$$
\smallskip
\item{2.} In the equation represented by the objective row in the initial
simplex tableau, the constant term will appear on the right-hand side. In the
example here, we have $z=3x_1+5x_2+17$, so the equation represented by the
objective row in the initial simplex tableau will be $-3x_1-5x_2+z=17$. So,
when writing the initial simplex tableau, enter the constant term at the top of
the RHS column (instead of zero):
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut$#$&\quad\hfil\strut$#$&\quad\hfil\strut$#$%
&\quad\hfil\strut$#$&\quad\hfil\strut$#$\quad&\vrule#&\quad\hfil\strut$#$\quad\cr
x_1&x_2&s_1&s_2&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-3&-5&0&0&1&&17\cr
\omit&\omit&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&height2pt\cr
1&1&1&0&0&&8\cr
2&1&0&1&0&&12\cr}}$$
\smallskip
\item{3.} Ignore the constant term entirely during the simplex algorithm and
just remember to add it to the optimal objective value at the end. For the
example, solve the following linear program instead, and then add~17 to the
optimal objective value:
$$\eqalignno{
{\rm maximize}\quad3x_1+5x_2&\cr
{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2&\le\phantom08\cr
2x_1+\phantom1x_2&\le12\cr
&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$}.&\hbox{\qed}\cr
}$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem What is the greatest possible number of critical paths in a project
with $n$~activities? Describe a family of examples for infinitely many values
of~$n$ that attain this number of critical paths.
\solution Consider a project with $n$~activities. We shall make the following
assumptions: First, there are no circular dependencies, so that the CPM network
contains no directed cycles (i.e., it is a directed acyclic graph). This is a
reasonable assumption, because if a project contains circular dependencies
among its activities then it can never be completed. Second, all project
durations are positive (specifically, nonzero). This is also a reasonable
assumption for real-world projects.
Define an {\it activity chain\/} to be a sequence $(a_1,a_2,\ldots,a_r)$ of
activities such that $a_i$~is an immediate prerequisite of~$a_{i+1}$ for all
$1\le in$, so writing $n$ as the single-term sum~$n$ is
not optimal, because writing it as $2+(n-2)$ produces a strictly larger
product. Suppose $n$ is written as a sum $c_1+c_2+\cdots+c_k$ of positive
integers, with $k\ge2$. If any term~$c_i$ is greater than~4, then $c_i$ can be
replaced by a sum of smaller positive integers whose product is greater
than~$c_i$ [e.g., $2+(c_i-2)$], so such a sum cannot be optimal. If any
term~$c_i$ is~1, then that term can be removed and another term increased by~1,
which will strictly increase the product, so a sum containing the term~1 cannot
be optimal either. If the sum contains three terms that are~2, then those terms
can be replaced by $3+3$, which will strictly increase the product (because
$3\times3>2\times2\times2$), so a sum containing three or more 2's also cannot
be optimal. Lastly, if any term~$c_i$ is~4, then that term can be replaced by
$2+2$ without changing the product. Therefore, there is an optimal sum
consisting solely of 2's~and~3's, with no more than two~2's. Consequently, for
$n\ge5$, an optimal sum is
$$\vbox{\offinterlineskip
\ialign{$#\hfil$&\quad#\hfil\cr
\underbrace{\vphantom(3+\cdots+3}_{m\rm\ terms},&if\/ $n=3m$;\cr
\noalign{\medskip}
2+2+\underbrace{\vphantom(3+\cdots+3}_{m-1\rm\ terms},&if\/ $n=3m+1$;\cr
\noalign{\medskip}
2+\underbrace{\vphantom(3+\cdots+3}_{m\rm\ terms},&if\/ $n=3m+2$.\cr
}}\eqno\hbox{\subqed}$$
\noindent Thus the number of critical paths in a project with $n$~activities is
bounded by the expression in this theorem. Moreover, this bound can be
achieved as follows.
\smallskip
\item{$\bullet$} For $n=1$, any project with a single activity (necessarily
having no prerequisites) has one critical path.
\smallskip\filbreak
\item{$\bullet$} For $n=3m$, a project of the following form has $3^m$~critical
paths.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate\cr
Activity&prerequisites&Duration\cr
\noalign{\vskip2pt\hrule\vskip2pt}
$a_1$&---&1\cr
$a_2$&---&1\cr
$a_3$&---&1\cr
\noalign{\smallskip}
$a_4$&$a_1$,~$a_2$,~$a_3$&1\cr
$a_5$&$a_1$,~$a_2$,~$a_3$&1\cr
$a_6$&$a_1$,~$a_2$,~$a_3$&1\cr
\noalign{\smallskip}
$a_7$&$a_4$,~$a_5$,~$a_6$&1\cr
$a_8$&$a_4$,~$a_5$,~$a_6$&1\cr
$a_9$&$a_4$,~$a_5$,~$a_6$&1\cr
\noalign{\smallskip}
$\vdots$&$\vdots$&$\vdots$\cr
\noalign{\smallskip}
$a_{3m-2}$&$a_{3m-5}$,~$a_{3m-4}$,~$a_{3m-3}$&1\cr
$a_{3m-1}$&$a_{3m-5}$,~$a_{3m-4}$,~$a_{3m-3}$&1\cr
$a_{3m}$&$a_{3m-5}$,~$a_{3m-4}$,~$a_{3m-3}$&1\cr
}}$$
The CPM network of a project of this form is shown below.
$$\fig{pset05-solns-cpm-1.mps}$$
All activities have duration~1, and therefore, as a consequence of the
structure of the project, every activity is critical. Hence any path from the
beginning of the project to the end is a critical path. There are
$m$~``layers'' in this CPM network: these are the sets $A_1=\{a_1,a_2,a_3\}$,
$A_2=\{a_4,a_5,a_6\}$, \dots, $A_m=\{a_{3m-2},a_{3m-1},a_{3m}\}$. Each of these
layers contains three activities, so there are $3^m$~critical paths.
\smallskip\filbreak
\item{$\bullet$} For $n=3m+1\ge4$, a project of the following form has
$4\cdot3^{m-1}$ critical paths.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate\cr
Activity&prerequisites&Duration\cr
\noalign{\vskip2pt\hrule\vskip2pt}
$a_1$&---&1\cr
$a_2$&---&1\cr
\noalign{\smallskip}
$a_3$&$a_1$,~$a_2$&1\cr
$a_4$&$a_1$,~$a_2$&1\cr
\noalign{\smallskip}
$a_5$&$a_3$,~$a_4$&1\cr
$a_6$&$a_3$,~$a_4$&1\cr
$a_7$&$a_3$,~$a_4$&1\cr
\noalign{\smallskip}
$a_8$&$a_5$,~$a_6$,~$a_7$&1\cr
$a_9$&$a_5$,~$a_6$,~$a_7$&1\cr
$a_{10}$&$a_5$,~$a_6$,~$a_7$&1\cr
\noalign{\smallskip}
$a_{11}$&$a_8$,~$a_9$,~$a_{10}$&1\cr
$a_{12}$&$a_8$,~$a_9$,~$a_{10}$&1\cr
$a_{13}$&$a_8$,~$a_9$,~$a_{10}$&1\cr
\noalign{\smallskip}
$\vdots$&$\vdots$&$\vdots$\cr
\noalign{\smallskip}
$a_{3m-1}$&$a_{3m-4}$,~$a_{3m-3}$,~$a_{3m-2}$&1\cr
$a_{3m}$&$a_{3m-4}$,~$a_{3m-3}$,~$a_{3m-2}$&1\cr
$a_{3m+1}$&$a_{3m-4}$,~$a_{3m-3}$,~$a_{3m-2}$&1\cr
}}$$
The CPM network of a project of this form is shown below.
$$\hss\fig{pset05-solns-cpm-2.mps}\hss$$
Again, every activity is critical, so any path from the beginning of the
project to the end is a critical path. There are $m+1$~``layers'' in this CPM
network; the first two layers contain two activities each, and the remaining
$m-1$~layers contain three activities each, so there are
$4\cdot3^{m-1}$~critical paths.
\smallskip\filbreak
\item{$\bullet$} For $n=3m+2$, a project of the following form has
$2\cdot3^m$~critical paths.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
&Immediate\cr
Activity&prerequisites&Duration\cr
\noalign{\vskip2pt\hrule\vskip2pt}
$a_1$&---&1\cr
$a_2$&---&1\cr
\noalign{\smallskip}
$a_3$&$a_1$,~$a_2$&1\cr
$a_4$&$a_1$,~$a_2$&1\cr
$a_5$&$a_1$,~$a_2$&1\cr
\noalign{\smallskip}
$a_6$&$a_3$,~$a_4$,~$a_5$&1\cr
$a_7$&$a_3$,~$a_4$,~$a_5$&1\cr
$a_8$&$a_3$,~$a_4$,~$a_5$&1\cr
\noalign{\smallskip}
$a_9$&$a_6$,~$a_7$,~$a_8$&1\cr
$a_{10}$&$a_6$,~$a_7$,~$a_8$&1\cr
$a_{11}$&$a_6$,~$a_7$,~$a_8$&1\cr
\noalign{\smallskip}
$\vdots$&$\vdots$&$\vdots$\cr
\noalign{\smallskip}
$a_{3m}$&$a_{3m-3}$,~$a_{3m-2}$,~$a_{3m-1}$&1\cr
$a_{3m+1}$&$a_{3m-3}$,~$a_{3m-2}$,~$a_{3m-1}$&1\cr
$a_{3m+2}$&$a_{3m-3}$,~$a_{3m-2}$,~$a_{3m-1}$&1\cr
}}$$
The CPM network of a project of this form is shown below.
$$\hss\fig{pset05-solns-cpm-3.mps}\hss$$
Again, every activity is critical, so any path from the beginning of the
project to the end is a critical path. There are $m+1$~``layers'' in this CPM
network; the first layer contains two activities, and the remaining $m$~layers
contain three activities each, so there are $2\cdot3^m$~critical paths. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Consider a directed graph~$G=(V,E)$ with nonnegative edge weights
$c_{ij}\ge0$ and specified nodes $s,t\in V$. For each node $i\in V$, let
$\pi_i$ be the distance of a shortest (directed) path from $i$ to~$t$. (Assume
that every node~$i$ has such a path to~$t$.) Show that $\pi$ is an optimal
feasible solution to the dual of the node-arc LP formulation for the shortest
path problem on~$G$ from $s$ to~$t$. Is the assumption $c_{ij}\ge0$ necessary?
\solution The dual of the node-arc LP formulation for the shortest path problem
on~$G$ from $s$ to~$t$ is as follows:
$$\eqalign{
{\rm maximize}\quad&\pi_s-\pi_t\cr
{\rm subject\ to}\quad&\pi_i-\pi_j\le c_{ij}
\quad\hbox{for all arcs $(i,j)\in E$}\cr
&\hbox{all variables unrestricted.}\cr
}$$
\noindent For each node $i\in V$, let $\pi_i$ be the shortest distance from $i$
to~$t$. Then for each arc $(i,j)\in E$, the constraint $\pi_i\le\pi_j+c_{ij}$
is satisfied, because the shortest distance from $i$ to~$t$ cannot be greater
than the shortest distance from $j$ to~$t$ plus the length of the arc joining
$i$~and~$j$ (by the triangle inequality). In more detail, we know that there
exists a directed path $(j=w_0,w_1,w_2,\ldots,w_k=t)$ from $j$ to~$t$ of total
distance $\sum_{p=0}^{k-1}c_{w_pw_{p+1}}=\pi_j$. So
$(i,j,w_1,w_2,\ldots,w_{k-1},t)$ is a directed walk from $i$ to~$t$ of total
distance $c_{ij}+\pi_j$. This implies that there is a directed path from $i$
to~$t$ of total distance no greater than $c_{ij}+\pi_j$, which means that the
{\it shortest\/} distance~$\pi_i$ from $i$ to~$t$ cannot be greater than this.
Therefore, all of the constraints are satisfied by this solution~$\pi$. Clearly
the domains place no restrictions on~$\pi$, so $\pi$ is a feasible solution.
Now consider any (directed) path $P=(s=v_0,v_1,v_2,\ldots,v_{l-1},v_l=t)$ from
$s$ to~$t$. Add the corresponding constraints:
$$\eqalign{
\pi_s-\pi_{v_1}\phantom{{}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{l-1}}-\pi_t}&\le c_{sv_1}\cr
\pi_{v_1}-\pi_{v_2}\phantom{{}+\pi_{v_3}+\ddots+\pi_{v_{l-1}}-\pi_t}&\le c_{v_1v_2}\cr
\pi_{v_2}-\pi_{v_3}\phantom{{}+\ddots+\pi_{v_{l-1}}-\pi_t}&\le c_{v_2v_3}\cr
\ddots\phantom{{}+\pi_{v_{l-1}}-\pi_t}&{\setbox0=\hbox{${}\le{}$}\hbox to\wd0{\hss$\vdots$\hss}}\cr
\pi_{v_{l-1}}-\pi_t&\le c_{v_{l-1}t}\cr
\noalign{\smallskip\hrule\smallskip}
\quad\pi_s\phantom{{}+\pi_{v_1}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{l-1}}}-\pi_t
&\le\sum_{p=0}^{l-1}c_{v_pv_{p+1}}.\quad\cr
}$$
The expression on the right-hand side of the resulting inequality is the length
of the path~$P$. Therefore, the objective value $\pi_s-\pi_t$ cannot be greater
than the length of~$P$. Since $P$ was an arbitrary path from $s$ to~$t$, the
value of $\pi_s-\pi_t$ cannot be greater than the length of {\it any\/} path
from $s$ to~$t$; in particular, it cannot be greater than the length of a
{\it shortest\/} path from $s$ to~$t$. So the solution~$\pi$ given in this
problem, in which $\pi_s$ is the length of a shortest path from $s$ to~$t$ and
$\pi_t$~is zero, must be optimal.
No part of the reasoning above used the assumption that $c_{ij}\ge0$, so this
assumption is not necessary. However, if there is a {\it cycle\/} with
negative total weight $\bigl[$say,
$(v_0,v_1,v_2,\ldots,\allowbreak v_{k-1},v_k=v_0)$ with
$\sum_{i=0}^{k-1}c_{v_iv_{i+1}}=C<0\bigr]$, then we can add the corresponding
constraints to get
$$\eqalign{
\pi_{v_0}-\pi_{v_1}\phantom{{}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&\le c_{iv_1}\cr
\pi_{v_1}-\pi_{v_2}\phantom{{}+\pi_{v_3}+\ddots+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&\le c_{v_1v_2}\cr
\pi_{v_2}-\pi_{v_3}\phantom{{}+\ddots+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&\le c_{v_2v_3}\cr
\ddots\phantom{{}+\pi_{v_{k-2}}-\pi_{v_{k-1}}}&{\setbox0=\hbox{${}\le{}$}\hbox to\wd0{\hss$\vdots$\hss}}\cr
\pi_{v_{k-2}}-\pi_{v_{k-1}}&\le c_{v_{k-2}v_{k-1}}\quad\cr
\quad{-}\pi_{v_0}\phantom{{}+\pi_{v_1}+\pi_{v_2}+\pi_{v_3}+\ddots+\pi_{v_{k-2}}}+\pi_{v_{k-1}}&\le c_{v_{k-1}v_0}\cr
\noalign{\smallskip\hrule\smallskip}
0&\le C,\cr
}$$
which is a contradiction, so the dual LP is infeasible. (Note that this is a
consequence of the fact that the primal is unbounded.)
Therefore the statement in the problem is still true and meaningful when the
assumption $c_{ij}\ge0$ is removed, as long as there are no cycles with
negative total weight. \qed
\filbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\figuregap{\vskip0pt plus12pt}
\problem Use Dijkstra's algorithm (or the primal-dual algorithm) to find a
shortest path from $s$ to~$t$ in the following undirected graph.
$$\fig{pset05-4.mps}$$
\solution We show the iterations of Dijkstra's algorithm in the figures below.
In each figure, the edge weights are circled, the vertex labels (denoting the
tentative distance from~$s$) are shown in red, the current set~$W$ of vertices
whose distances from~$s$ have definitely been determined is outlined in light
blue, and the vertex~$x$ outside~$W$ with the smallest vertex label is boxed
in green.
\figuregap
$$\fig{pset05-solns-dijkstra-1.mps}$$
\figuregap
$$\fig{pset05-solns-dijkstra-2.mps}$$
\figuregap
$$\fig{pset05-solns-dijkstra-3.mps}$$
(Note: At this stage $c$~and~$d$ tie for the minimum vertex label. Here we
chose $x=d$ arbitrarily, but it is equally valid to choose $x=c$.)
\goodbreak\figuregap
$$\fig{pset05-solns-dijkstra-4.mps}$$
\figuregap
$$\fig{pset05-solns-dijkstra-5.mps}$$
\figuregap
$$\fig{pset05-solns-dijkstra-6.mps}$$
\figuregap
$$\fig{pset05-solns-dijkstra-7.mps}$$
\figuregap
$$\fig{pset05-solns-dijkstra-8.mps}$$
\figuregap
$$\fig{pset05-solns-dijkstra-9.mps}$$
\figuregap
Now all vertices are included in~$W$, so the labels give the shortest distance
from~$s$ for each vertex. To find a shortest path from~$s$ to any vertex, we
identify the admissible edges, which are those edges whose weight equals the
difference of the vertex labels at their endpoints. The admissible edges are
shown as double green lines in the figure below.
$$\fig{pset05-solns-dijkstra-10.mps}$$
From this figure, we see that there are four shortest paths from $s$ to~$t$:
$s$--$a$--$c$--$e$--$t$, $s$--$a$--$c$--$f$--$t$, $s$--$b$--$c$--$e$--$t$,
and $s$--$b$--$c$--$f$--$t$. Each of these paths has total weight~34.
\goodbreak
Alternatively, we can use the primal-dual algorithm directly. The figures
below show the iterations of the primal-dual algorithm. In each figure, the
values of the dual solution~$\pi$ are written in green above each vertex, the
admissible edges~$J$ are drawn as double green lines, the set~$W$ of vertices
from which $t$ is reachable using only edges in~$J$ is outlined in light blue,
the values of the optimal solution~$\bar\pi$ to the dual of the restricted
primal are written in red below each vertex, the candidate edges~$K$ are drawn
with red hash marks, and the values of $c_{ij}-(\pi_i-\pi_j)$ are written in
blue below the candidate edges. The value of~$\theta_1$, which is the minimum
value of $c_{ij}-(\pi_i-\pi_j)$ over all candidate edges, is shown to the
lower right of the figure; this is the amount by which the dual values will be
increased for all vertices not in~$W$.
\figuregap
$$\fig{pset05-solns-primaldual-1.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-2.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-3.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-4.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-5.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-6.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-7.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-8.mps}$$
\figuregap
$$\fig{pset05-solns-primaldual-9.mps}$$
At this stage $t$~is reachable from~$s$ using only edges in~$J$, so the optimal
solution to the dual of the restricted primal is $\bar\pi=0$, which indicates
that the current dual solution is optimal. Therefore, the shortest distance
from $s$ to~$t$ is~34, and any path from $s$ to~$t$ using only admissible edges
is a shortest path. Again we see that there are four such paths:
$s$--$a$--$c$--$e$--$t$, $s$--$a$--$c$--$f$--$t$, $s$--$b$--$c$--$e$--$t$, and
$s$--$b$--$c$--$f$--$t$. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Give an example of a simple graph with at least two vertices such that
no two vertices have the same degree, or explain why this is impossible.
\solution This is impossible for a finite graph. Suppose that $G=(V,E)$ is a
simple finite graph with $\abs V=n\ge2$ such that no two vertices have the same
degree. The possible vertex degrees in~$G$ are 0,~1, 2, \dots, $n-1$, so, since
all $n$~vertices of~$G$ have different degrees, each one of these possible
degrees must occur exactly once. Therefore $G$ contains a vertex~$u$ of
degree~0 and also a vertex~$v$ of degree~$n-1$. These are not the same vertex,
because $n\ge2$ (so $n-1\not=0$). Now the vertex~$v$ must be adjacent to every
other vertex, including~$u$. On the other hand, the vertex~$u$ cannot be
adjacent to any other vertex, including~$v$. This is a contradiction, so such a
graph cannot exist.
However, it {\it is\/} possible if we consider graphs with infinitely many
vertices. For example, here is a graph on the vertex set $\N=\{0,1,2,\ldots\}$
in which each vertex~$n$ has degree~$n$:
$$\fig{pset05-solns-tree.mps}$$
Ignoring the isolated vertex~0, this graph is a rooted tree on the vertex
set~$\N$ in which 1~is the root and has exactly one child, and every vertex~$n$
other than~1 has exactly $n-1$ children.
\goodbreak
\def\phiround#1{[\![#1]\!]}
Here is another construction of a graph on the vertex set~$\N$ in which each
vertex~$n$ has degree~$n$; this construction has a very close connection to the
golden ratio. Let $\phi=(\sqrt5-1)/2=0.618\ldots$ and
$\Phi=(\sqrt5+1)/2=1.618\ldots\,$. Note that $\phi$~and~$\Phi$ are irrational,
and they satisfy the equations $\Phi=\phi+1$ and $\phi=1/\Phi$. For
$0\le x\in\R$, define
$$\phiround x=\cases{
\lfloor x\rfloor,&if $x-\lfloor x\rfloor<1-\phi$;\cr
\lceil x\rceil,&if $x-\lfloor x\rfloor>1-\phi$.\cr
}$$
In other words, $\phiround{x}$~rounds $x$ down if the fractional part of~$x$
is less than $1-\phi$ and up if the fractional part is greater than $1-\phi$.
For our purposes, we need not define what happens if the fractional part is
equal to $1-\phi$, because we are going to be applying the
function~$\phiround{{}\cdot{}}$ only to expressions of the form
$\phi n$~and~$\Phi n$ for $n\in\N$. For all $n\in\N$ we have
$\phi n-\lfloor\phi n\rfloor\not=1-\phi$, for if
$\phi n-\lfloor\phi n\rfloor=1-\phi$ then
$\lfloor\phi n\rfloor=\phi n+\phi-1=\phi(n+1)-1$, and hence $\phi(n+1)\in\Z$,
which cannot be true because $\phi\notin\Q$. Likewise, for all $n\in\N$ we have
$\Phi n-\lfloor\Phi n\rfloor\not=1-\phi$, for if
$\Phi n-\lfloor\Phi n\rfloor=1-\phi$ then
$\lfloor\Phi n\rfloor=\Phi n+\phi-1=\Phi n+\Phi-2=\Phi(n+1)-2$, and hence
$\Phi(n+1)\in\Z$, which cannot be true because $\Phi\notin\Q$. Therefore,
$\phiround{\phi n}$~and~$\phiround{\Phi n}$ are well defined for all $n\in\N$.
Next we see that for $m,n\in\N$, $m\ge\phiround{\phi n}$ if and only~if
$n\le\phiround{\Phi m}$. Note that $\phiround x=k$ if and only~if
$k-\phi