\documentstyle[12pt,amssymb,amstex,twoside]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{5}{October 1, 1996}{Start of Class, Thursday, October 10}

{\bf Reading:} Sections 6.6, 7.2--7.5, 7.8
of {\it Discrete Mathematics and its Applications} by Kenneth H.
Rosen.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%Sec. 6.6, Problem 22
{\bf [8 points]} (Problem 22, Sec. 6.6 of Rosen)

Answer the following questions concerning the poset 
$(\{2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72\},|)$. 
\begin{problemparts}
\problempart Find the maximal elements.
\problempart Find the minimal elements.
\problempart Is there a greatest element?
\problempart Is there a least element?
\problempart Find all upper bounds of $\{2,9\}$.
\problempart Find the least upper bound of $\{2,9\}$, if it exists.
\problempart Find all lower bounds of $\{60, 72\}$.
\problempart Find the greatest lower bound of $\{60, 72\}$, if it exists.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%sec 2.2, problem 11 and 15
{\bf [9 points]} (Problems 26 and 34, Sec. 7.2 of Rosen)

Let $G$ be a graph with $v$ vertices and $e$ edges. Let $M$ be the
maximum degree of the vertices fo $G$, and let $m$ be the minimum
degree of the vertices of $G$. Show that
\bparts
\ppart $2e/v \geq m$.
\ppart $2e/v \leq M$.
\ppart If $G$ is a simple graph with $15$ edges and $\overline G$ has 
$13$ edges, how many vertices does $G$ have?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%Nancy, Parallel scheduling
{\bf [10 points]} 

Recall the theorem given in class that given a task graph that is a
partial order with maximum chain length $t$, we can perform the entire
set of tasks, using an unlimited collection of parallel processors in 
time $t$.
\bparts
\ppart Apply this theorem to produce an optimal schedule for the task 
graph on page $419$ of Rosen. 
\ppart Give an upper bound on the parallel time for a 
generalization of this theorem, where some tasks take 
$1$ unit of time, and others take  $2$ units of time.
%\ppart Now suppose we have a limited number of processors, $P$, on which
%we like to perform $N$ tasks. Let $t$ be the length of the longest chain.
%Prove that we can perform all the tasks in time $t + N/P$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%Nancy

{\bf [18 points]}
\bparts
\ppart Give an algorithm to determine, given an undirected graph $G$, 
for all pairs of vertices, $(u,v)$, how many even-length paths there
are from $u$ to $v$. Explain why your algorithm is correct. Assume the 
graph is represented by an adjacency matrix.
\ppart Give an algorithm to determine, given an undirected graph $G$, 
for all pairs of vertices, $(u,v)$, whether or not the following 
predicate $P(u,v)$ is true:

$P(u,v)$: There is an even-length path, but no odd-length path, from
$u$ to $v$. Explain why your algorithm is correct.
\ppart Repeat (b), but now assume that your graph is bipartite. Can you
design a more efficent algorithm than your general algorithm in part (b)?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\problem
%Sec 7.2, Problem 38
%{\bf [8 points]} (Problem 38, Sec. 7.2 of Rosen)
%Describe an algorithm to decide whether a graph is bipartite.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [6 points]} 

Do Exercise $7.4-16$ on page $470$ of Rosen.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [10 points]} 

Do Exercise $7.4-30$ on page $472$ of Rosen.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%Nancy

{\bf [16 points]} 

An {\em independent set} of a graph $G=(V,E)$ is a subset $V'\subseteq V$ 
of vertices such that each edge in $E$ is incident on at most one vertex 
in $V'$. A {\em maximal independent set}, or {\em MIS}, is an independent 
set $V'$ such that for all vertices $v\in{V-V'}$, the set $V'\cup\{v\}$
is not independent, {\em i.e.}, every vertex not in $V'$ is adjacent to some 
vertex in $V'$. 

Consider an alternative graph coloring algorithm to the one given in
class, as follows:

Given an undirected graph $G$ with degree 
$\leq d$, choose any {\em MIS}, $V'$ of $G$. Color all the vertices of
$V'$ using the same color. Now discard the used color, and reduce the
graph $G$ by removing all the colored vertices and their incident
edges. Color the vertices of the remaining graph with the remaining
colors using the same procedure in a recursive manner. 
\bparts
\ppart Show that with this algorithm, we never color the two 
endpoints of an edge with the same color.
\ppart Prove by induction on $d$, that the algorithm uses $\leq {d+1}$
colors to color any undircted graph with degree $\leq d$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
%Sec 7.8, Problem 18

{\bf [7 points]} (Problem 18, Sec. 7.8 of Rosen)

A zoo wants to set up natural habitats in which to
exhibit its animals. Unfortunately, some animals will eat some of the
others when given the opportunity. How can a graph model and a
coloring be used to determine the number of different habitats needed
and the placement of the animals in these habitats?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [6 points]} 

Do Exercise $8.1-18$ on page $546$ of Rosen.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf [10 points]} 

\bparts
\ppart Prove the following theorem:\\
{\bf Theorem:} Given a connected graph $G=(V,E)$, where every node in
the graph is associated with a positive integer, {\em i.e.},
there is a function $f:V\longrightarrow \integers^{+}$, 
prove that if
the value of every node is the ``{\em average}'' (mean) of its 
neighbors values,
then all nodes must have the same value.
\ppart Is the theorem still valid if the value of every node is the
``{\em median}'' of its neighbors values? Either prove it, or
give a counterexample. (Definition: A median of a set of even size
is either of the two middle numbers. For example, if 
$A=\{1,2,3,4\}$, then either $2$ or $3$ is a median of the set $A$.)
\eparts

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

\end{problems} 
\end{document}


