1. Consider 27 cubes arranged in a 3x3x3 array. Form an associated graph with each cube viewed as a vertex, and with two vertices adjacent if their corresponding cubes have adjacent (touching) faces. Does this graph have a Hamiltonian path that starts at a vertex corresponding to the cube at the center, and ends at a vertex corresponding to a cube at one of the arrangement corners?

2. There are r*s couples at a dance. The men are divided into r groups, by age, with s guys in each group; the women are also divided into r groups, by height, with s women in each group. Show that r couples can be selected such that every height group and every age group is represented.

3. Two spanning trees on a weighted Graph G, say T1 and T2, are "neighbors" if T2 can be obtained by T1 by

(1) the addition of one arc to T1 to form a circuit; followed by

(2), the deletion of one arc in this cycle to form T2. Show that if T1 is not a minimal cost spanning tree,

then it is always possible to find a neighbor of T1 that costs less.

(In this way you could construct a lousy MST algorithm by first constructing any spanning tree,

and then by moving from cheaper neighbor to cheaper neighbor until no more improvement is possible).

To simplify your reasoning, you may assume that the edges in G have distinct values.

4. Suppose G is any undirected graph without circuits (not necessarily connected), and suppose further that the addition of any new edge between existing vertices of G always creates a circuit. Prove that G is a tree.

5. The number grid below represents a distance matrix for the edges of K5. Using the textbook branch-and-bound algorithm (the algorithm presented in class on 3/1), find the least-cost HAM circuit.

- 3 8 4 7 3 - 10 9 2 8 10 - 6 5 4 9 6 - 1 7 2 5 1 -

due date: Now due Thursday 3/8, at beginning of class

-- RobbieMoll - 23 Mar 2009

Topic revision: r6 - 2012-03-05 - RobbieMoll

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback