next up previous

CSE 5311 Fall 1999

Quiz #8

(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.

(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.