CSE 5311 Fall 1999
- (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.