\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}
\input psfig

\begin{document}

\psol{5}{October 14, 1996}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts

\ppart
Clearly the numbers $27$, $48$, $60$ and $72$ are maximal, since each 
divides no number in the list other than itself.  All of the other numbers 
divide 72, however, so they are not maximal.

\ppart
Only $2$ and $9$ are minimal.  Every other element is divisible by
either $2$ or $9$.  

\ppart
There is no greatest element, since, for example, there is no number
in the set that both $60$ and $72$ divide.

\ppart
There is no least element, since there is no number in the set that
divides both $2$ and $9$.

\ppart
We need to find numbers in the list that are multiples of both $2$ and
$9$.  Clearly $18$, $36$, and $72$ are the numbers we are looking for.

\ppart
Of the numbers we found in the previous part, $18$ satisfies the
definition of the least upper bound, since it divides the other two
upper bounds.

\ppart
We need to find numbers in the list that are divisors fo both $60$ and
$72$.  Clearly $2$, $4$, $6$, and $12$ are the numbers we are looking
for.

\ppart
Of the numbers we found in the previous parts, $12$ satisfies the
definition of the greatest lower bound, since the other three lower
bounds divide it.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts

\ppart 
First observe that $2e$ is the sum of the degrees of the vertices
(each edge contributes a degree of $2$ since it is incident to two
vertices).  But the total degree cannot be less than the minimum
degree multiplied by the number of vertices.  This means that $2e \geq
mv$ or that $2e/v \geq m$.

\ppart
As before, observe that $2e$ is the sum of the degress of the
vertices.  Since the total degree cannot be greater than the maximum
degree multiplied by the number of vertices.  This means that $2e \leq
Mv$ or that $2e/v \leq M$.

\ppart
Suppose $G$ has $n$ vertices.
Since $G$ has 15 edges and $\overline{G}$ has 13 edges, we know the
complete graph on $n$ vertices must have $15+13 = 28$ edges.  
Now the complete graph on $n$ vertices has $n(n-1)/2$ edges. (One way
to see this is to observe that vertex $1$ needs to be connected to
$2, 3, \ldots, n$ (total of $n-1$ edges), vertex $2$ needs to be
connected to $3, 4, \ldots, n$ (total of $n-2$ edges) and so on,
giving a total of $(n-1) + (n-2) + \cdots + 1 = n(n-1)/2$.)  This
means that we need to solve the equation $n(n-1)/2 = 28$, which can be
easily seen to be $n=8$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts

\ppart
We will list the tasks for each time slot (since the number of
processors is unlimited).

Time slot 1:  Foundation.  (1 processor)

Time slot 2:  Framing.  (1 processor)

Time slot 3:  Roof.  (1 processor)

Time slot 4:  Exterior siding (1 processor)

Time slot 5:  Plumbing, Wiring, Exterior painting  (3 processors)

Time slot 6:  Flooring, Wallboard, Exterior fixtures (3 processors)

Time slot 7:  Carpeting, Interior painting (2 processors)
 
Time slot 8:  Interior fixtures (1 processor)

Time slot 9:  Completion

\ppart
Without any other information, the bound is $2t$,  This is because
each task now takes time at most $2$.  So if we run the process in
such a way that a processor waits (rests) for one unit of time when it
runs a task that takes only one time unit, we have effectively put
ourselves in a situation where each task takes $2$ units of time.

We can exploit the information more optimally by doing the following:
Replace each task that takes time $2$ with two tasks that each take
time $1$, and where the first half needs to be completed before the
commencement of the second half.  This then gets us into a situation
where we can use the theorem directly to actually obtain a way to
schedule the tasks in stricly less than time $2t$ if such a way exists.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts

\ppart Let $G=(V,E)$ be an undirected graph, where $|V|=n$. Assume $G$
is represented by an adjacency matrix, $M$. Then, for every pair of
vertices, $(u,v)$, 
the number of even length paths of length $\leq n$,
can be obtained from $\sum_{i=1}^{\floor{n/2}}{M^{2i}}$, where the 
$(u,v)$ entry
of every such matrix, $M^{2k}$, $1\leq k\leq \floor{n/2}$, is the number of
distinct paths of length exactly $2k$ from $u$ to $v$ in $G$ (excluding 
cycles). For proof of
correctness, see Theorem $2$ on page $468$.

\ppart Let {\em EVEN} be the algorithm in part (a) except it now returns TRUE
whenever there exists an even-length path between a pair of vertices $(u,v)$. 
Let {\em ODD} be an algorithm that returns FALSE whenever 
there exists an odd-length path between a pair of vertices $(u,v)$, by checking
$\sum_{i=1}^{\floor{n/2}}{M^{2i-1}}$. Note that with {\em EVEN}
and {\em ODD}, as soon as an even-length and an odd-length path 
is found, we return the logical value TRUE and FALSE respectively. 
Then we have:\\
$P(u,v)=$ TRUE~ $\Longleftrightarrow~~\mbox{\em EVEN}~~\wedge~~\neg\mbox{\em ODD}=$ TRUE.

\ppart If the graph $G=(V,E)$ is bipartite, then there are two sets 
$V_1$, $V_2$ of vertices such that no two vertices in $V_1$ and no two 
vertices in $V_2$ are adjacent. For every pair of vertices, $(u,v)$, 
if $u\in V_1$ and $v\in V_2$ (or vice versa), and they share an edge, 
then there can never be an 
even-length path between them, and hence $P(u,v)$ is always false.
If $u$ and $v$ are both in $V_1$ or both in $V_2$, then there can never
be an odd-length path between them, and hence the problem reduces to 
finding an even-length path as we did in part (a).

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Vertices $c~\mbox{and}~ d$ are the cut vertices. The removal of either
one creates a graph with two components. The removal of any other
vertex does not disconnect the graph.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

Under these conditions, the matrix has a block structure, with all the
$1$'s confined to small squares (of various sizes) along the main
diagonal. The reason for this is that there are no edges between
different components. The only $1$'s occur inside the small
submatrices (but not all the entries in these square are $1$'s, of
course.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\bparts

\ppart For two nodes to have the same color, they must belong to the 
same $MIS$, since we color all the vertices of an $MIS$ with the same
color, and discard the used color so we never use that color again. 
But by definition, for any two vertices to be in the same $MIS$, they
must not be incident on the same edge in the graph. Hence, with 
this algorithm, we
never color the two endpoints of an edge with the same color.

\ppart 
\begin{proof} By induction on $d$: Let $P(d)$ denote the 
statement that any undirected graph
with degree $\leq d$ is $d+1$-colorable.\\ 
Base Case: $P(0)$ is clearly true since any graph with $0$ degree 
is $1$-colorable. $P(1)$ is also true since any graph with degree 
$\leq 1$ is $2$-colorable.\\
Inductive Case: We show for all $d,~P(d)\Rightarrow~P(d+1)$.\\ 
Let $G$ be any undirected graph with
degree $\leq {d+1}$. Choose any $MIS,~ V'$ in $G$ (note that an $MIS$
always exists: if the graph is complete, an $MIS$ consists of only one
node in the graph).  Color all the vertices in $V'$ using the same 
color. Now reduce the graph by removing all the vertices in $V'$ and their
incident edges, and discard the color. The degree of all the 
vertices in $V-V'$ must
be reduced by $\geq 1$, since every vertex $\not \in V'$ is adjacent to
some vertex $\in V'$. So the
reduced graph has degree $\leq d$, and thus by the induction
hypothesis is $d+1$-colorable. Adding the color that was used to 
color $V'$ to the set of $\leq {d+1}$ colors, implies that graph $G$ 
with degree $d+1$ is $d+2$-colorable.
\end{proof}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

We let the vertices of a graph be the animals, and we draw an edge
between two vertices if the animals they represent cannot be in the
same habitat because of their eating habits.   A coloring of this
graph gives an assignment of habitats, where the colors are the
habitats.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

Such a tree does exist. By Theorem $4(iii)$, we note that such a tree
must have $i=75/(m-1)$ internal nodes. This has to be a whole number,
so $m-1$ must divide $75$. This is possible, for example, if $m=6$, so
let us try it. A complete $6$-ary tree of height $2$ would have $36$
leaves. We therefore need to add $40$ leaves. This can be accomplished
by changing $8$ vertices at level $2$ to internal vertices; each such
change adds $5$ leaves to the tree ($6$ new leaves at level $3$, less
the one leaf at level $5$ that has been changed to an internal
vertex). We will not show a picture of this tree, but just summarize
its appearance. The root of the remaining $8$ vertices at level $2$
has $6$ children, giving $36$ vertices at level $2$. Of course, $28$
are leaves, and each of the remaining $8$ vertices at level $2$ has
$6$ children, living at level $3$, for a total of $48$ leaves at level
$3$. The total number of leaves is therefore $28+48=76$, as desired.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts
\ppart 
\begin{proof} By contradiction:\\
Suppose that not all the nodes in the graph have the same value.
Then by the well-ordering property there is a smallest value, $s$, among
the values of the nodes.  Note that this value may not be unique in 
the graph. Consider a node $v$ with value $s$. This node is connected
to another node with value $> s$. This is true because $s$ is the
smallest value in the graph, and $G$ is connected. But this 
implies that the average of the values of neighbors of $v$ must be
$>s$. But $s$ is the average of all such values. Contradiction!
Hence, in a connected graph if the value of 
every node is the {\em average} of its neighbors values, then all nodes
must have the same value.
\end{proof}

\ppart No the Theorem is no longer valid if the value of every node is
the {\em median} of the values of its neighbors. We give the following
counterexample.
\begin{figure}[h]
\centerline{\psfig{figure=median.ps,height=2in}}
\end{figure}

\eparts

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

\end{problems}

\end{document}





