\problemdata
{S00 tut3}
{scheduling}
{graph}

\begin{problem} \textbf{Scheduling Courses}
% source: fall98/tutorials/H19-rec4.tex, beginning

We consider a simple kind of scheduling problem --- for MIT courses with
prerequisites.  The problem is to determine how a student could complete
all of the courses in the fewest terms, under the simplifying, if
unlikely, assumption that there is no limit on the number of courses a
student can take in a term as long as their prerequisites have all been
met.  We model this problem with a digraph.  An example is shown in
Figure~\ref{fig:dag}.

\begin{figure}[htbp]
  \centerline{\psfig{figure=figures/dag.eps,height=2.0in}}

  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag}
\end{figure}

This example is a DAG.  Of course it is possible that the faculty in
charge of courses created a cycle of prerequisites; this would mean
that it was impossible to fulfill the prerequisites of any of the
courses in the cycle before taking the course.  Presumably this would
not be the intention of the faculty, so we assume that whatever the
prerequisite requirements may be, they do not have cycles; so the
digraph corresponding to the prerequisites will always be a DAG.

The connectedness relation of a DAG is a {\em partial order}.  The
example in Figure~\ref{fig:dag} suggests the reason for this name.
The edges in this graph restrict the order in which a student may take
classes.  For example, 6.001 must be taken before 6.003.  Of course,
the student still has some choice about the order; for this reason,
the set of classes is said to be ``partially'' ordered by this system
of prerequisites.  If we write $u \succeq v$ to mean that $u=v$ or
there is a directed path from vertex $u$ to $v$, then the relation
$\succeq$ is obviously \emph{transitive}:
\[ [u \succeq v \wedge v \succeq w] \implies u \succeq w,\]
and \emph{antisymmetric}:
\[ [u \succeq v \wedge v \succeq u] \implies u = v.\]
Formally, a partial order on a set is just a binary relation which is
transitive and antisymmetric.

Two elements $u$ and $v$ are said to be {\em comparable} under a
partial order, $\succeq$, iff $u \succeq v \vee v \succeq u$.  When
the partial order is the one from the connectedness relation of a DAG,
vertices $u,v$ are comparable precisely when $u=v$ or there is a
directed path from $u$ to $v$ or vice-versa.  Otherwise, $u$ and $v$
are incomparable.  For example, 18.01 and 6.002 are comparable since
there is a directed path from 18.01 to 6.002.  However, 18.01 and 8.01
are incomparable because there is no directed path from one to the
other.

\begin{problemparts}

\problempart  How many terms are necessary to complete all of the
courses in Figure~\ref{fig:dag}, assuming prerequisites are observed,
but course load is no issue?

\solution
The answer is suggested by the way Figure~\ref{fig:dag} is drawn.
Each term the student could take all the courses in a horizontal row,
starting with the first row and working down.  All of the courses in
each row are incomparable, and all the necessary prerequisites are in
previous rows.  Since there are six rows, the student can finish in
six terms.

Furthermore, there is no way to finish in fewer than six terms, since each
term the student can take at most one course in the six-course sequence
18.01, 18.03, 6.002, 6.004, 6.033, 6.857.  Notice that this sequence
constitutes the longest directed path in the graph.
}

\problempart Explain why every (finite) DAG has a finite longest walk.

\solution{ If path was as long as number of vertices, $V$, a vertex
would repeat and this would be a cycle.  So the length of a path is at
most $\card{V}-1$.  So the set 
\[\set{\card{V} - (k+1) : k \mbox{ is the length of a path in the DAG}}\]
is a nonempty set of natural numbers, and by the Well-ordering Principle, it has a
least element $k_{min}$.  Then $\card{V}-k_{min}$ is nonempty the
length of the longest path.  QUIBBLE: why is the set nonempty?  Actually
it might be empty if the graph has no edges; to cover this case we should
regard a single vertex as a path of length 0.
}

\medskip

% A {\em chain} in a partial order, $\succeq$, is a single element or a
% nondecreasing sequence of elements.  That is, $a_1, a_2, \ldots, a_n$ is a
% chain providing $a_{i+1} \succeq a_i$ for all $1 \leq i < n$.  So every
% path in a DAG is a chain in the partial order determined by connectedness
% in the DAG.  An \emph{antichain} is a set of elements no two of which are
% comparable.  In a DAG, an antichain is a set of vertices with no paths
% connecting any two of them.  Any antichain in the course prerequisite DAG
% identifies a set of courses that can be taken in any order, or
% simultaneously, as long as their other prerequisites have been met.
 
We let $t$ be the number of vertices in the longest walk in the graph.
% This chain must be a path (Exercise: Why?).  
Now at least $t$ terms are
necessary to complete all the courses, because at most one course on the
chain can be taken each term.

\problempart Show that every DAG with a critical path of length $t$
has a schedule with $t$ steps.

  \solution{
    \begin{theorem*}
      If the longest path in a DAG $G$ has length $t-1$, then the
      vertices can be partitioned into a sequence of $t$ blocks such
      that any edge into a vertex must start at a vertex from an
      earlier block.
    \end{theorem*}

    \begin{proof}
    \end{proof}
   
  }

\problempart Show that there is a schedule for taking courses
which achieves the minimum number of terms, $t$.  

  \solution{
    The solution to the previous part implies that $t$ terms are
    sufficient.  In term $i$, the student should take the set of
    courses in the $i$th block.  Since the edges into any block come
    from an earlier block, all the prerequisites of courses in a block
    have been taken by the time the block is scheduled to be taken.
    And since the blocks partition the set of all courses, the student
    will complete every course.
    
  }
\end{problemparts}
\end{problem}
