CSE326 Assignment #4
Spring 2002

Due: Friday, May 24, 2002, at the beginning of class.



Reading in Lewis & Denenberg:


Problems

    1. Find a DAG that may be topologically sorted in two ways
    2. Find a DAG with more than 2 vertices that has only one topological sort

  2. Problem 12.1

  3. For each of the five properties of the Tree Characterization Theorem, Part I, find a graph which has that property but is not a tree. Hint: trees must be connected.

  4. Problem 12.11, part a only. Hint: find a counterexample.

  5. Problem 12.25

  6. Problem 12.32

  7. Extra Credit Problem 12.19

  8. Extra Credit Problem 12.11, part b.