Q3

Consider eight points on the Cartesian two-dimensional x-y plane.

For each pair of vertices u and v, the weight of edge uv is the Euclidean (Pythagorean) distance between those two points. For example, 

Q3.1

Using the algorithm of your choice, determine one possible minimum-weight spanning tree and compute its total distance, rounding your answer to one decimal place. Clearly show your steps.

Q3.2

Because many pairs of points have identical distances (e.g. dist(h, c) = dist(h, b) = dist(h, f) = √5), the above diagram has more than one minimum-weight spanning tree.

Determine the total number of minimum-weight spanning trees that exist in the above diagram. Clearly justify your answer.