### NAME:

### PRECEPT:

### LOGIN:

###
COS 226 Exercises on MST

**1. **
Label the following points in the plane A through I, respectively:
(1, 3) (2, 1) (2, 6) (1, 6) (6, 6) (3, 4) (3, 6) (5, 2) (5, 7)

Taking edge lengths (Euclidean distance) to be weights, consider
the weighted graph defined by the edges
A-B A-C C-G F-G B-F B-E B-H B-D D-H E-I G-I E-F E-H

Give the order in which the edges of the MST are discovered by
Kruskal's algorithm, breaking any ties in favor of the lexicographically
smallest edge (e.g., edge A-C is chosen before B-F which is chosen before
B-H).
Hint: to simplify your calculations, you can use the squares of the
distances instead of the distances.

**2. **
Answer question 1 for Prim's algorithm, starting the search at A,
breaking any ties in favor of the lexicographically smallest edge.
Hint: to simplify your calculations, you can use the squares of the distances
instead of the distances.

**3. **
Explain briefly, but rigorously, why running Kruskal's algorithm
(or Prim's algorithm) with the squares of the Euclidean distances results
in an MST on the original graph with the actual Euclidean distances.