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.