%  Problem set 6
%  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

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

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent{\bf Solution.}\enspace\ignorespaces}

\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~6}
\smallskip
\centerline{Assigned Monday, June~22, 2015. Due Thursday, June~25, 2015.}

\medskip

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

\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.

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

\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.

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

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

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

\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.

\smallskip

\noindent[Hint: You may find it useful to prove and use Proposition~1 in
Section~A.2 of the textbook, on page~21.]

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

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

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

\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.

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

\bye
