CSE326 Assignment #4
Spring 2002
Due: Friday, May 24, 2002, at the beginning of class.
Reading in Lewis & Denenberg:
Problems
-
- Find a DAG that may be topologically sorted in two ways
- Find a DAG with more than 2 vertices that has only one
topological sort
- Problem 12.1
- 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.
- Problem 12.11, part a only. Hint: find a counterexample.
- Problem 12.25
- Problem 12.32
- Extra Credit Problem 12.19
- Extra Credit Problem 12.11, part b.