Let G be a directed acyclic graph with the six vertices a, b, c, d, e, and f, and six edges b->d, c->d, e->b, e->c, f->b, and f->c.

1. Describe a topological ordering of G that could be produced by the reverse-postorder-DFS topological sorting algorithm.

2. If we list the vertices in the alphabetical order a, b, c, d, e, f, is this a topological order? Why or why not?

3. What is the minimum number of layers needed in a layered drawing of G, without any restrictions on the width of a layer? Give a drawing of G with this many layers.

4. What is the minimum number of layers in a layered drawing of G, if we require that each layer have at most two vertices? Give a drawing of G with this many layers.

5. Give a topological ordering that could have been produced by the Coffman-Graham algorithm for G: at each step, if there are two or more vertices that are all available to be added next to the ordering, you should choose one that became available the earliest.

6. How many layers does the Coffman-Graham layering algorithm use, when we require that each layer have at most two vertices? Give a drawing that could have been produced by this algorithm.

7. Among the vertices of G, which ones could be first in a topological ordering? Which ones could be last?