CSE 5311 Fall 1999

Quiz #8

1.

(8 points). You are given experimental data consisting of small DNA fragments. For each fragment f, it has been determined experimentally that certain fragments lie to the left of f on the chromosome, certain fragments lie to the right of f, and the rest can be on either side. How would you find a consistent ordering of the fragments from left to right that satisfies all the constaints? Solve this problem using one of the graph algorithms introduced in class.

2.

(12 points). Suppose graph G has two edge-disjoint spanning trees (two spanning trees that have no edges in common). Prove that in this graph G, every pair of nodes forms part of a cycle.