1. Let the directed acyclic graph G1 have six vertices, a, b, c, d, e,
   and f, and seven edges a->b, a->c, b->d, b->e, c->e, d->f, and
   e->f. How many different topological orderings does G1 have? List
   them all. (See http://en.wikipedia.org/wiki/Topological_sorting.)

2. Let the directed graph G2 have eight vertices, a, b, c, d, e, f, g,
   and h, and 12 edges, a->c, a->h, b->d, c->g, e->b, e->f, e->g, f->a,
   f->e, g->a, h->a, and h->d. Draw the condensation of G2. (See
   http://en.wikipedia.org/wiki/Condensation_(graph_theory).)

3. Let the directed acyclic graph G3 have seven vertices, a, b, c, d, e,
   f, and g, and seven edges, a->b, a->c, a->d, a->e, b->g, e->f, and
   e->g. Show the assignments of the vertices of G to layers produced by

     (a) The longest path layering, in which each vertex's layer is the
     number of vertices in the longest directed path starting at that
     vertex,

     (b) The width-w layering (in which we start a new layer whenever
     the existing layer becomes full or would have a horizontal edge)
     for the vertex ordering a,b,c,d,e,f,g and width w=3.

4. Do either of the layerings from your answer to question 3 minimize
   the total length of all edges, where length is measured as the number
   of layers between the start and end of an edge? Why or why not?