

\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{graphics}
\input{macros-course}

\begin{document}


\pset{3}{2/16/99 (w/ 3rd ed. refs 2/22)}{Tuesday, February 23}

\newcommand{\reserve}[1]{}

\newcommand{\solution}[1]{}
% \newcommand{\solution}[1]{\bigskip #1}

{\bf Reading assignment: Rosen sections 7.1--7.4, 7.8, 8.1--2, and
Handout 12: Notes on Graphs \& Trees}

Assume that all graphs are simple--- undirected with no multi-edges or
self-loops--- unless otherwise specified.

\begin{problems}

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

\problem {\bf (10 points)} The adjacency matrix of a graph is given below.

\[
\left[
\begin{array}{cccccc}
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0
\end{array}
\right]
\]

\begin{problemparts}

\problempart Draw the graph defined by this adjacency matrix.  Label
the vertices of your graph $1, 2, \ldots, 6$ so that vertex $i$
correponds to row and column $i$ of the matrix.

\solution{
\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{adjgraph.eps}}}
\bigskip
}

\problempart Determine the chromatic number of this graph, and
give a coloring of the vertices that uses the minimum number of
colors.

\solution{The diagram above shows a 3-coloring.  The chromatic number
cannot be less than 3, because vertices 1, 2, and 4 are all connected
and therefore must receive distinct colors.  Consequently, the
chromatic number of the graph is exactly 3.}

\end{problemparts}

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

\problem {\bf (10 points)} Let $G$ be a graph.  Prove that there is a
path from every vertex of odd degree to some other vertex of odd
degree.

\solution{
\begin{proof}
If graph $G$ has no vertex of odd degree, then the claim is true
vacuously.  Otherwise, let $v$ be a vertex of odd degree.  Consider a
longest path starting at $v$ in which each edge occurs at most once.
Then every edge leaving the final vertex on the path must already be
on the path.  We will show that this final vertex of the path is
another vertex of odd degree.

Since $v$ has odd degree, the path contains at least one edge.
Furthermore, the final vertex of the path cannot be $v$, since the
edges incident to $v$ would then consist of the first and last edge of
the path plus two edges for each time that the path crosses $v$--- an
even total.  Therefore, the edges incident to the final vertex of the
path consist of the final edge of the path plus two edges for each
time that the path crosses the final vertex--- an odd total, as
claimed.
\end{proof}
}

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

\problem {\bf (15 points)} An edge of a connected graph is called a {\em
cut-edge} if removing the edge disconnects the graph.  Prove that an
edge $e$ in a connected graph $G$ is a cut-edge if and only if no
simple cycle contains $e$.

For this problem, use the definition of a ``simple cycle'' given on
page 468 of Rosen (p.463 in ed.3).  (The lecture notes require a
simple cycle to have no repeated vertex, but Rosen requires no
repeated edge.)

\solution{
\begin{proof}
First, we prove that if $e$ is contained in a simple cycle, then $e$
is not a cut-edge.  Since $G$ is connected, there exists a path $P$
between every pair of distinct vertices $u$ and $v$.  We must show
that there still exists a path between $u$ and $v$ after edge $e$ is
removed.  Let $e, e_1, e_2, \ldots, e_n$ be the edges in a simple
cycle containing $e$.  Since the cycle is simple, none of the edges
$e_1, e_2, \ldots, e_n$ are equal to $e$.  Therefore, we can construct
a new path that connects $u$ and $v$, but does not contain edge $e$ by
substituting either $e_1, e_2, \ldots, e_n$ or $e_n, e_{n-1}, \ldots,
e_1$ in place of edge $e$ in the path $P$.  (Which sequence is
substituted for edge $e$ depends on the direction in which the path
$P$ traverses the edge $e$.)  This shows that the graph remains
connected after edge $e$ is removed, and so edge $e$ is not a
cut-edge.

Next, we prove that if $e$ is not a cut-edge, then $e$ is contained in
a simple cycle.  We will make use of Theorem 1 on page 469 of Rosen
(p.464 in ed.3), which states that there is a {\em simple} path
between every pair of distinct vertices in a connected graph.  Since
$e$ is not a cut-edge, the graph obtained by removing edge $e$ is
connected.  So by the theorem, there exists a simple path $P$
connecting the endpoints of edge edge $e$ even after edge $e$ is
removed from the graph.  Adjoining edge $e$ to path $P$ gives a simple
cycle containing edge $e$.
\end{proof}
}

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

\problem {\bf (15 points)} A graph $G$ is {\em self-complementary} if
$G$ and $\bar{G}$ are isomorphic.  The symbol $\bar{G}$, where $G$ is
a graph, is defined in problem 33 on page 456 of Rosen (p.449 in
ed.3).  The term ``isomorphic'' is defined on page 460 of Rosen (p.454
in ed.3).

\begin{problemparts}

\problempart Draw a self-complementary graph with more than one
vertex.

\solution{The simplest solution is given below.  Edges of the graph
are shown with solid lines, and edges of the complement are shown with
dotted lines.

\bigskip
\centerline{\resizebox{!}{1.5in}{\includegraphics{selfcomp.eps}}}
\bigskip
}

\problempart Give a formula for the number of edges in the complete
graph with $n$ vertices.  No proof is required.

\solution{In a complete graph, each of the $n$ vertices is joined by
edges to $n-1$ other vertices.  However, this counts every edge twice,
once for each endpoint.  Therefore, the number of edges in the
complete graph with $n$ vertices is

\[
\frac{n(n-1)}{2}.
\]
}

\problempart Show that if a graph $G$ is self-complementary, then the
number of vertices in $G$ is congruent to either 0 or 1 mod 4.

\solution{Let $m$ be the number of edges in $G$, let $\bar{m}$ be the
number of edges in the complementary graph $\bar{G}$, and let $n$ be
the number of vertices in each of these graphs.  If $G$ is
self-complementary, then $m$ and $\bar{m}$ must be equal.  Futhermore,
every edge in the complete graph on $n$ vertices is contained in
exactly one of the graphs $G$ and $\bar{G}$.  Therefore, $m + \bar{m}
= \frac{n(n-1)}{2}$.  Putting these two facts about $m$ and $\bar{m}$
together, we find that

\[
m = \bar{m} = \frac{n(n-1)}{4}.
\]

Since the number of edges in a graph must be an integer, $n (n-1)$
must be a multiple of 4.  That is, a self-complementary graph must
satisfy

\begin{eqnarray*}
n (n-1) \equiv 0 \pmod{4}.
\end{eqnarray*}

This congruence holds exactly when the number of vertices $n$ is
congruent to 0 or 1 mod 4.
}

\end{problemparts}


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

\problem {\bf (10 points)} Consider the following table of exchange
rates.  A table entry indicates that one unit of row-currency can be
exchanged for the given amount of column-currency.

\bigskip
\centerline{
\begin{tabular}{c|ccccc}
	    & \$ US & pounds & \$ Canada & euros & rubles \\ \hline
\$ US		& 1.00	& 0.61	& 1.49	& 0.89	& 24.50 \\
pounds		& 1.62	& 1.00	& 2.43	& 1.44	& 40.85 \\
\$ Canada 	& 0.66	& 0.42	& 1.00	& 0.59	& 16.50 \\
euros 		& 1.12	& 0.69	& 1.69	& 1.00	& 28.23 \\
rubles		& 0.04	& 0.02	& 0.05	& 0.03	& 1.00
\end{tabular}
}
\bigskip

%  I assume that the real values of the currencies in US dollars are as
%  follows:
%
%    $ US	pounds		$ Canada	euros		rubles
%    1.00	1.63		0.67		1.13		0.04
%
%  I want most transaction to be lose money, but I'll create a path
%  ($ US -> euros -> $ Canada -> pounds -> rubles -> $US) that
%  makes money.  There might be a shorter cycle that makes money
%  overall, though not with every trade.  Furthermore, I've ensured
%  that one can't do ($ US -> somthing -> $ US) and make money.

\begin{problemparts}
\problempart Express the information in this table using some type of
graph.

\solution{We can represent this table using a weighted, directed graph
as shown below.

\bigskip
\centerline{{\bf Picture to be added.}}
%\centerline{\resizebox{!}{2.5in}{\includegraphics{exchange.eps}}}
\bigskip
}

\problempart Suppose that I have 100 US dollars, and I want to
increase my number of dollars through a sequence of currency
exchanges.  Identify the abstract property that your graph must
possess in order for this to be possible and determine whether or not
your graph has this property.

\solution{There must be a direct cycle containing the US vertex such
that the product of the weights around the cycle is greater than 1.
The graph does contain at least one such cycle, which is shown with a
dotted line above.  The product of the weights around this cycle is
$1.0322\ldots$.}

\end{problemparts}

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

\problem {\bf (15 points)} This problem concerns Hamiltonian circuits
in $n$-cubes.  A {\em Hamiltonian circuit} in a graph is a circuit
traversing every vertex in the graph exactly once.  The $n$-cube is
defined on page 448 of Rosen (p.441 in ed.3).  (Rosen also uses the
name $Q_n$ for an $n$-cube.)  However, the following recursive
definition of an $n$-cube is equivalent to the one given in Rosen, but
may simplify your solutions.  A 0-cube is a single vertex.  An
$(n+1)$-cube consists of two $n$-cubes with corresponding vertices
joined by edges.  For example, a cube is two squares with
corresponding corners joined.

\begin{problemparts}
\problempart Draw a 4-cube.

\solution{
\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{fourcube.eps}}}
\bigskip
}

\problempart In your drawing, highlight a Hamiltonian circuit.

\solution{The dotted edges in the diagram above form a Hamiltonian
circuit.}

\problempart Use induction on $n$ to prove that an $n$-cube has a
Hamiltonian circuit for all $n \geq 2$.

\solution{The proof is by induction.  Let $P(n)$ be the proposition
that an $n$-cube has a Hamiltonian circuit.  In the base case, $P(2)$
is true, because a 2-cube is itself a cycle.

In the inductive step, assume that an $n$-cube has a Hamiltonian
circuit to prove that an $(n+1)$-cube has a Hamiltonian circuit.
Regard an $(n+1)$-cube as two $n$-cubes with corresponding vertices
joined.  The first $n$-cube has a Hamiltonian circuit $H$ by
induction, and there is a matching Hamiltonian circuit $H'$ in the
second $n$-cube.

Take an edge $(u, v) \in H$ and the corresponding edge $(u', v') \in
H'$.  We can construct a Hamiltonian circuit in the $(n+1)$-cube by
starting at vertex $u$, traversing the circuit $H$ all through the first
$n$-cube until reaching vertex $v$, crossing the edge $(v, v')$,
traversing the circuit $H'$ all through the second $n$-cube until
reaching vertex $u'$, and then crossing the edge $(u', u)$.
}
\end{problemparts}

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

\problem {\bf (15 points)} Many two-person games in which players
alternate moves--- like chess, checkers, and tic-tac-toe--- can be
represented abstractly by "game trees".

The root of a game tree has children labeled with each of the possible
initial moves by the first player.  For example, in the game tree for
tic-tac-toe, the root has nine children corresponding to the nine
boxes that the first player could mark with an "X".  Each of these
nodes has eight children corresponding to the eight remaining boxes
which the second player could mark with an "O", and so on.

In general, each node corresponds to a situation in the game, and its
children correspond to each of the possible moves by the player whose
turn it is in that situation.  The leaves of the tree correspond to
situations where no moves are possible --- the game is over.  The
leaves are labelled with \emph{win}, \emph{lose}, or \emph{draw},
indicating the outcome for the first player.  (A win for one player is
a loss for the other--- no "everybody wins"-type games at MIT. {\tt
:-)})

A \emph{strategy} for a player in a game specifies which move the
player should make in any situation where it is that player's turn to
move.  A \emph{winning} stategy ensures that the player will win no
matter what moves the other player makes.  Similarly, a
\emph{non-losing} stategy ensures that the player will \emph{win or
draw} no matter what moves the other player makes.

For example, most elementary school children figure out non-losing
strategies in tic-tac-toe for \emph{both} the first and second players.
There is no winning strategy in tic-tac-toe for either player.  No one
knows if any player has a winning strategy for chess or checkers.
However, on general principles, we can be sure that at least one player
has a non-losing strategy.

\begin{problemparts}

\problempart Prove that for any two-person game with a finite game
tree, at least one of the players has a non-losing strategy.

\solution{The proof is by strong induction on the depth of the game
tree.  Let $P(n)$ be the proposition that for a game tree of depth
$n$, at least one of the players has a non-losing strategy.

In the base case, a tree of depth 0 is a node labeled {\em win}, {\em
lose}, or {\em draw}.  If the node is labeled {\em win} or {\em draw},
then the first player has a non-losing strategy.  If the node is
labeled {\em draw} or {\em lose}, then the second player has a
non-losing strategy.  In all three cases, the proposition $P(0)$
holds.

In the inductive step, for $n \geq 0$ assume $P(1), P(2), \ldots,
P(n)$ to prove $P(n+1)$.  A game tree of depth $n+1$ consists of a
root joined to subtrees of depth at most $n$.  Let $A$ be the player
making a move in the situation corresponding to the root node, and let
$B$ be the other player.

If player $B$ has a non-losing strategy for every subtree, then player
$B$ has a non-losing strategy for the full game tree; no matter what
move player $A$ makes, player $B$ is left with a game tree for which
he has a non-losing strategy.

On the other hand, if player $B$ lacks a non-losing strategy for some
subtree, then by strong induction player $A$ has a non-losing strategy
for the same subtree.  Furthermore, player $A$ has a non-losing
strategy for the full game tree; namely, pick the subtree for which he
has a non-losing strategy on his first move, and then pursue that
non-losing strategy for the subtree.

In either case, at least one of the players has a non-losing strategy.
This shows that $P(0), P(1), \ldots, P(n)$ imply $P(n+1)$ and
completes the proof by strong induction.}

\problempart Show that either exactly one player has a winning
strategy, or both players have non-losing strategies.

\solution{}

\end{problemparts}

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

\reserve{
\problem {\bf (10 points)} The weighted graph below represents a system
of pipes.  The weight on an edge is the {\em capacity} of the
corresponding pipe; that is, the maximum rate at which water can pass
through the pipe in gallons per second.  Suppose that water enters the
system at vertex $S$ and leaves the system at vertex $T$.  The goal of
this problem is to determine the capacity of the system; that is, the
maximum rate at which water can pass through the entire system in
gallons per second.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{flowprob.eps}}}
\bigskip

\begin{problemparts}

\problempart Redraw the system of pipes.  For each pipe, indicate a
rate and direction of flow through the pipe so that the rate of flow
through the entire system is as large as possible.  Make sure that the
rate of flow through a pipe does not violate the limit given in the
diagram above.  Also, make sure that rate of flow into each vertex is
equal to the rate of flow out of the vertex (excluding vertices $S$
and $T$).  This establishes a lower bound on the capacity of the
system.

\solution{With the flow rates and directions shown below, the rate of
flow through the entire system is 7 gallons per second.  Therefore,
the capacity of the system is at least 7 gallons per second.

\bigskip
\centerline{\resizebox{!}{2.0in}{\includegraphics{flowsol.eps}}}
\bigskip
}

\problempart Find a set of pipes with minimum total capacity such that
removing those pipes from the system completely disconnects vertex $S$
from vertex $T$.  Mark these pipes on your diagram.  This establishes
an upper bound on the capacity of the system; the rate of flow from
$S$ to $T$ can be no greater than the total capacity of this set of
pipes.

\solution{The edges marked with X's in the diagram have a total
capacity of 7 gallons per second.  Removing these edges disconnects
$S$ from $T$.  Therefore, the capacity of the system is at most 7
gallons per second.}

\end{problemparts}

To receive full credit, your lower bound on the capacity of the system
from part (a) must equal your upper bound from part (b).
}

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

\problem {\bf (10 points)} A pair 6.042 students, Wendy and Steve,
have decided to devote some of their spare time this term to
establishing dominion over the entire galaxy.  Recognizing this as an
ambitious project, they worked out the following table of tasks on the
back of Steve's copy of the notes for recitation 2.

\begin{enumerate}
\item {\bf Devise a logo} and cool imperial theme music - 8 days.
\item {\bf Build a fleet} of Hyperwarp Stardestroyers out of eating
paraphenalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Wendy's cat, Muffy - 7 days, after task \#1.
\item {\bf Train an army} of elite interstellar warriors by dragging
people to see {\em The Phantom Menace} dozens of times - 4 days, after
tasks \#3 and \#4.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#5.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#5.
\end{enumerate}

Wendy and Steve want to complete all these tasks in the shortest
possible time.  However, they have agreed on some constraining work
rules.

\begin{itemize}

\item Only one person can be assigned to a particular task; they can
not work together on a single task.

\item Once a person is assigned to a task, that person must work
exclusively on the assignment until it is completed.  So, for example,
Wendy cannot work on building a fleet for a few days, run get shots
for Muffy, and then return to building the fleet.

\end{itemize}

For each task, the table above lists the time required for completion
and which other tasks must be finished before the given task is begun.

\begin{problemparts}
\problempart Express the information in the task list using some type
of graph.

\solution{ The information in the table is represented below in the
form of a directed acyclic graph.  Each vertex represents a task,
and the weight of a vertex is the completion time.  Each directed edge
represents a dependendency between tasks.

\bigskip
\centerline{\resizebox{!}{3.0in}{\includegraphics{conquest.eps}}}
\bigskip
}

\problempart Wendy and Steve want to know how long conquering the
galaxy will take.  Steve suggests dividing the total number of days of
work by the number of workers, which is two.  What lower bound on the
time to conquer the galaxy does this give, and why might the actual
time required be greater?

\solution{
\begin{eqnarray*}
\frac{8 + 18 + 9 + 7 + 4 + 6 + 8}{2} & = & 30 \text{ days}
\end{eqnarray*}

If working together and interrupting work on a task were permitted,
then this answer would be correct.  However, the rules may prevent
Wendy and Steve from both working all the time.}

\problempart Wendy proposes a different method for determining the
duration of their project.  She suggests looking at the duration of
the ``critical path'', the longest sequence of tasks such that each
depends on the one before.  What lower bound does this give, and why
might it also be too low?

\solution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 days), training the army (4 days), and then
defeating Microsoft (8 days).  Since these tasks must be done
sequentially, galactic conquest will require at least 29 days.

If there were enough workers, this answer would be correct; however,
with only two workers, Wendy and Steve may be unable to make progress
on the critical path every day.}

\problempart What is the minimum number of days that Wendy and Steve
need to conquer the galaxy?  No proof is required.

\solution{
36 days - add explanation.
}

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problems} \end{document}
