Consider an 𝑛-point set 𝑉 in the unit square in the plane. We define a weight functio
Posted: Fri May 06, 2022 6:52 am
Consider an 𝑛-point set 𝑉
in the unit square in the
plane. We define a weight
function on the edge set of the
complete graph on 𝑉 : the weight of an
edge 𝑥𝑦 is the distance between the
points 𝑥 and 𝑦.
(c) Show that the total length of the
edges of a minimum spanning tree 𝑇 is at
most 10√𝑛.
in the unit square in the
plane. We define a weight
function on the edge set of the
complete graph on 𝑉 : the weight of an
edge 𝑥𝑦 is the distance between the
points 𝑥 and 𝑦.
(c) Show that the total length of the
edges of a minimum spanning tree 𝑇 is at
most 10√𝑛.