\problemdata
{DAG}
{topological sort}

\begin{problem}
\textbf{Topological Sort of a DAG}

Consider the following definitions of a \emph{cycle} and of a
\emph{directed acyclic graph (DAG)}.

\begin{definition*}
  A \textbf{cycle} is a walk that ends where it started (i.e., the
  last vertex equals the first).
\end{definition*}

\begin{definition*}
  A \textbf{directed acyclic graph (DAG)} is a directed graph with no
  cycles.
\end{definition*}

As an example, Figure~\ref{fig:dag-one} contains a picture of a directed
acyclic graph.

\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-one}
\end{figure}

Now, consider the following definition of a topological sort of the
vertices of a DAG $G$.

\begin{definition*}
  A \textbf{topological sort} of the vertices of a DAG $G$ is a
  sequence comprised of all the vertices of $G$ (each appearing once),
  such that for any two vertices $u$ and $v$ of $G$, if $u$ appears
  before $v$, then there is no edge from $v$ to $u$.
\end{definition*}

We want you to prove the following theorem.

\begin{theorem*}
  Every DAG has a topological sort.
\end{theorem*}

The trick that you need to use is that it is possible to pick a
``first'' vertex for your topological sort and then proceed
inductively.  

\bigskip
\hrule

\begin{problemparts}
\problempart 
Consider the following definition of a minimal vertex of a DAG.
Notice that there can be more than one minimal vertex.

\begin{definition*}
  A \textbf{minimal} vertex $u$ in a DAG $G$ is a vertex for which
  there does not exist another vertex $v$ in $G$ such that the edge
  from $v$ to $u$ is in $G$.
\end{definition*}

What is the minimal vertex of the DAG in Figure~\ref{fig:dag-one}?

  \solution{
    18.01, 8.01, 6.001, and 6.170 are all minimal vertices.
   
  }

\problempart 
In fact, every DAG has a minimal vertex.  Prove the following lemma.

\begin{lemma*}
  Every DAG has a minimal vertex.
\end{lemma*}
\solution{
  \begin{proof}
    We prove that every DAG $G$ has a minimal vertex by contradiction.
    Consider a DAG $G$ with $n$ vertices.  Suppose that no vertex of
    $G$ is minimal.  Then, for every vertex of the graph there exists
    another vertex that points to it.  Now, take some vertex $v \in G$
    and define the following walk in $G$ recursively: $v_0=v$, and for
    $i > 0$, $v_i$ is some vertex that points to the vertex $v_{i-1}$.

    This definition is a bit odd because it is nondeterministic.  But
    it doesn't matter which preceding vertex you pick at each step.
    The key is that it defines some $v_i$ for every $i$.

    Now note that the sequence of vertices $v_{n+1},\ldots,v_0$ is a
    walk of length $n+1$; call this walk $w$.  Since the DAG $G$ has
    only $n$ vertices, it follows that some vertex is repeated along
    the walk $w$; that is, it is the case that $v_i=v_j$, for some $i
    < j$.  But this means that $v_i,\ldots,v_j$ is a cycle, which is
    impossible in a DAG; thus, a contradiction.%
  \end{proof}
  }

\problempart 
Give an example of a topological sort of the vertices of the DAG in
Figure~\ref{fig:dag-one}.
 
  \solution{
    
  }

\problempart 
Use the above lemma to prove the existence of a topological sort for
every DAG.

  \solution{
    By (ordinary) induction. \\ $P(n)$ = any DAG $G$ with $n$ vertices
    has a topological sort.

    Base case $(P(1))$: for a DAG with one vertex, the one vertex
    makes a topological sort. \\ 

    Inductive step: Assume $(P(n))$. Consider a DAG $G'$ of $n+1$
    vertices and a DAG $G$ of $n$ vertices that results from removing
    an arbitrary minimal vertex of $G'$; call it $u$.  Recall that by
    our lemma any DAG has a minimal vertex.  We must also argue that
    what we are left is also a DAG.

    By the inductive hypothesis, the DAG $G$ has a topological sort.
    Thus, a topological sort for $G'$ is $u$ followed by all the other
    vertices in $G$ ordered according to the topological sort of $G$.

    Thus, we have shown by induction that every DAG has a topological
    sort.
  }
\end{problemparts}
\end{problem}
