%  Problem set 6: solutions
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\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~6: solutions}

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

\problem Suppose a simple undirected graph has more than one minimum spanning
tree. Can Prim's algorithm (or Kruskal's algorithm) be used to find all of
them? Explain why or why not, and give an example.

\solution Yes, Prim's algorithm (or Kruskal's algorithm) can be used to find
all minimum spanning trees. Of course, each of these algorithms only produces a
single minimum spanning tree when it is run, so what we really mean is that
every minimum spanning tree is a possible result of both of these algorithms;
by making the appropriate choices during the algorithm, any particular minimum
spanning tree can be found.

We begin with a lemma whose proof is essentially the same as the proof of
Theorem~12.1 in Papadimitriou and Steiglitz.

\medskip

\proclaim Lemma. Let $G=(V,E)$ be a connected graph with an edge
weight~$d(u,v)$ for each edge $\{u,v\}\in E$. Let $(V,T)$ be a minimum spanning
tree of\/~$G$, and let $(V,F)$ be a spanning forest such that $F\subsetneq T$.
Let $U\subsetneq V$ be the vertex set of a connected component of\/~$(V,F)$,
and let $\partial U\subseteq E$ be the set of edges of\/~$G$ having exactly one
endpoint in~$U$. (The set~$\partial U$ is called the {\rm boundary} of\/~$U$.)
Then among the edges in~$\partial U$ having minimum weight, there is one that
is in~$T$.

\noindent{\bf Proof.}\enspace Suppose for the sake of contradiction that the
set of minimum-weight edges in~$\partial U$ contains no edges of~$T$. Let
$\{u,v\}\in\partial U$ be a minimum-weight edge. Add $\{u,v\}$ to~$T$; this
creates a (unique) cycle. Because this cycle contains at least one vertex
in~$U$ and at least one vertex not in~$U$ (namely, $u$~and~$v$), it must
contain another edge $\{u',v'\}\in\partial U$ different from $\{u,v\}$, and
$\{u',v'\}$ must be in~$T$. By assumption, $d(u,v)<d(u',v')$, so if we remove
the edge $\{u',v'\}$ we obtain a new spanning tree~$(V,T')$, with
$T'=T\cup\bigl\{\{u,v\}\bigr\}\setminus\bigl\{\{u',v'\}\bigr\}$, with strictly
smaller weight than $(V,T)$. But this contradicts the fact that $(V,T)$ is a
minimum spanning tree. \subqed

\medbreak

Each iteration of Prim's algorithm (or Kruskal's algorithm) consists of adding
an edge to a spanning forest, initially having no edges, until the spanning
forest becomes a spanning tree. Therefore, the spanning forest that results
after $k$~iterations of either of these algorithms has exactly $k$~edges.

\proclaim Claim. Fix a minimum spanning tree~$(V,T)$ of~$G$. For every
$0\le k\le n-1$, after $k$~iterations of Prim's algorithm (or Kruskal's
algorithm), it is possible for the resulting spanning forest~$(V,F)$ to satisfy
$F\subseteq T$.

\noindent{\bf Proof.}\enspace By induction on~$k$. Clearly the statement is
true for $k=0$, because both Prim's algorithm and Kruskal's algorithm begin
with a spanning forest having no edges, so $F=\emptyset\subseteq T$. Suppose
$k\ge1$. By induction, it is possible, after $k-1$~iterations, for Prim's
algorithm (or Kruskal's algorithm) to produce a spanning forest~$(V,F')$ having
$F'\subseteq T$; since $k-1<n-1$, we know that $F'\not=T$. In the $k$th
iteration of Prim's algorithm, a minimum-weight edge~$e$ is selected out of the
set~$\partial U$ of edges having exactly one endpoint in~$U$, where $U$ is the
vertex set of the connected component of~$(V,F')$ containing a fixed
vertex~$v_1$ arbitrarily chosen at the beginning of the algorithm. In the $k$th
iteration of Kruskal's algorithm, a minimum-weight edge~$e=\{u,v\}$ is selected
out of the set of all edges whose endpoints are in different connected
components of~$(V,F')$; this edge is in the set~$\partial U$, where $U$ is the
vertex set of the connected component of~$(V,F')$ containing~$u$. In either
case, we see by the lemma above that among the edges in~$\partial U$ having
minimum weight, there is one that is in~$T$, so we may select~$e$ to be an
edge in~$T$, and then $F:=F'\cup\{e\}\subseteq T$. \subqed

\medbreak

Therefore, taking $k=n-1$ in this claim, we see that it is possible for Prim's
algorithm (or Kruskal's algorithm) to produce the tree~$(V,T)$. As $(V,T)$ was
an arbitrary minimum spanning tree, this shows that it is possible for both of
these algorithms to find any minimum spanning tree.

\goodbreak

As an example, consider the graph shown on the left below. It has two minimum
spanning trees, shown separately.
$$\fig{pset06-solns-sptree-1.mps}\qquad\fig{pset06-solns-sptree-2.mps}
	\qquad\fig{pset06-solns-sptree-3.mps}$$
If $v_1$ is chosen to be the vertex~$a$ at the beginning of Prim's algorithm,
then both Prim's algorithm and Kruskal's algorithm start by selecting the edge
$\{a,c\}$. In the next iteration, both $\{a,d\}$ and $\{c,d\}$ are candidates
to be selected. Selecting $\{a,d\}$ leads to the minimum spanning tree shown
in the center above, while selecting $\{c,d\}$ leads to the one shown on the
right. \qed

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

\problem Explain how a minimum spanning tree algorithm can easily be used to
find a {\it maximum\/} spanning tree in a graph. Then explain why, if you want
to find the {\it longest\/} path between two vertices in a graph, using this
same technique with Dijkstra's algorithm does not work.

\solution A maximum spanning tree can be found by negating all of the edge
weights and then applying a minimum spanning tree algorithm to the resulting
graph.

Alternatively, if we would like to work only with nonnegative edge weights, we
can find the largest edge weight~$M$, replace every edge weight~$w$ with $M-w$,
and then apply a minimum spanning tree algorithm. This is equivalent to
negating all of the edge weights and then increasing each edge weight by~$M$.
This approach works because every spanning tree on a graph with $n$~vertices
has exactly $n-1$~edges, so the total weight of every spanning tree will be
increased by exactly $(n-1)M$.

The simple reason that negating edge weights does not work to find a longest
path with Dijkstra's algorithm is that Dijkstra's algorithm requires all
weights to be nonnegative.

The $M-w$ trick doesn't work with Dijkstra's algorithm either, because
different paths between a given pair of vertices may consist of different
numbers of edges. Negating each edge weight and then adding~$M$ to each weight
will therefore add different multiples of~$M$ to the total weights of these
paths, and this will not necessarily preserve the longest or shortest path.
\qed

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

\problem Find a maximum $s$--$t$ flow and a minimum $s$--$t$ cut in the
following flow network.
$$\fig{pset06-3.mps}$$

\def\figuregap{\goodbreak\vskip 0pt plus60pt minus16pt}
\def\xout#1{\setbox0=\hbox{#1}\hbox to\wd0{\hss$\backslash$\hss}\llap{\box0}}

\solution The iterations of the Ford--Fulkerson algorithm are shown below. In
these figures, the capacities of the arcs are shown circled in gray, the node
labels are in green, and nonzero flows along arcs are in light blue. The node
labels are given in the form $({\it from}[i],\hbox{\it how-much}[i])$. Arcs
with zero flow are drawn as straight black arrows, saturated arcs are drawn as
double red arrows, and unsaturated arcs with nonzero flow are drawn as wavy
light blue arrows. Below the figure is the {\it LIST\/} of vertices built up as
the Ford--Fulkerson algorithm progresses through the network. We treat the
{\it LIST\/} as a queue here: nodes are added to the right-hand side when they
are labeled, and they are removed from the left-hand side (indicated by
crossing them out) when they are scanned.

\figuregap

$$\displaylines{
	\fig{pset06-solns-ff-1.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$c$},
		\xout{$d$}, \xout{$g$}; $e$; $f$; $t$.}\cr
}$$
The node~$t$ received a label, so we have found an augmenting path. The value
of the label $\hbox{\it how-much}[t]$ is~3, so we can augment the flow by~3
along this path. To identify the path, we follow the {\it from\/} labels
backward from~$t$: ${\it from}[t]=g$, ${\it from}[g]=a$, and ${\it from}[a]=s$,
so our augmenting path is $s$--$a$--$g$--$t$. All of the {\it from\/} labels
along this path were ``positive'' (they did not have a leading minus sign), so
the flow along every arc in this path will be increased by~3. We adjust the
flow and repeat the labeling process from the beginning.

\figuregap

$$\displaylines{
	\fig{pset06-solns-ff-2.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$c$},
		\xout{$d$}; \xout{$e$}; \xout{$f$}; \xout{$g$}; $h$; $t$.}\cr
}$$
Following the {\it from\/} labels backward from~$t$, we find the augmenting
path $s$--$a$--$d$--$g$--$t$. We augment the flow along every arc in this path
by $\hbox{\it how-much}[t]=1$ and repeat the labeling process from the
beginning.

\vfill\eject

$$\displaylines{
	\fig{pset06-solns-ff-3.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$c$},
		\xout{$d$}; \xout{$e$}; \xout{$f$}; \xout{$g$}; \xout{$h$}; $t$.}\cr
}$$
The augmenting path here is $s$--$b$--$e$--$h$--$t$; we augment the flow along
this path by~1.

\figuregap

$$\displaylines{
	\fig{pset06-solns-ff-4.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$c$},
		\xout{$d$}; \xout{$e$}, \xout{$f$}; \xout{$g$}; \xout{$h$}; $t$.}\cr
}$$
The augmenting path here is $s$--$a$--$c$--$e$--$h$--$t$; we augment the flow
along this path by~2.

\figuregap

$$\displaylines{
	\fig{pset06-solns-ff-5.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$d$};
		\xout{$c$}; \xout{$g$}; \xout{$e$}, \xout{$f$}; \xout{$h$}; $t$.}\cr
}$$
The augmenting path here is $s$--$b$--$c$--$e$--$h$--$t$; we augment the flow
along this path by~3.

\figuregap

$$\displaylines{
	\fig{pset06-solns-ff-6.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$d$};
		\xout{$c$}, \xout{$g$}; \xout{$e$}, \xout{$f$}; \xout{$h$}; $t$.}\cr
}$$
The augmenting path here is $s$--$a$--$d$--$c$--$e$--$h$--$t$; we augment the
flow along this path by~2.

\figuregap

$$\displaylines{
	\fig{pset06-solns-ff-7.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$d$};
		\xout{$c$}, \xout{$g$}; \xout{$f$}; \xout{$h$}; $e$, $t$.}\cr
}$$
The augmenting path here is $s$--$a$--$d$--$c$--$f$--$h$--$t$; we augment the
flow along this path by~3.

\figuregap

$$\displaylines{
	\fig{pset06-solns-ff-8.mps}\cr
	\hbox{{\it LIST\/}: \xout{$s$}; \xout{$a$}, \xout{$b$}; \xout{$d$};
		\xout{$c$}, \xout{$g$}.}\cr
}$$
Now $t$ did not get a label, so there is no augmenting path, so this flow is
optimal. The value of this flow is~15. A minimum $s$--$t$ cut is determined by
partitioning the nodes according to whether they received a label in this
last iteration:
$$W=\{s,a,b,c,d,g\},\qquad\bar W=\{e,f,h,t\}.$$
$$\fig{pset06-solns-ff-9.mps}$$
The capacity of this cut is the sum of the capacities~$b_{ij}$ of the arcs that
point from a node~$i$ in~$W$ to a node~$j$ in~$\bar W$:
$b_{be}+b_{ce}+b_{cf}+b_{gt}=1+7+3+4=15$, which equals the value of the maximum
$s$--$t$ flow, in accordance with the max-flow min-cut theorem. Note also that
in the maximum flow all arcs that go forward across the cut (from $W$
to~$\bar W$) are saturated while all arcs that go backward across the cut (from
$\bar W$ to~$W$) have zero flow. \qed

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

\problem Carefully describe an algorithm for the following problem: Given a
simple undirected graph $G=(V,E)$, determine whether $G$ is bipartite, and if
so give a bipartition (i.e., a partition of the vertex set~$V$ into two sets
$U$~and~$W$ such that every edge has one endpoint in~$U$ and one endpoint
in~$W$). Illustrate the operation of your algorithm on two examples, one
bipartite graph and one non-bipartite graph. Prove that your algorithm is
correct in general.

\newdimen\d
\def\marginalfig#1{\strut\vadjust{% this is a pretty bad kludge
	\setbox0=\hbox{\fig{#1}}%
	\d=\ht0 \advance\d by-\baselineskip
	\smash{\hbox to\hsize{\hfill\vtop{\hbox{\lower\d\box0}}}\hss}}%
	\ignorespaces}

\solution Here are the steps of an algorithm for this problem.

\medskip

\item{1.} Begin with all vertices uncolored. Set ${\it LIST}:=\emptyset$.

\smallskip

\item{2.} Choose an uncolored vertex~$v$. Color $v$ red. Add $v$ to $\it LIST$.

\smallskip

\item{3.} Choose a vertex~$w$ in~$\it LIST$, and remove~$w$ from $\it LIST$.

\smallskip

\item{4.} If any neighbor of~$w$ has the same color as~$w$, stop: the graph is
not bipartite.

\smallskip

\item{5.} For each uncolored neighbor~$x$ of~$w$: color $x$ blue if $w$~is red,
or color $x$ red if $w$~is blue; and then add~$x$ to~$\it LIST$.

\smallskip

\item{6.} If $\it LIST$ is nonempty, go back to step~3.

\smallskip

\item{7.} If there still exist uncolored vertices, go back to step~2.

\smallskip

\item{8.} We are done. The graph is bipartite. Let $U$ be the set of red
vertices, and let $W$ be the set of blue vertices; then $(U,W)$ is a
bipartition.

\medbreak

\noindent For example, consider the following graph, which is bipartite:
$$\fig{pset06-solns-bipartite-1.mps}$$

\goodbreak

{\advance\rightskip by2.25in

\item{1.} We begin with all vertices uncolored and an empty $\it LIST$.

\smallskip

\item{2.} \marginalfig{pset06-solns-bipartite-2.mps} We choose an uncolored
vertex, say~$a$, and color it red. We add $a$ to $\it LIST$. Now
${\it LIST}=\{a\}$.

\smallskip

\item{3.} We choose a vertex in $\it LIST$; it must be~$a$, as that is the only
element of $\it LIST$. We remove it from $\it LIST$, so now $\it LIST$ is empty
again.

\smallskip

\item{4.} No neighbor of~$a$ has the same color as~$a$, so we skip step~4.

\smallskip

\item{5.} \marginalfig{pset06-solns-bipartite-3.mps} We color each uncolored
neighbor of~$a$ blue and add these vertices to $\it LIST$. These vertices are
$b$~and~$c$. Now ${\it LIST}=\{b,c\}$.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, say~$b$, and remove it from
$\it LIST$. Now ${\it LIST}=\{c\}$.

\smallskip

\item{4.} No neighbor of~$b$ has the same color as~$b$, so we skip step~4.

\smallskip

\item{5.} \marginalfig{pset06-solns-bipartite-4.mps} We color each uncolored
neighbor of~$b$ red and add these vertices to $\it LIST$. This is only the
vertex~$d$. Now ${\it LIST}=\{c,d\}$.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, say~$c$, and remove it from
$\it LIST$. Now ${\it LIST}=\{d\}$.

\smallskip

\item{4.} No neighbor of~$c$ has the same color as~$c$, so we skip step~4.

\smallskip

\item{5.} No neighbor of~$c$ is uncolored, so there is nothing to do in step~5.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, which must be~$d$, and remove it
from $\it LIST$. Now $\it LIST$ is empty.

\smallskip

\item{4.} No neighbor of~$d$ has the same color as~$d$, so we skip step~4.

\smallskip

\item{5.} No neighbor of~$d$ is uncolored, so there is nothing to do in step~5.

\smallskip

\item{6.} $\it LIST$ is empty, so we skip step~6.

\smallskip

\item{7.} There still exist uncolored vertices, so we go back to step~2.

\smallskip

\item{2.} \marginalfig{pset06-solns-bipartite-5.mps} We choose an uncolored
vertex, say~$e$, and color it red. We add $e$ to $\it LIST$. Now
${\it LIST}=\{e\}$.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, which must be~$e$, and remove it
from $\it LIST$. Now $\it LIST$ is empty.

\smallskip

\item{4.} No neighbor of~$e$ has the same color as~$e$, so we skip step~4.

\smallskip

\item{5.} \marginalfig{pset06-solns-bipartite-6.mps} We color each uncolored
neighbor of~$e$ blue and add these vertices to $\it LIST$. This is only the
vertex~$g$. Now ${\it LIST}=\{g\}$.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, which must be~$g$, and remove it
from $\it LIST$. Now $\it LIST$ is empty.

\smallskip

\item{4.} No neighbor of~$g$ has the same color as~$g$, so we skip step~4.

\smallskip

\item{5.} \marginalfig{pset06-solns-bipartite-7.mps} We color each uncolored
neighbor of~$g$ red and add these vertices to $\it LIST$. These vertices are
$f$~and~$h$. Now ${\it LIST}=\{f,h\}$.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, say~$f$, and remove it from
$\it LIST$. Now ${\it LIST}=\{h\}$.

\smallskip

\item{4.} No neighbor of~$f$ has the same color as~$f$, so we skip step~4.

\smallskip

\item{5.} No neighbor of~$f$ is uncolored, so there is nothing to do in step~5.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, which must be~$h$, and remove it
from $\it LIST$. Now $\it LIST$ is empty.

\smallskip

\item{4.} No neighbor of~$h$ has the same color as~$h$, so we skip step~4.

\smallskip

\item{5.} No neighbor of~$h$ is uncolored, so there is nothing to do in step~5.

\smallskip

\item{6.} $\it LIST$ is empty, so we skip step~6.

\smallskip

\item{7.} All vertices have been colored, so we skip step~7.

\smallskip

\item{8.} The graph is bipartite, and $U=\{a,d,e,f,h\}$, $W=\{b,c,g\}$ is a
bipartition.\quad\checkmark

\medbreak}

\noindent For another example, consider the following graph, which is not
bipartite:
$$\fig{pset06-solns-nonbipartite-1.mps}$$

{\advance\rightskip by1.25in

\item{1.} We begin with all vertices uncolored and an empty $\it LIST$.

\smallskip

\item{2.} \marginalfig{pset06-solns-nonbipartite-2.mps} We choose an uncolored
vertex, say~$a$, and color it red. We add $a$ to $\it LIST$. Now
${\it LIST}=\{a\}$.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, which must be~$a$, and remove it
from $\it LIST$. Now $\it LIST$ is empty.

\smallskip

\item{4.} No neighbor of~$a$ has the same color as~$a$, so we skip step~4.

\bigskip

\item{5.} \marginalfig{pset06-solns-nonbipartite-3.mps} We color each uncolored
neighbor of~$a$ blue and add these vertices to $\it LIST$. These vertices are
$b$~and~$e$. Now ${\it LIST}=\{b,e\}$.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, say~$b$, and remove it from
$\it LIST$. Now ${\it LIST}=\{e\}$.

\smallskip

\item{4.} No neighbor of~$b$ has the same color as~$b$, so we skip step~4.

\vfill\eject

\item{5.} \marginalfig{pset06-solns-nonbipartite-4.mps} We color each uncolored
neighbor of~$b$ red and add these vertices to $\it LIST$. This is only the
vertex~$c$. Now ${\it LIST}=\{c,e\}$.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, say~$c$, and remove it from
$\it LIST$. Now ${\it LIST}=\{e\}$.

\smallskip

\item{4.} No neighbor of~$c$ has the same color as~$c$, so we skip step~4.

\smallskip

\item{5.} \marginalfig{pset06-solns-nonbipartite-5.mps} We color each uncolored
neighbor of~$c$ blue and add these vertices to $\it LIST$. This is only the
vertex~$d$. Now ${\it LIST}=\{d,e\}$.

\smallskip

\item{6.} $\it LIST$ is nonempty, so we go back to step~3.

\smallskip

\item{3.} We choose a vertex in $\it LIST$, say~$d$, and remove it from
$\it LIST$. Now ${\it LIST}=\{e\}$.

\smallskip

\item{4.} We notice that one of the neighbors of~$d$, namely~$e$, has the same
color as~$d$. Therefore we report that the graph is not
bipartite.\quad\checkmark

\medbreak}

\noindent In order to prove the correctness of this algorithm, we first prove
Proposition~1 from Section~A.2 of Papadimitriou and Steiglitz, and in order to
do that we first prove a lemma.

\proclaim Lemma. Every closed odd walk contains an odd cycle.

\noindent{\bf Proof.}\enspace By induction on the length~$l$ of the walk.

The base case for general graphs is $l=1$. In this case, the walk consists of a
loop (an edge joining a vertex to itself). The loop itself is an odd cycle.
Note that this cannot occur in a {\it simple\/} graph, which has no loops.

The base case for simple graphs is $l=3$. In this case, the walk must be a
cycle of length~3 (because the graph does not contain loops).

For the inductive step, suppose $l\ge5$ (or $l\ge3$ for general graphs). If no
vertex is repeated in the walk (except the first and last vertex, which are the
same), then the walk itself is an odd cycle. Otherwise, some vertex~$v$ is
repeated, and we can break the walk into two $v$--$v$ walks. Since $l$ is odd,
the length of one of these $v$--$v$ walks must be odd, and by induction it
contains an odd cycle. \subqed

\proclaim Proposition~1. A graph is bipartite iff it has no circuit of odd
length.

\noindent{\bf Proof.}\enspace($\Longrightarrow$)\enspace Suppose $G$ is
bipartite, and let $(U,W)$ be a bipartition of the vertex set. Then every edge
has one endpoint in~$U$ and one endpoint in~$W$, so the vertices of a walk
alternate between vertices in~$U$ and vertices in~$W$. Thus a walk that begins
and ends at the same vertex (in particular, a cycle) must have even length. So
$G$ has no cycles of odd length.

($\Longleftarrow$)\enspace Suppose $G=(V,E)$ has no cycles of odd length. We
shall construct a bipartition~$(U,W)$ of~$G$. Without loss of generality, we
may assume that $G$~is connected; otherwise, we can construct a
bipartition~$(U_i,W_i)$ of each connected component separately and then take
$U=\bigcup U_i$ and $W=\bigcup W_i$.

Fix an arbitrary vertex~$u\in V$, and for all $v\in V$ define $d(v)$ to be the
shortest length of a path from $u$ to~$v$. [Since $G$ is connected by
assumption, $d(v)$~is well defined for all $v\in V$.] Let
$U=\{\,v\in V:\hbox{d(v) is even}\,\}$ and
$W=\{\,v\in V:\hbox{d(v) is odd}\,\}$. If there is an edge between two vertices
$u_1,u_2\in U$, then the shortest path from $u$ to~$u_1$, plus the edge from
$u_1$ to~$u_2$, plus the shortest path from $u_2$ to~$u$ yields a closed odd
walk in~$U$. By the preceding lemma, such a walk contains an odd cycle. But
this contradicts the hypothesis that $G$ contains no odd cycles, so there can
be no such edge between vertices in~$U$. Likewise, there can be no edge between
vertices in~$W$. So $(U,W)$ is a bipartition. \subqed

\medbreak

\noindent Now we establish the correctness of the algorithm.

Suppose the algorithm reports that the graph is bipartite. This must happen in
step~8, which cannot happen until all vertices have been colored and processed
by step~4. If the resulting vertex coloring of the graph assigns the same color
to both endpoints of an edge, then this would have been noticed in step~4 when
processing the second endpoint; so this does not happen. Therefore every edge
has one red endpoint and one blue endpoint, so $(U,W)$ is a bipartition, and
the graph is indeed bipartite.

On the other hand, suppose the algorithm reports that the graph is not
bipartite. this occurs when it is noticed in step~4 that two adjacent vertices
$w$~and~$x$ have the same color. The vertices chosen as~$v$ in step~2 are the
first vertices in their connected components to be assigned a color. Every
other vertex is assigned red if it is an even distance from one of these $v$'s
or blue if it is an odd distance (where ``distance'' means ``the number of
edges in a shortest path''). If two adjacent vertices have the same color, then
there is a closed odd walk in the graph [as in the ($\Longleftarrow$) part of
the proof of Proposition~1], so the graph contains an odd cycle, so it is
indeed not bipartite. \qed

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

\problem Find a maximum matching in the following bipartite graph.
$$\fig{pset06-5.mps}$$

\solution One way to do this is to reduce the problem to that of finding a
maximum $s$--$t$ flow in the following network:
$$\fig{pset06-solns-matching-1.mps}$$

\goodbreak

\noindent The corresponding max-flow LP is shown below. In this LP, the
variable~$v$ denotes the value of the flow, and for each arc $(i,j)$ in the
network the variable~$f_{ij}$ denotes the flow along that arc. The first
14~constraints enforce flow balance at every node: the net outflow at every
node must be~0, except at node~$s$ where it is~$v$ and at node~$t$ where it
is~$-v$. The remaining 12~constraints enforce the capacities of the arcs
from~$s$ and the arcs to~$t$.

$$\eqalign{
	{\rm maximize}\quad&v\cr
	{\rm subject\ to}\quad&\vtop{%
	\halign{\hfil\strut$#$&\strut${}#$\hfil\cr
		f_{sa}+f_{sb}+f_{sc}+f_{sd}+f_{se}+f_{sf}&=v\cr
		f_{au}+f_{aw}-f_{sa}&=0\cr
		f_{bu}+f_{bv}+f_{bw}+f_{by}-f_{sb}&=0\cr
		f_{cx}+f_{cz}-f_{sc}&=0\cr
		f_{du}+f_{dv}+f_{dw}+f_{dy}-f_{sd}&=0\cr
		f_{ex}+f_{ez}-f_{se}&=0\cr
		f_{fx}+f_{fz}-f_{sf}&=0\cr
		f_{ut}-f_{au}-f_{bu}-f_{du}&=0\cr
		f_{vt}-f_{bv}-f_{dv}&=0\cr
		f_{wt}-f_{aw}-f_{bw}-f_{dw}&=0\cr
		f_{xt}-f_{cx}-f_{ex}-f_{fx}&=0\cr
		f_{yt}-f_{by}-f_{dy}&=0\cr
		f_{zt}-f_{cz}-f_{ez}-f_{fz}&=0\cr
		-f_{ut}-f_{vt}-f_{wt}-f_{xt}-f_{yt}-f_{zt}&=-v\cr
	}}\cr
	&\qquad\qquad\vtop{%
	\halign{\hfil\strut$#$&&\strut${}#$\hfil&\qquad\qquad\hfil\strut$#$\cr
		f_{sa}&\le1&f_{ut}&\le1\cr
		f_{sb}&\le1&f_{vt}&\le1\cr
		f_{sc}&\le1&f_{wt}&\le1\cr
		f_{sd}&\le1&f_{xt}&\le1\cr
		f_{se}&\le1&f_{yt}&\le1\cr
		f_{sf}&\le1&f_{zt}&\le1\cr
	}}\cr
	&\hbox{all variables nonnegative.}\cr
}$$

\goodbreak

\noindent An optimal solution to this LP is $v=5$,
$f_{aw}=f_{by}=f_{cx}=f_{dv}=f_{ez}=1$,
$f_{sa}=f_{sb}=f_{sc}=f_{sd}=f_{se}=f_{vt}=f_{wt}=f_{xt}=f_{yt}=f_{zt}=1$, and
all other variables~0. Therefore, a maximum matching in this graph is as
shown below.
$$\fig{pset06-solns-matching-2.mps}$$
(This maximum matching is not unique.) \qed

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

\problem A small trucking company has a fleet of five trucks, and on a certain
day has seven loads to deliver. In the following tables, the capacities of the
trucks and the sizes of the loads are both given in units of 1000~pounds.
$$\vtop{\offinterlineskip
\halign{&\quad\hfil\strut#\hfil\quad&\vrule#\cr
&&&&Daily\cr
Truck&&Capacity&&cost\cr
\omit&height2pt&\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt&\omit&height2pt\cr
1&&\phantom03&&\$200\cr
2&&\phantom06&&\$300\cr
3&&\phantom06&&\$400\cr
4&&\phantom08&&\$350\cr
5&&11&&\$500\cr}}\qquad\vtop{\offinterlineskip
\halign{&\quad\hfil\strut#\hfil\quad&\vrule#\cr
Load&&Weight\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
A&&1\cr
B&&2\cr
C&&3\cr
D&&4\cr
E&&4\cr
F&&5\cr
G&&8\cr}}$$
The daily cost for a truck must be paid if that truck is to be used to make any
deliveries. Because of their locations, loads A~and~D cannot be delivered by
the same truck, nor can loads B~and~E. Formulate an integer program to
determine which loads should be assigned to each truck in order to minimize the
total daily cost.

\solution For $i\in\{\rm A,B,C,D,E,F,G\}$ and $j\in\{1,2,3,4,5\}$, let
$x_{ij}\in\{0,1\}$ indicate whether load~$i$ is to be delivered by truck~$j$.
For $j\in\{1,2,3,4,5\}$, let $y_j\in\{0,1\}$ indicate whether the daily cost
is to be paid for truck~$j$.

Our objective is to minimize the total daily cost, which is
$200y_1+300y_2+400y_3+350y_4+500y_5$.

We have several sets of constraints. First, every load must be delivered by
exactly one truck, so
$$\sum_{j=1}^5x_{ij}=1\qquad\hbox{for all $i\in\{\rm A,B,C,D,E,F,G\}$}.$$
The truck capacities cannot be exceeded, so
$$x_{{\rm A}j}+2x_{{\rm B}j}+3x_{{\rm C}j}+4x_{{\rm D}j}+4x_{{\rm E}j}+5x_{{\rm F}j}+8x_{{\rm G}j}\le W_j
	\qquad\hbox{for all $j\in\{1,2,3,4,5\}$},$$
where $W_j$ is the capacity of truck~$j$. The daily cost must be paid to use
each truck, so
$$x_{ij}\le y_j\qquad\hbox{for all $i\in\{\rm A,B,C,D,E,F,G\}$ and all $j\in\{1,2,3,4,5\}$},$$
because if $y_j=0$ then $x_{ij}$~must also be~0. Finally, loads A~and~D cannot
be delivered by the same truck, nor can loads B~and~E, so
$$\eqalign{
	x_{{\rm A}j}+x_{{\rm D}j}\le1&\qquad\hbox{for all $j\in\{1,2,3,4,5\}$},\cr
	x_{{\rm B}j}+x_{{\rm E}j}\le1&\qquad\hbox{for all $j\in\{1,2,3,4,5\}$}.\cr
}$$

\filbreak

\noindent Therefore we have the following integer program.
$$\def\x#1{\phantom{x_{\rm G0}}\llap{$x_{\rm#1}$}}
\eqalign{
	{\rm minimize}\quad\phantom{x_{\rm G1}\le y_1,\quad x_{\rm G2}\le y_2,\quad x_{\rm G3}\le y_3,\quad x_{\rm G4}\le y_4,\quad x_{\rm G5}}
		\llap{$200y_1+300y_2+400y_3+350y_4+500y_5$}&\cr
	{\rm subject\ to}\quad\phantom{x_{\rm G1}\le y_1,\quad x_{\rm G2}\le y_2,\quad x_{\rm G3}\le y_3,\quad x_{\rm G4}\le y_4,\quad x_{\rm G5}}
		\llap{$x_{\rm A1}+x_{\rm A2}+x_{\rm A3}+x_{\rm A4}+x_{\rm A5}$}&=\phantom01\cr
	x_{\rm B1}+x_{\rm B2}+x_{\rm B3}+x_{\rm B4}+x_{\rm B5}&=\phantom01\cr
	x_{\rm C1}+x_{\rm C2}+x_{\rm C3}+x_{\rm C4}+x_{\rm C5}&=\phantom01\cr
	x_{\rm D1}+x_{\rm D2}+x_{\rm D3}+x_{\rm D4}+x_{\rm D5}&=\phantom01\cr
	x_{\rm E1}+x_{\rm E2}+x_{\rm E3}+x_{\rm E4}+x_{\rm E5}&=\phantom01\cr
	x_{\rm F1}+x_{\rm F2}+x_{\rm F3}+x_{\rm F4}+x_{\rm F5}&=\phantom01\cr
	x_{\rm G1}+x_{\rm G2}+x_{\rm G3}+x_{\rm G4}+x_{\rm G5}&=\phantom01\cr
	x_{\rm A1}+2x_{\rm B1}+3x_{\rm C1}+4x_{\rm D1}+4x_{\rm E1}+5x_{\rm F1}+8x_{\rm G1}&\le\phantom03\cr
	x_{\rm A2}+2x_{\rm B2}+3x_{\rm C2}+4x_{\rm D2}+4x_{\rm E2}+5x_{\rm F2}+8x_{\rm G2}&\le\phantom06\cr
	x_{\rm A3}+2x_{\rm B3}+3x_{\rm C3}+4x_{\rm D3}+4x_{\rm E3}+5x_{\rm F3}+8x_{\rm G3}&\le\phantom06\cr
	x_{\rm A4}+2x_{\rm B4}+3x_{\rm C4}+4x_{\rm D4}+4x_{\rm E4}+5x_{\rm F4}+8x_{\rm G4}&\le\phantom08\cr
	x_{\rm A5}+2x_{\rm B5}+3x_{\rm C5}+4x_{\rm D5}+4x_{\rm E5}+5x_{\rm F5}+8x_{\rm G5}&\le11\cr
	\x{A1}\le y_1,\quad\x{A2}\le y_2,\quad\x{A3}\le y_3,\quad\x{A4}\le y_4,\quad\x{A5}&\le y_5\cr
	\x{B1}\le y_1,\quad\x{B2}\le y_2,\quad\x{B3}\le y_3,\quad\x{B4}\le y_4,\quad\x{B5}&\le y_5\cr
	\x{C1}\le y_1,\quad\x{C2}\le y_2,\quad\x{C3}\le y_3,\quad\x{C4}\le y_4,\quad\x{C5}&\le y_5\cr
	\x{D1}\le y_1,\quad\x{D2}\le y_2,\quad\x{D3}\le y_3,\quad\x{D4}\le y_4,\quad\x{D5}&\le y_5\cr
	\x{E1}\le y_1,\quad\x{E2}\le y_2,\quad\x{E3}\le y_3,\quad\x{E4}\le y_4,\quad\x{E5}&\le y_5\cr
	\x{F1}\le y_1,\quad\x{F2}\le y_2,\quad\x{F3}\le y_3,\quad\x{F4}\le y_4,\quad\x{F5}&\le y_5\cr
	\x{G1}\le y_1,\quad\x{G2}\le y_2,\quad\x{G3}\le y_3,\quad\x{G4}\le y_4,\quad\x{G5}&\le y_5\cr
	x_{\rm A1}+x_{\rm D1}\le1,\qquad x_{\rm B1}+x_{\rm E1}&\le1\cr
	x_{\rm A2}+x_{\rm D2}\le1,\qquad x_{\rm B2}+x_{\rm E2}&\le1\cr
	x_{\rm A3}+x_{\rm D3}\le1,\qquad x_{\rm B3}+x_{\rm E3}&\le1\cr
	x_{\rm A4}+x_{\rm D4}\le1,\qquad x_{\rm B4}+x_{\rm E4}&\le1\cr
	x_{\rm A5}+x_{\rm D5}\le1,\qquad x_{\rm B5}+x_{\rm E5}&\le1\cr
	&\phantom{{}=00}\llap{$x_{ij}\in\{0,1\}$\quad for all $i\in\{\rm A,B,C,D,E,F,G\}$ and all $j\in\{1,2,3,4,5\}$}\cr
	&\phantom{{}=00}\llap{$y_{j}\in\{0,1\}$\quad for all $j\in\{1,2,3,4,5\}$}.\cr
}$$

\goodbreak

\noindent The formulation is all that is necessary for this problem. If this
integer program is solved, it is found that there are eight optimal feasible
solutions, each having total cost \$1350:
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#\cr
\omit&\multispan{17}\hrulefill\cr
\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt\cr
1&&A, B&&A, B&&B&&B&&C&&C&&C&&C&\cr
2&&F&&F&&A, F&&A, F&&A, F&&A, E&&B, D&&F&\cr
3&&---&&---&&---&&---&&---&&---&&---&&---&\cr
4&&D, E&&G&&D, E&&G&&D, E&&G&&G&&D, E&\cr
5&&C, G&&C, D, E&&C, G&&C, D, E&&B, G&&B, D, F&&A, E, F&&A, B, G&\cr
\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt&\omit&height2pt\cr
\omit&\multispan{17}\hrulefill\cr
}}$$
For instance, the first solution above has
$x_{\rm A1}=x_{\rm B1}=x_{\rm C5}=x_{\rm D4}=x_{\rm E4}=x_{\rm F2}=x_{\rm G5}=1$,
$y_1=y_2=y_4=y_5=1$, and all other variables~0. \qed

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

\bye
